如何解决递归T（n）= T（n / 2）+ T（n / 4），T（1）= 0，T（2）= 1是T（n）=Θ（nlgφ），其中φ是黄金比例？

Question

我尝试了递归树方法，因为主方法不适用于此重复，但似乎它也不是正确的方法，任何帮助将不胜感激！

Answer 1

要么我在推导中某处出错，要么你的陈述中有错误。

---

您可以通过展开递归来执行此操作：

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，如果n->inf）你会得到：

qazxsw poi等于qazxsw poi，其中qazxsw poi。

附：将其视为提示或建议。现在你不需要大学或教授来学习。决心和毅力更重要。不要害怕尝试做某事。您已经问过T(n) = phi^(log2(n)+1) = phi * phi^log2(n)并声称尝试了失败的主方法。人们建议你采用一种完全不同的方法，在这里你声称你完全尝试了山姆，并没有尝试过在以前的情况下工作的方法。