Prednaska - Vypoctova zlozitost algoritmov 2.11.2020 9:15

Zhrnutie prednášky

Prednáška dokončuje tému triedenia haldovým triedením (heapsort) ako príklad zrýchlenia algoritmu voľbou vhodnejšej údajovej štruktúry. Triedenie výberom maxima má zložitosť O(n²), pretože maximum sa hľadá v neusporiadanom lineárnom poli. Halda je binárny strom s vlastnosťou usporiadania (rodič je väčší alebo rovný ako potomkovia) a špecifickým tvarom (listy najviac v dvoch úrovniach, čo najviac vľavo). Dá sa implementovať priamo v poli, kde potomkovia prvku na indexe i ležia na indexoch 2i a 2i+1 a druhú polovicu poľa tvoria listy. Na príklade sa ukazuje preusporiadanie poľa na haldu odzadu výmenou rodiča s väčším z potomkov. V druhej časti hodiny sa má metóda rozdeľ a panuj rozobrať na ďalších problémoch vrátane otázky, kedy je vhodná.

• - Metódu rozdeľ a panuj využívajú QuickSort a MergeSort.
• - Triedenie výberom maxima má zložitosť O(n²), lebo maximum sa hľadá v neusporiadanom poli.
• - Halda je binárny strom, v ktorom je rodič väčší alebo rovný ako jeho potomkovia.
• - Tvar haldy: listy sú najviac v dvoch úrovniach a čo najviac vľavo, strom sa plní po úrovniach zľava doprava.
• - Haldu možno uložiť v poli indexovanom od 1: potomkovia prvku i sú na indexoch 2i a 2i+1.
• - Druhú (väčšiu) polovicu poľa tvoria listy, ktoré nemajú potomkov.
• - Pole sa preusporiada na haldu od polovice smerom dozadu výmenou rodiča s väčším z potomkov.

Zhrnutie pripravené s pomocou AI z prepisu videa.