學習筆記-合併排序法(merge sort)

此筆記是想要探討合併排序的BigO時間複雜度。

大綱：

合併排序merge sort：

原理

圖解

時間複雜度：

證明

marge sort原理：

1. 陣列分半直到陣列剩一個單位
2. 每一次合併時時都排序一次

陣列分半

未排序的陣列

將陣列分半至一單位

合併時開始排序

每次兩組做比較大小並且排序

比較方式為兩組各產生1個茅點，比對兩茅點做大小排序。
這裡用顏色表示茅點=>紅色為左邊組茅點，黃色為右邊組茅點

第一輪

第一次所有陣列都只有一個元素，故每兩個一組做比較，合併成一組。

第二輪

當兩陣列內大於1個元素時的排序會是下圖的樣子(其實只有一個元素也是一樣的排法ＸＤ)

之後作法以此類推，最後得出

整個merge sort流程：

證明時間複雜度

merge sort時間複雜度為O(N logN)

merge sort複雜度計算分成兩部分計算

1. 分半時
2. 合併時

分半時 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*logN
logN意義：logＮ表示當陣列有N個元素，每一層折半，會有幾層。
以下圖為例 層數就是當8個元素每一層都折半的話會得到幾層(log8)，答案是3層。
總次數會是8*3=24次。所以合併的複雜度為O(N logN)

總時間複雜度加總為O(N)+O(N logN)，

BigO降低非優勢條件，忽略O(N)得O(N logN)。