Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Následující verze | Předchozí verze | ||
pitel:isz:vyhledavani_razeni [03. 07. 2012, 11.53:44] – upraveno mimo DokuWiki 127.0.0.1 | pitel:isz:vyhledavani_razeni [30. 12. 2022, 13.43:01] (aktuální) – upraveno mimo DokuWiki 127.0.0.1 | ||
---|---|---|---|
Řádek 1: | Řádek 1: | ||
+ | ====== Vyhledávání a řazení ====== | ||
+ | ====== Vyhledávání ====== | ||
+ | Nejdůležitějším parametrem je **přístupová doba**, tedy doba potřebná k nalezení požadované informace. Přesněji je možné uvádět: " | ||
+ | ===== Sekvenční vyhledávání v poli ===== | ||
+ | Po jednom prvku procházíme pole((neseřazené)) a kontrolujeme jestli se aktuální prvek shoduje s hledaným. Pokud je index prvku roven délce pole a ani tak jsme nenašli, je vyhledání neúspěšné. | ||
+ | |||
+ | * Minimální čas úspěšného vyhledání = 1 (hledaný byl hned první prvek) | ||
+ | * Maximální čas úspěšného vyhledání = N((délka pole)) (hledný prvek byl až na posledním místě) | ||
+ | * Průměrný čas úspěšného vyhledání = N/2 | ||
+ | * Čas neúspěšného vyhledání = N | ||
+ | |||
+ | Algoritmus je možné vylepšit tzv. zarážkou, která se přidá na konec pole. Pak samozřejmě vždy najdeme požadovaný prvek, a úspěch se pozná podle indexu prvku. | ||
+ | |||
+ | Dobrým vylepšením je v případě nalezení prvku tento prvek prohodit s jeho sousedem. Takto se často hledané prvky dostanou na začátek pole a budou tak nalézány dříve. | ||
+ | |||
+ | Pokud pole seřadíme, můžeme dříve detekovat nenalezení prvku. | ||
+ | |||
+ | ===== Binární vyhledávání ===== | ||
+ | [[wp> | ||
+ | |||
+ | Pracuje nad seřazeným polem a funguje na principu půlení intervalu. | ||
+ | |||
+ | <code pascal> | ||
+ | {Nastavení zarážek} | ||
+ | min := 1; {Pascal indexuje pole od 1} | ||
+ | max := N; {N je velikost pole A} | ||
+ | |||
+ | repeat | ||
+ | mid := (min + max) div 2; {Najdi prostřední prvek} | ||
+ | if x > A[mid] then | ||
+ | min := mid + 1 | ||
+ | else | ||
+ | max := mid - 1; {V opačném případě zpracujeme část menší než prostřední} | ||
+ | until (A[mid] = x) or (min > max); {Tohle opakujeme dokud prostřední prvek není tím hledaným nebo dokud není jak rozsah zmenšovat} | ||
+ | </ | ||
+ | |||
+ | Tato metoda má **logaritmickou složitost**. | ||
+ | ==== Binární vyhledávací strom ==== | ||
+ | [[wp> | ||
+ | |||
+ | Je to stromová datová struktura, kde každý uzel má nejvíce 2 potomky((proto binární)) a přitom levý potomek je menší a pravý je větší než rodičovský. | ||
+ | |||
+ | Vše potřebné je na výše uvedené Wikipedii. | ||
+ | |||
+ | ===== Hashovací tabulky ===== | ||
+ | [[wp> | ||
+ | |||
+ | FIXME | ||
+ | |||
+ | ==== Mapovací funkce ==== | ||
+ | [[wp> | ||
+ | |||
+ | Je to funkce, která se provede nad daty která chceme do tabulky přidat, nebo vyhledat, a podle ní se rozhodne ke kterému řádku tabulky přistoupíme. | ||
+ | |||
+ | Funkce musí být: | ||
+ | * Rychlá | ||
+ | * Způsobovat co nejméně kolizí (jinými slovy, musí vytvářet co možná nejunikátnější hashe) | ||
+ | |||
+ | ===== Prohledávání textu ===== | ||
+ | [[wp> | ||
+ | |||
+ | ==== Knuth-Morris-Pratt ==== | ||
+ | [[wp> | ||
+ | |||
+ | Ke své práci využívá konečný automat. Následující ukázka demonstruje automat pro hledaný vzorek //AABC// při použití abecedy {A,B,C}. | ||
+ | |||
+ | {{pitel: | ||
+ | |||
+ | Nevýhodou takového řešení je skutečnost, | ||
+ | |||
+ | {{pitel: | ||
+ | |||
+ | ==== Boyer-Moor ==== | ||
+ | [[wp> | ||
+ | |||
+ | Viz opora IAL strana 174 | ||
+ | |||
+ | ====== Řazení ====== | ||
+ | * [[wp> | ||
+ | * [[http:// | ||
+ | * [[pitel: | ||
+ | ====== Shrnutí ====== | ||
+ | * vyhledávání: | ||
+ | * prohledávání textu: naivní metoda, knuth-morris-pratt (konečný automat), boyer-moore (2 tabulky, porovnává se hledané slovo odzadu) | ||
+ | * řazení: bubble, insertion, select, merge, heap, quick | ||
+ | * Znát složitosti algoritmů |