我正在使用MIT课件和CLRS书《算法简介》进行学习。
我目前正在尝试解决重复问题(第107页)
如果我创建一个递归树，则会得到:
该树具有lg(n)级。因此，我认为复发应该是
但是，如果我使用主定理，我会得到
显然，这两者都不对。哪一个是正确的？我的推理哪里出错了？
最佳答案
第二个看起来正确。请注意，您的递归树看起来像
但是2(n/2)4≠n4，因为(n/2)4 = n4/16，所以2(n/2)4 = n4/8。实际上，如果算出数学，就会知道在i级别完成的工作是
因此我们得到(1 + 1/8 + 1/64 + 1/512 + ...)n4，可以证明小于2n4。因此您的函数是Θ(n4)。