Efektívne algoritmy a zložitosť - 07 - Master theorem. Najbližší pár bodov.

Zhrnutie prednášky

Prednáška rekapituluje metódu rozdeľuj a panuj, ktorej časovú zložitosť popisuje rekurencia T(n) = a·T(n/b) + f(n), a Master theorem na jej riešenie. Dôkaz sa vedie cez strom rekurzívnych volaní, kde sa práca sčíta po úrovniach: listy prispievajú Θ(n^k), kde k = log_b a, a vnútorné úrovne tvoria sumu a^j·f(n/b^j). Ak je f(n) = O(n^(k−ε)), suma tvorí geometrický rad a celkovo vychádza Θ(n^k). Ak je f(n) = Θ(n^k), každá z log n úrovní prispieva Θ(n^k), a teda T(n) = Θ(n^k log n). Rozbor tretieho prípadu, kde dominuje koreň stromu a využije sa podmienka regularity, sa v úvode prepisu len začína.

• - Rekurencia T(n) = a·T(n/b) + f(n) charakterizuje algoritmy typu rozdeľuj a panuj.
• - Strom rekurzívnych volaní: práca sa sčíta po úrovniach a v listoch, ktorých je n^(log_b a).
• - Prípad 1: f(n) = O(n^(k−ε)) dáva T(n) = Θ(n^k), dominujú listy.
• - Prípad 2: f(n) = Θ(n^k) dáva T(n) = Θ(n^k log n), úrovne sú vyvážené.
• - Prípad 3: f(n) = Ω(n^(k+ε)) s podmienkou regularity dáva T(n) = Θ(f(n)), dominuje koreň.
• - Pri dôkaze prvého prípadu sa využíva súčet geometrického radu a identita b^k = a.

Zhrnutie pripravené s pomocou AI z prepisu videa.