合併排序法的時間與空間複雜度

時間複雜度

分割（divide）

數列長度為n，在第k次分割資料量為多少？每次分割資料量都減少一半

1. 第1次分割，資料量n/2

2. 第2次分割，資料量n/4

3. ...

4. 第k次分割，資料量n/2^k=1

上述資料分割成一個遞迴樹結構。

n/2^k=1 => n=2^k => logn=k

所以進行k次分割就是logn

合併（conquer）

遞迴樹的每層合併都要遍歷所有元素，時間複雜度O(n)

合併排序法的總時間複雜度

分割階段需進行logn次分割，每次分割都需要O(n)時間來做合併。故總時間複雜度為O(logn)* O(n)= O(nlogn)

空間複雜度

額外空間

在遞迴樹中的每層合併操作都需要O(n)空間來存合併結果。

遞迴空間

合併排序遞迴深度為logn，所以會有O(logn）層函數呼叫。

故總空間複雜度為O(n)