Prezentacia - Vypoctova zlozitost algoritmov 12.10.2020 9:15

Zhrnutie prednášky

Prednáška nadväzuje na úvod do výpočtovej zložitosti algoritmov a zameriava sa na spôsob určovania časovej výpočtovej zložitosti pre základné algoritmické konštrukcie. Vysvetľuje sa zložitosť sekvencie ako súčet zložitostí jednotlivých príkazov, zložitosť vetvenia ako maximum zo zložitostí jednotlivých vetiev a zložitosť cyklu ako súčet zložitostí jednotlivých iterácií. Zavádza sa aj pojem asymptotickej výpočtovej zložitosti, ktorá vyjadruje rád rýchlosti rastu zložitosti pri porovnávaní dvoch funkcií pomocou ich pomeru. Na príklade výpočtu mocniny m^n sa demonštruje odvodenie zložitosti O(n) pomocou cyklu a naznačuje sa existencia rýchlejšieho algoritmu založeného na umocňovaní na druhú.

• - Zopakovanie definície časovej výpočtovej zložitosti ako funkcie závislej od veľkosti vstupu N
• - Zložitosť sekvencie sa počíta ako súčet zložitostí jednotlivých príkazov
• - Zložitosť vetvenia (if) sa určuje ako maximum zo zložitostí jednotlivých vetiev (najhorší prípad)
• - Zložitosť cyklu sa počíta ako súčet zložitostí jednotlivých iterácií tela cyklu
• - Asymptotická výpočtová zložitosť vyjadruje rád rastu funkcie porovnaním pomeru dvoch funkcií pri N smerujúcom do nekonečna
• - Príklad výpočtu mocniny m^n pomocou cyklu s N násobeniami vedie k zložitosti O(n)
• - Naznačený existuje rýchlejší algoritmus na výpočet mocniny pomocou opakovaného umocňovania na druhú

Zhrnutie pripravené s pomocou AI z prepisu videa.