Matematické Fórum

mikejestrab · 18. 12. 2017 14:01

Zdravím, nejsem si jistý, jak postupovat při řešení takovéto úlohy:
Pomocí mistrovské metody určete asymptotický odhad funkce $t(n)=8t(n/2) + n^2 +n$ .
Z definice víme, že $f(n)=n^2+n, a=8, b=2, \log_{2}8=3$ $=>$ $n^{\log_{b}a}=n^3$ .

Jak teď můžu vyjádřit tu asymptotickou složitost? Můžu říci, že:
$f(n) = O(n^{3-\varepsilon})$ např. pro $\varepsilon = (0,1) => t(n) = \Theta (n^3)$ ?

Matematické Fórum

#1 18. 12. 2017 14:01

Rekurentní rovnice - Master Theorem

Zápatí