Question

算法~n=1时T(n)=O(1) ; n>1 时 T(n)=2*T(n/2)+O(n) ; 所以T(n) = O(nlg

Answer 1

为方便计算,假设 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)

所有对数的时间复杂度相等