Cvicenie - Vypoctova zlozitost algoritmov 14.10.2020 13:00

Zhrnutie prednášky

Úvod online cvičenia pozostáva z organizačných poznámok o odovzdávaní riešení cez test v e-kurze Moodle, kde sa nedá vracať medzi otázkami. Hlavná časť nadväzuje na pondelkovú prednášku o rýchlom umocňovaní M na N, pri ktorom sa počíta počet násobení v závislosti od exponentu. Pre párny exponent sa exponent polovičí a pre nepárny sa zníži o 1, takže T(33) = 1 + T(32) = 7 a T(34) = 1 + T(17) = 7. Najhorší prípad nastáva pre n = 2^k − 1 a zložitosť vychádza približne 2·log2(n+1) − 1. Ďalšia úloha spočíva v ukázaní, že táto funkcia je asymptoticky ohraničená zhora funkciou log n, a to experimentálne v Exceli s voľbou konštanty c.

• - Zložitosť umocňovania sa meria počtom násobení v závislosti od exponentu n.
• - Nepárny exponent sa znižuje o 1, párny sa polovičí, preto párna vetva vedie k cieľu rýchlejšie.
• - Rekurentne platí T(33) = 1 + T(32) = 7 a T(34) = 1 + T(17) = 7, pričom hodnoty sa čítajú z grafu.
• - Najhorší prípad nastáva pre n = 2^k − 1 a výsledná zložitosť je 2·log2(n+1) − 1.
• - Funkcia zložitosti je asymptoticky ohraničená zhora logaritmom, O(log n), nezávisle od základu logaritmu.
• - Horná hranica sa overuje v Exceli voľbou kladnej konštanty c tak, aby c·log2(n) bolo väčšie ako zložitosť.
• - Nerovnosť musí platiť len pre všetky n od určitej hranice ďalej, nie nutne pre všetky n.

Zhrnutie pripravené s pomocou AI z prepisu videa.