算法~n=1时T(n)=O(1) ; n>1 时 T(n)=2*T(n/2)+O(n) ; 所以T(n) = O(nlgn)怎么做出来的?

算法~n=1时T(n)=O(1) ; n>1 时 T(n)=2*T(n/2)+O(n) ; 所以T(n) = O(nlgn)怎么做出来的?
算法~n=1时T(n)=O(1) ; n>1 时 T(n)=2*T(n/2)+O(n) ; 所以T(n) = O(nlgn)怎么做出来的?

算法~n=1时T(n)=O(1) ; n>1 时 T(n)=2*T(n/2)+O(n) ; 所以T(n) = O(nlgn)怎么做出来的?
为方便计算,假设 n = 2^k,因此：
T(n) = 2T(n / 2) + O(n)
= (4T(n / 4) + 2O(n/2)) + O(n)
= ((8T(n / 8) + 4O(n/4)) + O(n)) + O(n)
=…
= 2^kT(1) + O(n) + … + O(n) + O(n) + O(n)
= nO(1) + k * O(n) = (k + 1)O(n) = O(n * log2n)
所有对数的时间复杂度相等