时间复杂度递归式,该如何解决
时间复杂度递归式
时间复杂度递归式T（n）= 6T(n/5)+n , n>1. T(1)=Q(1)
Q(n)?
------解决方案--------------------
刚才又想了一下，不知道对不对
T(5n)=6T(n)+5n>6T(n)
若有某一个T(s)>s，则此后的T(s*5^k)>(6^k)*s，因此T(s*5^k)/(s*5^k)>(6/5)^k。
令n=s*5^k，即k=Ln(n/s)/Ln(5)，则可知道
T(n)/n>(6/5)^(Ln(n/s)/Ln(5))，当n->∞时该T(n)/n->∞，这表明T(n)为n的高阶无穷大量。
如此，则当n非常大时，有6T(n)>>n，此时有
T(5n)=6T(n)。
当T(n)=n^(Ln(6)/Ln(5))时，有
T(5n)=5^(Ln(6)/Ln(5)) * n^(Ln(6)/Ln(5))=6T(n)，因此T(n)应当与n^(Ln(6)/Ln(5))同阶
即T(n)=O(n^1.1133)
时间复杂度递归式T（n）= 6T(n/5)+n , n>1. T(1)=Q(1)
Q(n)?
------解决方案--------------------
刚才又想了一下，不知道对不对
T(5n)=6T(n)+5n>6T(n)
若有某一个T(s)>s，则此后的T(s*5^k)>(6^k)*s，因此T(s*5^k)/(s*5^k)>(6/5)^k。
令n=s*5^k，即k=Ln(n/s)/Ln(5)，则可知道
T(n)/n>(6/5)^(Ln(n/s)/Ln(5))，当n->∞时该T(n)/n->∞，这表明T(n)为n的高阶无穷大量。
如此，则当n非常大时，有6T(n)>>n，此时有
T(5n)=6T(n)。
当T(n)=n^(Ln(6)/Ln(5))时，有
T(5n)=5^(Ln(6)/Ln(5)) * n^(Ln(6)/Ln(5))=6T(n)，因此T(n)应当与n^(Ln(6)/Ln(5))同阶
即T(n)=O(n^1.1133)