我只需要使用迭代方法找到这种递归的复杂性:
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 …