Naučte se

Nechť a ≥ 1 a b > 1 jsou reálné konstanty, f(n) kladná funkce jedné proměnné. Uvažujme rekurentní rovnici

t(n) = a·t(nb) + f(n),

kde n/b může znamenat ⌈n/b⌉ listů a ⌊n/b⌋ a tyto rozdíly zanedbáváme. Pak t(n) má následující asymptotické řešení:

  • Pokud f(n) = O(nlogba−ε)pro nějakou konstantu ε > 0, pak t(n) = Θ(nlogba).
  • Pokud f(n) = Θ(nlogba), pak t(n) = Θ(nlogbalogn).
  • Pokud f(n) = Ω(nlogba+ε) pro nějakou konstantu ε >0 a pokud:
    • af(n/b) ≤ d·f(n) pro nějakou konstantu d∈(0,1)a všechna n≥n0, pak t(n) = Θ(f(n)). (opak případu (1), f(n) je polynomiálně větší než logba.)

Tyto 3 případy nepokrývají všechny případy. Pokud je rozdíl mezi funkcemi menší než polynomiální, nelze tuto metodu použít!

Od iterační metody k mistrovské

    t(n)    = a·t(n/b) + f(n),
            = a·t(n/b) + a2·t(n/b2)
            = f(n) + a2·t(n/b2) + a3·t(n/b3)
        = k−1^∑_j=0 aj·f(n/bj) + ak·t(1) (pro 1≤k≤logbn)
            ...
            Záleží na tom, co je asymptoticky ”větší" nlogba nebo suma závislá na f(n)

Související