求解递归T(n)= 2T(n / 2)+ sqrt(n) [英] Solving a recurrence T(n) = 2T(n/2) + sqrt(n)
本文介绍了求解递归T(n)= 2T(n / 2)+ sqrt(n)的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
需要一点帮助!到目前为止,这是我使用向后替换的方法:
Need a little help! This is what I have so far using backward substitution:
T(n) = 2T(n/2) + sqrt(n), where T(1) = 1, and n = 2^k
T(n) = 2[2T(n/4) + sqrt(n/2)] + sqrt(n) = 2^2T(n/4) + 2sqrt(n/2) + sqrt(n)
T(n) = 2^2[2T(n/8) + sqrt(n/4)] + 2sqrt(n/2) + sqrt(n)
= 2^3T(n/8) + 2^2sqrt(n/4) + 2sqrt(n/2) + sqrt(n)
通常
T(n) = 2^kT(1) + 2^(k-1) x sqrt(2^1) + 2^(k-2) x sqrt(2^2) + ... + 2^1 x sqrt(2^(k-1)) + sqrt(2^k)
到目前为止正确吗?如果是这样,我想不出如何简化它并将其简化为通用公式。
Is this right so far? If it is, I can not figure out how to simplify it and reduce it down to a general formula.
我猜是这样的吗?组合条件
I'm guessing something like this? Combining the terms
= 1 + 2^(k-(1/2)) + 2^(k-(2/2)) + 2^(k-(3/2)) + ... + 2^((k-1)/2) + 2^(k/2)
这就是我遇到的问题。也许可以排除2 ^ k?
任何帮助都将非常有用,谢谢!
And this is where I'm stuck. Maybe a way to factor out a 2^k? Any help would be great, thanks!
推荐答案
您已经到了一半。
表达式可以简化为:
You're half way there. The expression can be simplified to this:
这篇关于求解递归T(n)= 2T(n / 2)+ sqrt(n)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文