algorithm - 使用迭代法求复杂度 T(n) = 4T(n/2) + (n^2)*logn

Question

我只需要使用迭代方法找出这个递归的复杂度:

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

我知道你可以使用 master 方法解决这个问题，复杂度是 (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)))

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

Answer 1

如果你仔细展开递归，你会得到: .

现在复杂的和变成了

当 n/2^k = 1 或 k = log(n) 时，此递归将自行耗尽。将其代回您得到的等式:

，其中 c = T(1)。

所以一切都由 n^2 log^2(n) 支配，这就是递归的复杂性。

P.S.其实求和不需要近似，用初等数学很容易算出来。