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

Question

嗨,我正在研究算法,我得到一个关于得到O(nlogn)而不使用主定理的问题.

我很难得到O(nlogn)..

有没有人知道从T(n)= 2T(n/2)+ O(n)得到O(nlogn)的数学方法？

谢谢

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

如果需要，您总是可以通过归纳证明。