ADŠ prednáška 05: Amortizovaná časová zložitosť. Neefektívne prioritné fronty.

Zhrnutie prednášky

Prednáška najprv zopakuje analýzu rekurzívnych algoritmov typu rozdeluj a panuj, kde sa práca sčíta po vrstvách stromu rekurzie a tvorí geometrickú postupnosť. Keďže súčet takejto postupnosti je úmerný jej najväčšiemu členu, rozhoduje buď práca v koreni, alebo práca na najmenších podproblémoch, čo vedie k Master theorem. Potom sa zavádza nová téma, amortizovaná analýza, na príbehu žeriavnika v prístave. Kontajnery sa vykladajú na dve kopy (zásobníky) a musia sa odvážať v poradí príchodu, čiže ako vo fronte. Pri odvoze treba niekedy všetky kontajnery presunúť z jednej kopy na druhú, takže jedna operácia je drahá, no iné sú lacné. Na takomto príklade sa ukazuje, že niektoré programy nepotrebujú na každú operáciu rovnaký čas.

• - Rekurzívne algoritmy typu rozdeluj a panuj sa analyzujú sčítaním práce po vrstvách stromu rekurzie.
• - Práca na jednotlivých vrstvách tvorí geometrickú postupnosť, takže jej súčet je úmerný najväčšiemu členu.
• - Konštantné faktory a posun hĺbky stromu o ±1 sú pri asymptotickej zložitosti nepodstatné.
• - Podľa kvocientu postupnosti dominuje buď práca v koreni, alebo práca na najmenších podproblémoch (Master theorem).
• - Príbeh žeriavnika: kontajnery sa odvážajú v poradí príchodu (FIFO), pričom sa ukladajú na dve kopy.
• - Pri odvoze treba občas presunúť celú kopu na druhú, takže niektoré operácie sú drahé a iné lacné.
• - Amortizovaná analýza hodnotí cenu operácií v dlhšej postupnosti, nie len v najhoršom prípade jednej operácie.

Zhrnutie pripravené s pomocou AI z prepisu videa.