如何解决这种重复：T(n) = T(n/2) + T(n/4) + O(1)
Master Method 似乎没有帮助，因为这不是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)
我相信解决上述问题（in 中的二次方1/2^p）为我们提供了p = log_2 phi phi 是黄金比例的地方。
计算给我们T(n) = Theta(n^0.694...)
于 2011-03-28T19:33:19.613 回答