Vyhledávání, třídění, složitost IB111 Programování a algoritmizace 2010 Otrávené studny 8 studen, jedna z nich je otrávená laboratorní rozbor dokáže rozpoznat přítomnost jedu ve vodě je drahý kolik rozborů potřebujeme? Vyhledávání: hra myslím si přirozené číslo X mezi 1 a 1000 povolená otázka: „Je X menší než N? kolik otázek potřebujete na odhalení čísla? (kolik předem formulovaných otázek potřebujete?) Vyhledávání: problém mnoho různých variant, základní verze: vstup: setříděná posloupnost čísel + dotaz (číslo) např. 2, 3, 7, 8, 9, 14 + dotaz 8 výstup: index hledaného čísla v posloupnosti (případně -1 pokud tam není) např. 3 Vyhledávání a logaritmus naivní metoda = průchod seznamu lineární vyhledávání pomalé (viz např. databáze s milióny záznamů) jen velmi krátké seznamy základní rozumná metoda = půlení intervalu analogicky hře s hádáním čísel podívám se na prostřední člen podle jeho hodnoty pokračuji v levém/pravém intervalu logaritmický počet kroků (vzhledem k délce seznamu) Vyhledávání půlením intervalu (rekurzivně) Vyhledávání půlením intervalu (iterativně) Upozornění k uvedeným algoritmům uvedené pseudokódy nejsou přímo v Pythonu hlavní rozdíl: indexování od 0 vs od 1 záměr: abyste trénovali čtení různých notací abyste při přepisování kódu museli přemýšlet Vyhledávací stromy (více později) Třídění: komentář terminologie: třídění, řazení mnoho různých algoritmů pro stejný účel většina programovacích jazyků má vestavěnou podporu (funkce sort()) Proč se tím tedy zabýváme? Třídění: komentář Proč se tím tedy zabýváme? 1 ilustrace algoritmického myšlení, technik návrhu algoritmů 2 ilustrace drobné změny algoritmu s velkým dopadem na rychlost programu 3 tradice, hezky se to vizualizuje a vysvětluje Doporučený zdroj http://www.sorting-algorithms.com/ animace kódy vizualizace Více podobných: Google → sorting algorithms Třídění: problém vstup: posloupnost (přirozených) čísel např. 8, 2, 14, 3, 7, 9 výstup: setříděná posloupnost např. 2, 3, 7, 8, 9, 14 Co vy na to? zkuste vymyslet třídící algoritmus co nejvíce různých principů co nejefektivnější algoritmus možná inspirace: jak třídíte karty? Složitost n – délka vstupní posloupnosti počet operací jednoduché algoritmy O(n2 ), „kvadratická složitější algoritmy O(n log(n)) Bubble sort probublávání vyšších hodnot nahoru srovnávání a prohazování sousedů for i in range(n): print a for j in range(n-i-1): if a[j] > a[j+1]: a[j], a[j+1] = a[j+1], a[j] # paralelní přiřazení; # = prohození hodnot invariant cyklu: a[n-i-1..n-1] ve finální pozici Bubble sort: příklad běhu [8, 2, 7, 14, 3, 1] [2, 7, 8, 3, 1, 14] [2, 7, 3, 1, 8, 14] [2, 3, 1, 7, 8, 14] [2, 1, 3, 7, 8, 14] [1, 2, 3, 7, 8, 14] Select sort třídění výběrem projdeme dosud nesetříděnou část pole a vybereme nejmenší prvek nejmenší prvek zařadíme na aktuální pozici (výměnou) Select sort Insert sort zatřiďování prefix pole udržujeme setříděný každou další hodnotu zařadíme tam, kam patří „třídění karet Insert sort Quick sort rekurzivní algoritmus vybereme „pivota a pole rozdělíme na dvě části: větší než pivot menší než pivot obě části pak nezávisle setřídíme (rekurzivně pomocí quick sortu) Quick sort ilustrace Quick sort pokud máme smůlu při výběru pivota, tak je stejně pomalý jako předchozí v průměrném případě je rychlý – quick O(n log(n)) Merge sort rekurzivní algoritmus pole rozdělíme na dvě poloviny a ty setřídíme (merge sort) ze setříděných polovin vyrobíme jedno setříděné pole – „zipování Merge sort Operace Merge Radix sort předchozí algoritmy využívají pouze operaci porovnání dvou hodnot aplikovatelné na cokoliv, co lze porovnávat, žádné další předpoklady s doplňujícími předpoklady můžeme dostat nové algoritmy (obecný princip) Radix sort aplikovatelné na (krátká) čísla postupujeme od nejméně významné cifry k nejvýznamnější setřídíme pole podle dané cifry = rozdělení do 10 „kyblíčků (jednoduché, rychlé) Radix sort ilustrace Složitost trochu podrobněji složitost algoritmu – jak je algoritmus výpočetně náročný časová, prostorová měříme počet operací nikoliv čas na konkrétním stroji vyjadřujeme jako funkci délky vstupu O notace – zanedbáváme konstanty např. O(n), O(n log(n)), O(n2 ) Ilustrace rozdílů v složitosti Složitost třídících algoritmů n – délka vstupní posloupnosti počet operací jednoduché algoritmy O(n2 ), „kvadratická složitější algoritmy O(n log(n)) Shrnutí vyhledávání: půlení intervalu, rekurze třídící algoritmy: jednoduché (kvadratické): bubble, selection, insertion složitější (n log n, rekurzivní): quick sort, merge sort