ADŠ prednáška 04: Master theorem

Zhrnutie prednášky

Prednáška o časovej zložitosti rekurzívnych algoritmov sa začína na príklade Merge Sortu, ktorý využíva techniku rozdeľuj a panuj. Pole sa opakovane rozdelí na polovice až na jednoprvkové časti, ktoré sú triviálne usporiadané, a potom sa postupne spájajú do väčších usporiadaných celkov. Kľúčovou pomocnou operáciou je funkcia merge, ktorá spojí dve usporiadané polia pomocou dvoch indexov a jedným porovnaním získa vždy ďalší prvok výstupu, takže pracuje v lineárnom čase. Ukázala sa implementácia v Pythone vrátane testov a ladiacich výpisov, ktoré ukazujú postupnosť rekurzívnych volaní. Tento príklad slúži ako východisko pre odhad zložitosti rekurzívnych programov a následné všeobecné techniky, ako je Master theorem.

• - Rozdeľuj a panuj: problém sa rozdelí na menšie podproblémy, ktoré sa vyriešia rekurzívne a ich výsledky sa spoja.
• - Merge Sort delí pole na dve polovice, každú rekurzívne usporiada a výsledky spojí.
• - Pole s najviac jedným prvkom je už usporiadané, čo je ukončovacia podmienka rekurzie.
• - Funkcia merge spája dve usporiadané polia pomocou dvoch indexov, pričom každé porovnanie pridá do výstupu jeden prvok.
• - Po vyčerpaní jedného poľa sa zvyšné prvky druhého poľa jednoducho pridajú na koniec výstupu.
• - Pridávanie prvku na koniec poľa v Pythone sa zatiaľ považuje za konštantné, vysvetlenie príde na neskoršej prednáške.
• - Ladiace výpisy názorne ukazujú strom rekurzívnych volaní a dopĺňajú pochopenie rekurzie.

Zhrnutie pripravené s pomocou AI z prepisu videa.