如何解决递归T（n）= T（n / 2）+ T（n / 4），T（1）= 0，T（2）= 1是T（n）=Θ（n lgφ），哪里是黄金分割率？ [英] How to solve the recurrence T(n) = T(n/2) + T(n/4), T(1) = 0, T(2) = 1 is T(n) = Θ(n lg φ ), where φ is the golden ratio?

问题描述

我尝试了递归树方法，因为master方法不适用于此递归，但似乎也不是正确的方法，将不胜感激！

解决方案

要么我的推导中出现错误，要么您的陈述中有错误。

---

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

  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 ）如果

并将其剥离为 phi ^ n （5的平方根与复杂度无关，第二个 thi ^ n-> ; 0 如果 n-> inf ）您将得到：

T（n）= phi ^（log2（n）+1）= phi * phi ^ log2（n）等于 O（n ^ log2（ phi）），其中 log2（phi）= 0.694 。

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

I tried recursion tree method since the master method is not applicable for this recurrence but it seems that it is not the right method also, any help would be appreciated !

解决方案

Either I have an error somewhere in my derivation or there is an error in your statement.

---

You do this by unrolling the recursion:

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)

where F(i) if a Fibonacci number.

Using boundary condition 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) which is equal F(log2(n) + 1)

Now using this formula:

and stripping it to only phi^n (square root of 5 has nothing to do with complexity and the second thi^n -> 0 if n->inf) you will get:

T(n) = phi^(log2(n)+1) = phi * phi^log2(n) which is equal to O(n^log2(phi)), where log2(phi) = 0.694.

P.S. Look at it as a hint or a suggestion. Now you do not need college or a professor to learn something. Determination and perseverance is more important. Do not be afraid to try doing something. You already asked this question and claimed to try master method where you failed. People suggested you a completely different approach and here you claim that you tried completely the sam and have not tried the method that worked in a previous case.

这篇关于如何解决递归T（n）= T（n / 2）+ T（n / 4），T（1）= 0，T（2）= 1是T（n）=Θ（n lgφ），哪里是黄金分割率？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！