我尝试了递归树方法,因为主方法不适用于这种递归,但它似乎也不是正确的方法,我们将不胜感激!
最佳答案
要么是我的推导某处有误,要么是你的陈述有误。
你通过展开递归来做到这一点:
T(n) = T(n/2) + T(n/4) = 2T(n/4) + T(n/8)
T(n) = 3T(n/8) + 2T(n/16)
T(n) = 5T(n/16) + 3T(n/32)
....
T(n) = F(i + 1)T(n/2^(i-1)) + F(i)T(n/2^i)
如果 F(i)
Fibonacci number .
使用边界条件 T(n/2^i) = T(1)
有 n = 2^i
-> i = log2(n)
。
T(n) = F(log2(n) + 1) T(2) + F(log2(n)) T(1)
等于 F(log2( n) + 1)
现在使用这个公式:
并将其剥离为仅 phi^n
(5 的平方根与复杂度无关,第二个 thi^n -> 0
if n ->inf
) 你会得到:
T(n) = phi^(log2(n)+1) = phi * phi^log2(n)
等于 O(n^log2(phi))
,其中 log2(phi) = 0.694
。
P.S. 将其视为提示或建议。现在你不需要大学或教授来学习一些东西。决心和毅力更重要。不要害怕尝试做某事。你已经问过this question并声称在你失败的地方尝试主方法。人们向您建议了一种完全不同的方法,而您在这里声称您完全尝试了相同的方法,并且没有尝试过在以前的案例中有效的方法。
关于algorithm - 如何求解递归 T(n) = T(n/2) + T(n/4), T(1) = 0, T(2) = 1 即 T(n) = Θ(n lg φ ),其中 φ 是黄金比例?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34150768/