Lineárne a binárne vyhľadávanie. BST. Vyhľadávanie so spätným návratom.

Zhrnutie prednášky

Prednáška otvára novú veľkú tému algoritmov vyhľadávania a vyučujúci stručne predstavuje plán zvyšku semestra: binárne vyhľadávacie stromy, backtracking, dynamické programovanie (Fibonacciho postupnosť, edit distance), grafové algoritmy (prehľadávanie do hĺbky a šírky, Floydov a Floydov-Warshallov algoritmus), vyhľadávanie pomocou hašovania a hľadanie podreťazcov (hrubá sila, KMP, Boyer-Moore, Karp-Rabin). Triediace algoritmy sa presúvajú na záver semestra. Hlavná časť začína lineárnym vyhľadávaním na príklade poľa záznamov typu meno a priezvisko, kde sa hľadá podľa zvoleného kľúča. V neusporiadanom poli má vyhľadávanie lineárnu zložitosť O(n), pridanie prvku na koniec je konštantné. Následne sa ukazuje budovanie usporiadaného poľa postupným vkladaním prvkov, čo je príprava na rýchlejšie binárne vyhľadávanie.

• - Vyhľadávanie zisťuje, či a kde sa v dátovej štruktúre nachádza záznam s daným kľúčom; využíva sa napríklad v databázach.
• - Kľúčom je atribút záznamu (napr. priezvisko), podľa ktorého sa hľadá; kandidáti na kľúč jednoznačne identifikujú záznam.
• - Lineárne vyhľadávanie prechádza pole od začiatku, kým nenájde zhodu alebo nedôjde na koniec; časová zložitosť je O(n).
• - Pridanie prvku na koniec neusporiadaného poľa má konštantnú zložitosť, lebo nezávisí od počtu prvkov.
• - Usporiadané pole sa buduje postupným vkladaním (princíp insertion sortu) s lexikografickým porovnávaním.
• - Plán semestra: BST, backtracking, dynamické programovanie, grafy, hašovanie a vyhľadávanie podreťazcov; triedenie až na záver.

Zhrnutie pripravené s pomocou AI z prepisu videa.