如何解决递归T（n）= T（n / 2）+ T（n / 4），T（1）= 0，T（2）= 1是T（n）=Θ（n lgφ），哪里是黄金分割率？

我的推导中有错误或者您的陈述中有错误。

---

您可以通过展开递归来做到这一点：

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)如果一个斐波那契数。

使用边界条件T(n/2^i) = T(1)have- 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 -> 0if则无关n->inf），您将得到：

T(n) = phi^(log2(n)+1) = phi * phi^log2(n)等于O(n^log2(phi))哪里log2(phi) = 0.694。

PS将其视为提示或建议。现在，您不需要大学或教授学习任何东西。决心和毅力更重要。不要害怕尝试做某事。您已经问过这个问题，并声称尝试在失败的地方尝试主方法。人们建议您采用一种完全不同的方法，在这里您声称您完全尝试了sam，但没有尝试过在先前案例中有效的方法。