递归T(n)= 2T(n/2)+(n-1) [英] The Recurrence T(n)= 2T(n/2) + (n-1)

问题描述

我有这种复发:

T(n)= 2T(n/2) + (n-1)

我的尝试如下:

树是这样的:

T(n) = 2T(n/2) + (n-1)
T(n/2) = 2T(n/4) + ((n/2)-1)
T(n/4) = 2T(n/8) + ((n/4)-1) 
...

• 树的最高点:(n/(2 ^h ))-1 = 1⇒h = lg n-1 = lg n-lg 2
• 最后一级的费用:2 ^h = 2 ^{lg n-lg 2} =(1/2)n
• 直到h-1级的所有级别的成本:Σ _{i = 0，...，lg(2n)} n-(2 ⁱ -1)，这是一个几何级数，等于(1/2)((1/2)n-1)
• the hight of the tree : (n/(2^h))-1 = 1 ⇒ h = lg n - 1 = lg n - lg 2
• the cost of the last level : 2^h = 2^{lg n - lg 2} = (1/2) n
• the cost of all levels until level h-1 : Σ_{i=0,...,lg(2n)} n - (2ⁱ-1), which is a geometric series and equals (1/2)((1/2)n-1)

所以，T(n)=Θ(n lg n)

So, T(n) = Θ(n lg n)

我的问题是:是吗?

推荐答案

不，不是.您最后一级的成本是错误的，因此从中得出的结果也是错误的.

No, it isn't. You have the cost of the last level wrong, so what you derived from that is also wrong.

(我假设您想自己找到复杂性，因此除非您询问，否则不再提示.)

(I'm assuming you want to find the complexity yourself, so no more hints unless you ask.)

根据要求提供一些提示

要找到复杂度，一种通常有用的方法是递归应用等式并将结果插入第一个，

To find the complexity, one usually helpful method is to recursively apply the equation and insert the result into the first,

T(n) = 2*T(n/2) + (n-1)
     = 2*(2*T(n/4) + (n/2-1)) + (n-1)
     = 4*T(n/4) + (n-2) + (n-1)
     = 4*T(n/4) + 2*n - 3
     = 4*(2*T(n/8) + (n/4-1)) + 2*n - 3
     = ...

通常会得出一个封闭的公式，您可以通过归纳法来证明(如果您有足够的经验就不需要进行证明，那么您就可以查看正确性而无需写下证明)

That often leads to a closed formula you can prove via induction (you don't need to carry out the proof if you have enough experience, then you see the correctness without writing down the proof).

扰流器:您可以在处理主定理的几乎所有资源中查找其复杂性.

Spoiler: You can look up the complexity in almost any resource dealing with the Master Theorem.

这篇关于递归T(n)= 2T(n/2)+(n-1)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！