algorithm - 如何从 T(n) = 2T(n/2) + O(n) 得到 O(nlogn)

Question

我想在O(n log(n))不使用主定理的情况下进行计算。

有谁知道O(n log(n))从递归公式计算的数学方法T(n) = 2T(n/2) + O(n)？

Answer 1

注意模式（简化一点，最好保留O(n)而不是n）：

T(n) = 2T(n/2) + n
     = 2(2T(n/4) + n/2) + n  = 4T(n/4) + n + n  = 4T(n/4) + 2n
     = 4(2T(n/8) + n/4) + 2n = 8T(n/8) + n + 2n = 8T(n/8) + 3n
     = 8(2T(n/16) + n/8)+ 3n = 8T(n/16)+ n + 3n = 16T(n/16) + 4n
     ...                                        = 32T(n/32) + 5n
     ...
                                                = n*T(1) + log2(n)*n
                                                = O(n*log2(n))

Answer 2

绘制递归树：

树的高度将为 log n

每个级别的成本将是常数倍 n

因此，总成本将为 O(nlogn)。http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/RecursionTree.htm

如果你愿意，你总是可以通过归纳来证明它。

Answer 3

对于仍在弄清楚如何绘制递归树的任何人：

图片：T(n) = 2T(n/2) + O(n) 算法的递归树

如下图绘制一棵树，我们可以看到每次我们除以 2 直到我们的叶子等于 1

n/2^k = 1 
2^k = n 
k= log(n)

上述陈述证明我们的树的深度为log(n)。

在每个级别上，我们都进行了花费 O(n) 的操作。

即使我们每次除以 2，我们仍然对这两个部分进行操作，因此我们在每个级别都有n次迭代。

由于我们执行它的次数等于我们的深度，因此产生的复杂度是O(nlog(n))。

另外，请查看此视频教程https://youtu.be/1K9ebQJosvo