← Sve lekcije

Master teorem i rekurzivno stablo

Za T(n) = a·T(n/b) + Θ(nk): usporedi a s bk. Ovdje vidiš i zašto to radi: trošak razine i u rekurzivnom stablu je nk·(a/bk)i, pa ovisi samo o tome pada li, stoji ili raste.

Trošak po razinama Ci

Rekurzivno stablo

Tablica razina


        
lokalni rad f(n), daje k rekurzivni pozivi, daju a i b
Koji slučaj vrijedi?
0 / 0

Pazi: nisu svi zadaci za Master teorem. Ako se argument oduzima (n − 1, n − 2), Master teorem se ne primjenjuje.