小编huh*_*rto的帖子

我正在学习使用麻省理工学院课件和CLRS书籍算法入门.

我目前正在尝试解决重复问题(来自第107页)

T(n)= 2T(n/2)+ n ⁴

如果我制作一个重复树,我得到:

0级:n ⁴

1级2(n/2)⁴

2级4(n/4)⁴

3级8(n/8)⁴

树有lg(n)级.因此,我认为应该再次发生

T(n)=Θ(n ⁴ lg n)

但是,如果我使用主定理,我就明白了

T(n)=Θ(n ⁴)

显然这两者都不对.哪一个是正确的？我的推理在哪里出错了？