complexity-theory - 重复复杂度

Question

求紧渐近界：

如果 n = 1，则 T(n) = 1

2T(n/4) + T(n/2) + n ²如果 n > 1

我尝试绘制递归树。第一行我有 n ²，第二行我有 (3/8)(n ⁴ )，第三行我有 (27/1024)(n ⁸ ).. 不知道如何从那里继续。提前致谢。

Answer 1

我认为主定理可以应用于这个问题。它比递归树更容易理解。

将递推公式写成另一种形式。添加T(n/2)到左侧和右侧。

T(n) + T(n/2) = + 2T(n/4) + 2T(n/2) + n ²

T(n) + T(n/2) = + 2[ T(n/4) + T(n/2) ] + n ²

定义G(n) = T(n) + T(n/2)，然后

G(1) = Θ(1)

G(n) = 2G(n/2) + n ²，如果 n > 1

将主定理应用于上述新的递推公式

G(n) = Θ(n ² )

那是

T(n) + T(n/2) = Θ(n ² )

对于 n > 1

T(n) = 2 * T(n/4) + T(n/2) + n ²

= T(n/4) + [ T(n/2) + T(n/4) ] + n ²

= T(n/4) + Θ(n2/4) + n2

= T(n/4) + Θ(n2)

将主定理应用于上述新的递推公式

T(n) = Θ(n2)