2019 - Týždeň 4

Zhrnutie prednášky

Prednáška nadväzuje na štruktúry z minulého týždňa, kde sa v poli štruktúr osôb vyhľadávalo lineárnym vyhľadávaním. Lineárne vyhľadávanie prechádza prvky postupne a má zložitosť O(n), pričom v najhoršom prípade sa prejdú všetky prvky. Binárne vyhľadávanie využíva princíp rozdeľuj a panuj, polovicou krokov zahadzuje polovicu možností a má logaritmickú zložitosť log2 n. Vyžaduje však usporiadané pole, preto sa v štandardnej knižnici stdlib nachádza okrem funkcie bsearch aj triediaci algoritmus qsort (quicksort). Na záver sa rozoberajú parametre funkcie qsort, napríklad ukazovateľ na začiatok poľa a počet prvkov. V úvode sa ešte pripomínajú organizačné záležitosti, najmä termín ďalšieho zadania a podujatie Mach­ňáč deň.

• - Lineárne vyhľadávanie prechádza prvky jeden po druhom, zložitosť O(n).
• - Binárne vyhľadávanie v každom kroku zahodí polovicu možností, zložitosť O(log2 n).
• - Binárne vyhľadávanie funguje na princípe divide and conquer (rozdeľuj a panuj).
• - Podmienkou binárneho vyhľadávania je usporiadané pole.
• - Štandardná knižnica stdlib obsahuje funkcie bsearch a qsort (quicksort) namiesto ručne písaného bubble sortu.
• - Funkcia qsort má parametre: ukazovateľ na začiatok poľa (base), počet prvkov (nmemb) a veľkosť prvku (size).

Zhrnutie pripravené s pomocou AI z prepisu videa.