查找复杂T（N）= 4T（N/2）+（N^2）*使用迭代方法

Question

我需要仅使用迭代方法来发现此递归的复杂性LOGN：

T(n) = 4T(n/2) + (n^2)*logn 

我知道，你可以使用主方法解决这个问题和复杂性是(n^2)(logn)^2，但我尝试使用迭代方法解决它，我有别的东西：

T(n) = 4 * T(n/2) + (n^2) * log(n) 
T(n/2) = 4 * T (n/4) + ((n/2)^2) * log(n/2) 
T(n/4) = 4 * T(n/8) + ((n/4)^2) * log(n/4) 

T(n) = 4 * (4 * (4 * T(n/8) + (n/4)^2 * log(n/4)) + (n/2)^2 * log(n/2)) + (n^2) * log(n) 

T(n) = 64T(n/8) + 16((n/4)^2) * log(n/4) + 4((n/2)^2) * log(n/2) + (n^2)log(n) 

T(n) = (4^i) * T(n/(2^i)) + 4^(i-1) * (n/(2^(i-1)))^2 * log(n/(2^(i-1))) 

使用我以后= LOGN我得到，该算法复杂度为2^n ..这是不正确的。

Answer 1

如果您仔细放开递归，您将得到：。

现在复杂的总和为

时，此递归会用尽自己n/2^k = 1或k = log(n)。将其代入方程式中：

，其中c = T(1)。

所以一切都以n^2 log^2(n)为主，这是递归的复杂性。

P.S.实际上不需要近似于和，很容易用初等数学来计算它。