首页 > 代码库 > 合并排序算法时间复杂度分析

合并排序算法时间复杂度分析

一、合并已排序的两个数组,依次比较两个数组元素大小,并按大小加入到暂存数组B,最后保存到A:

Algorithm: MERGE(A, p, q, r)

输入:数组A[p...q]和A[q+1...r],各自按升序排列

输出:将A[p...q]和A[q+1...r]合并后的升序排序的新数组

01. s←p; t←q+1; k←p; {s, t, p 分别指向A[p...q], A[q+1...r]和暂存数组B}

02. while s≤q and t≤r

03.   if A[s] ≤A[t] then

04.     B[k]←A[s]

05.     s ←s+1

06.   else

07.     B[k]←A[t]

08.     t←t+1

09.   end if

10.   k←k+1

11.end while

12. if s=q+1 then B[k...r] ←A[t...r]

13. else B[k...r] ←A[s...q]

14. end if

15. A[p...r] ←B[p...r]

 

二、对数组进行排序(分治策略):

Algorithm: MERGESORT(A[low…high])

输入:待排序数组A[low,...high]

输出:A[low…high]按非降序排列

01. if low<high then

02.   mid←[(low+high)/2]

03.   MERGESORT(A, low, mid)

04.   MERGESORT(A, mid+1, high)

05.   MERGE(A, low, mid, high)

06. end if

 

三、时间复杂度分析:

1. 最小比较次数:

  n = 1时,C(n) = 0;

  n >= 2时,C(n) = 2C(n/2) + n/2,理想情况下,MERGE算法进行比较次数,最少为与子数组长度相等。此时其中一个子数组先全部依次进入暂存数组B,然后另一个子数组直接全部加入B。

结果:C(n) = (nlogn)/2

2. 最大比较次数:

  n = 1时,C(n) = 0;

  n>= 2时,C(n) = 2C(n/2) + n-1,理想情况下,MERGE算法进行比较次数,最大为总长度 - 1。此时两个子数组的元素轮流加入暂存数组B,因此共比较n - 1次。

结果:C(n) = nlogn - n + 1

综合1和2得,合并排序算法时间复杂度为T(n) = nlogn。