algorithm - 解决涉及 Theta 符号的时间复杂度的重复出现

Question

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

如何解决这种复发？我不能在这里使用 Master 定理。

Answer 1

不使用 Master 定理，只需简单地继续扩展递推关系，直到您看到一个模式。

T(n) = 4T(n/2) + Θ(n^2 /log(n))
= 4*(4t(n/4) + theta((n/2)^2 / log(n/2))) + theta(n^2/log(n)) 
= 4^2 * (t(n/4) + theta((n/2)^2 / log(n/2)) / 4) + theta(n^2/log(n)) 
theta((n/2)^2 / log(n/2)) / 4 can be simplified to theta(n^2/log(n))
= 4^2 * (t(n/4)) + 2theta(n^2/log(n)) 
= 4^2 * (4t(n/8) + theta((n/4)^2 / log(n/4))) + 2theta(n^2/log(n)) 
= 4^3 * (t(n/8) + theta((n/4)^2 / log(n/4)) / 4) + 2theta(n^2/log(n)) 
theta((n/4)^2 / log(n/4)) / 4 can be simplified to theta(n^2/log(n))
= 4^3 * (t(n/8)) + 3theta(n^2/log(n)) 

所以我们可以进一步简化为

4^k * (t(n/k)) + k*theta(n^2/log(n)) 

这将一直持续到 k = n，假设 T(1) = 1，我们得到

4^n + n*theta(n^2/log(n))

因为 4^n 大于 n*theta(n^2/log(n))，所以答案是 O(4^n)。