递归的复杂度 T(n)=T(n/2)+T(n/2)+n^2？
Complexity of the recurrence T(n)=T(n/2)+T(n/2)+n^2?
根据Master Theorem，这个递归是θ(n^2)，但是如果我们用树递归来解决这个问题，那么解就是θ(n^2*logn)。我做错了什么吗？
如果递归关系是T(n) = 2T(n/2) + n^2，那么你就是主定理的第三种情况，正则性条件适用，所以T( n) = Theta(n^2)。 [c_crit 是 log_2(2) = 1，n^2 = Omega(n)，2(n/2)^2 = (n^2)/2（所以 k<1 , 特别是 k=1/2)]
如果手工展开递归关系，则得到：
T(n) = n^2 + 2(n/2)^2 + 4(n/4)^2 + 8(n/8)^2 + ...
= n^2 ( 1 + 1/2 + 1/4 + 1/8 + ...)
<= 2n^2
所以这个方法也给你 T(n) = Theta(n^2).
inputting the recurrence relation into Wolfram Alpha and seeing what it says的方法给出了T(n) ~ 2n^2，所以又是Theta(n^2)。
根据Master Theorem，这个递归是θ(n^2)，但是如果我们用树递归来解决这个问题，那么解就是θ(n^2*logn)。我做错了什么吗？
如果递归关系是T(n) = 2T(n/2) + n^2，那么你就是主定理的第三种情况，正则性条件适用，所以T( n) = Theta(n^2)。 [c_crit 是 log_2(2) = 1，n^2 = Omega(n)，2(n/2)^2 = (n^2)/2（所以 k<1 , 特别是 k=1/2)]
如果手工展开递归关系，则得到：
T(n) = n^2 + 2(n/2)^2 + 4(n/4)^2 + 8(n/8)^2 + ...
= n^2 ( 1 + 1/2 + 1/4 + 1/8 + ...)
<= 2n^2
所以这个方法也给你 T(n) = Theta(n^2).
inputting the recurrence relation into Wolfram Alpha and seeing what it says的方法给出了T(n) ~ 2n^2，所以又是Theta(n^2)。