この再発を解決する方法:T(n) = T(n/2) + T(n/4) + O(1)
これはT(n) = aT(n/b) + f(n). そして、しばらく行き詰まりました。
1965 次
1 に答える
5
Akra Bazziは、Masterメソッドよりもはるかに強力なメソッドです。
「非再帰的」項はO（1）であるため、方程式を解くことになります。
1/2^p + 1/4^p = 1
そして、あなたが得る答えはT(n) = Theta(n^p)
上記（の二次方程式）を解くと 、ファイが黄金比である1/2^pことがわかります。p = log_2 phi
私たちに与えるコンピューティングT(n) = Theta(n^0.694...)
于 2011-03-28T19:33:19.613 に答える