Algoritmy a dátové štruktúry prednáška 02

Zhrnutie prednášky

Prednáška nadväzuje na predchádzajúcu analýzu rekurzívnych algoritmov a zovšeobecňuje ju pre programy typu rozdeľuj a panuj, ktoré vstup veľkosti n rozdelia na a podproblémov veľkosti n/b a mimo rekurzie vykonajú prácu rádovo n na c. Pomocou rozkreslenia stromu rekurzie a súčtu geometrického radu sa odvodzujú tri prípady podľa hodnoty kvocientu a/(b na c) - menší, rovný alebo väčší ako jedna - čo vedie k výsledku známemu ako Master Theorem. Druhá časť prednášky sa venuje amortizovanej časovej zložitosti na príklade smutného žeriavnika v prístave, ktorý pomocou dvoch kôp kontajnerov (vstupnej a výstupnej) implementuje frontu; jednotlivý výber môže trvať lineárne dlho, no v súčte n operácií trvá len O(n), teda amortizovane konštantne. Na záver sa načrtáva problém neefektívneho zväčšovania statického poľa (po jednom prvku alebo po pevných blokoch), ktorý vedie ku kvadratickej zložitosti a ktorý sa má riešiť v nasledujúcej prednáške.

• Rekurentný vzťah T(n) = a·T(n/b) + O(n^c)
• Analýza pomocou stromu rekurzie a geometrického radu
• Tri prípady podľa kvocientu a/b^c
• Master Theorem
• Amortizovaná časová zložitosť - princíp a motivácia
• Príbeh žeriavnika a implementácia fronty dvoma kôpkami kontajnerov
• Amortizovaná vs. najhoršia časová zložitosť jednej operácie
• Problém neefektívneho zväčšovania statického poľa

Zhrnutie pripravené s pomocou AI z prepisu videa.