先锋
2018年10月13日
一次归并操作的时间复杂度是O(n)
对n个元素进行排序的时间：
T(n) = 2*T(n/2) + a*n (a是常数）
= 2*(2*T(n/4)+a*n/2)+a*n
= 4*T(n/4)+2a*n
= 4*(2*T(n/8)+a*n/4)+2*a*n
= 8*T(n/8)+3*a*n
...
= 2k *T(n/2k)+k*a*n
直到 n/2k = 1 (此时 k = log2n)，
T(n)= 2k *T(1)+k*a*n = 2k *T(1)+k*a*n = 2k+k*a*n
= n+a*(log2n)*n
复杂度O(nlogn)
0
0