huh*_*rto 5 algorithm math big-o recurrence big-theta
我正在学习使用麻省理工学院课件和CLRS书籍算法入门.
我目前正在尝试解决重复问题(来自第107页)
T(n)= 2T(n/2)+ n 4
如果我制作一个重复树,我得到:
0级:n 4
1级2(n/2)4
2级4(n/4)4
3级8(n/8)4
树有lg(n)级.因此,我认为应该再次发生
T(n)=Θ(n 4 lg n)
但是,如果我使用主定理,我就明白了
T(n)=Θ(n 4)
显然这两者都不对.哪一个是正确的？我的推理在哪里出错了？
第二个看起来是正确的.请注意,您的重复树看起来像
n 4 + 2(n/2)4 + 4(n/4)4 + ... + 2 i(n/2 i)4
但2(N/2)4 ≠N 4,因为第(n/2)4 = N 4 /16,和SO 2(N/2)4 = N 4 /8 事实上,如果你计算出数学,你会得到在第一级完成的工作
n 4 /(2 -3i)
所以我们得到(1 + 1/8 + 1/64 + 1/512 + ...)n 4,可以显示小于2n 4.所以你的函数是Θ(n 4).