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

Hi i am studying the algorithm and I get a question about get O(nlogn) without using master theorem.

大家好，我正在学习算法，我得到一个关于get O(nlogn)的问题，而不用使用主定理。

I am having trouble to get O(nlogn)..

我有麻烦了。

Does anyone know that mathematical ways to get O(nlogn) from the T(n) = 2T(n/2) + O(n) ?

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

thanks

谢谢

2 个解决方案

#1

Draw a recursion tree:

画一个递归树:

height of the tree will be log n

树的高度是log n。

cost at each level will come out to be constant times n

每一层的成本将会是常数乘以n。

Hence the total cost will be O(nlogn). http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/RecursionTree.htm

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

And you can always prove it by induction if you want.

你可以用归纳法证明它。

#2

Notice the pattern (simplified a bit, better would be to keep O(n) rather than n):

注意这个模式(简化一点，最好是保留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))

#1