首页 > 代码库 > 合并排序算法时间复杂度分析
合并排序算法时间复杂度分析
一、合并已排序的两个数组,依次比较两个数组元素大小,并按大小加入到暂存数组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。