大綱:
合併排序merge sort:
原理
圖解
時間複雜度:
證明
marge sort原理:
- 陣列分半直到陣列剩一個單位
- 每一次合併時時都排序一次
陣列分半
未排序的陣列
將陣列分半至一單位
合併時開始排序
每次兩組做比較大小並且排序
比較方式為兩組各產生1個茅點,比對兩茅點做大小排序。這裡用顏色表示茅點=>紅色為左邊組茅點,黃色為右邊組茅點
第一輪
第一次所有陣列都只有一個元素,故每兩個一組做比較,合併成一組。
第二輪
當兩陣列內大於1個元素時的排序會是下圖的樣子(其實只有一個元素也是一樣的排法XD)
之後作法以此類推,最後得出
整個merge sort流程:
證明時間複雜度
merge sort時間複雜度為O(N logN)
merge sort複雜度計算分成兩部分計算
- 分半時
- 合併時
分半時 O(N)
#有分解行為才算一次
#(8)表示陣列中有8個元素假設8元素拆分
(8)
拆一次
(4)(4)
拆兩次
(2)(2)(2)(2)
拆四次
(1)(1)(1)(1)(1)(1)(1)(1)(1)
總共7次7個元素陣列
(7)
拆一次
(4)(3)
拆兩次
(2)(2)(2)(1)
拆四次
(1)(1)(1)(1)(1)(1)(1)
總共七次所以可以拆解的時間複雜為
偶數 O(N-1)
奇數 O(N)
但BigO不計算常數,故O(N)
合併時O(N logN)
在合併n個元素時,每一次都會迭代n個元素,原因是因為需要比大小。
所以總時間就會是N*logNlogN意義:logN表示當陣列有N個元素,每一層折半,會有幾層。以下圖為例 層數就是當8個元素每一層都折半的話會得到幾層(log8),答案是3層。
總次數會是8*3=24次。所以合併的複雜度為O(N logN)
總時間複雜度加總為O(N)+O(N logN),
BigO降低非優勢條件,忽略O(N)得O(N logN)。