performance - 重复 W(n)= 2W(floor(n/2)) + 3

Question

我有这种复发:

W(n)= 2W(floor(n/2)) + 3
W(2)=2

我的尝试如下:

树是这样的:

W(n) = 2W(floor(n/2)) + 3
W(n/2) = 2W(floor(n/4)) + 3
W(n/4) = 2W(floor(n/8)) + 3 
...

• 树的高度:我假设它是 lgn，因为树在每个扩展过程中都有 2 个分支，但不确定 :S
• 最后一层的成本:2^lgn * W(2) = 2n
• 所有级别的成本，直到级别 h-1 : 3 * sigma 从 0 到 (2^i) 的 lgn-1，这是一个几何级数 = 3 (n-1)

所以，T(n) = 5n - 3 属于 Theta(n)

我的问题是:这样对吗？

Answer 1

我不认为它正好是 5n-3 除了 n 是 2^t，但是如果您查看 Master Theorem，您的 theta 是正确的，不需要计算(但对启动有好处):

假设你有:

T(n) = aT(n/b) + f(n)，其中 a>=1，b>1 那么:

1. 如果 f(n) = n^log_ba-eps 对于任何 eps > 0 则 T(n) = n^log_ba 就像你的情况，其中 a=b=2，f(n) = O(1)。
2. f(n) = Theta(n^log_ba * log^kn) 然后 T(n)=Theta(n< sup>log_ba * log^k+1n).
3. 否则为 Theta(f(n))。 (请参阅 CLRS 或 wiki 中的这种情况下的约束详细信息，...)

详情见维基。