分治的經典問題

經典例題 : 合併排序法 (Merge Sort)

#

要用分治的概念來實作合併排序法，總共會經歷三大步驟

• 1 切割問題
• 2 遞迴每個小問題
• 3 合併這些小問題的答案

切割問題

#

首先，我們每次都將一個陣列分成兩半，一直到不能再分割為止，這個操作的複雜度為 \(O(logn)\)。

遞迴每個小問題

#

切割後的陣列會透過遞迴的方式個別去操作

合併小問題的答案

#

如何將兩個排序好的陣列透過複雜度較好的方式合併呢?
我們可以先開一個空的陣列，並且重複將兩個原陣列中較小的數字拿出來放進新陣列中，這樣就可以透過 \(O(n)\) 的時間複雜度達到合併的效果，並且合併所有的小陣列需要 \(O(logn)\) 的操作次數，因此總時間複雜度為 \(O(nlogn)\) 。

程式碼流程

#

MergeSort(A, left, right) {
    if (left > right) { 
        return;
    }
    mid = (left + right) / 2;
    mergeSort(A, left, mid);
    mergeSort(A, mid + 1, right);
    merge(A, left, mid, right);
}