分而治之和貪婪演算法一樣, 也是一種演算法基本策略. 在使用了分而治之演算法的問題中, 我們通常通過遞迴來解決問題, 因為分而治之的思想本質上就是遞迴思想. 對於某一些問題, 我們通常採用這樣的策略 :

  • 將大問題分解為若干個小問題, 但是問題本質不變
  • 逐個地解決這些小問題, 若且唯若小問題的規模足夠小; 如果小問題的規模還沒有小到一定程度, 那麼我們再次使用第一步的策略繼續細分
  • 將小問題的解合併為大問題的解, 從而得到問題的解

上面所說的策略, 實際上就是演算法分而治之的基本策略. 現在, 假如你是一個搬運工, 你需要將貨車上的十噸貨物搬入貨船, 運往別的國家. 我相信沒有一個人可以一次性搬走十噸的東西, 所以一般採取的策略就是分而治之. 一般來說, 這些貨物都是打包裝箱的, 所以我們一箱一箱地搬運就可以了. 這是最簡單的分而治之策略在生活中的運用, 但是這和最開始我們說的使用遞迴還是不太一樣. 這是因為我們人類是智能的生物, 我們憑藉直覺和經驗直接就可以知道一次要搬運多少貨物. 目前電腦科學中的人工智慧學科就是在模仿人類, 但是不論怎樣, 電腦都不可能擁有人的智慧. 因此電腦目前只能按照人類給定的步驟來解決問題, 這也就是我們之前所提到的確定性圖靈機器. 如果要讓電腦搬運貨物, 我們會給出怎樣的策略呢? 首先計算貨物的總大小, 檢查貨物是否超過了目前搬運的最大承受範圍, 如果沒有, 那麼直接搬運; 否則, 將貨物一分為二, 接著查看一分為二之後的貨物是否超過了目前搬運的最大承受範圍... 這在電腦科學中, 就是非常明顯的遞迴了

其實, 在二分搜尋中, 我們已經使用了這個策略. 當時, 我們是使用迴圈來實作的, 因為任何遞迴都可以更改為迴圈, 任何迴圈也都可以更改為遞迴. 如果使用遞迴來實作二分搜尋, 那麼它的基本思想是 : 首先檢查給定的搜尋範圍, 如果沒有元素, 那麼直接回傳一個代表搜尋失敗的值. 接著, 當給定範圍中的元素數量有且唯有一個的時候, 那麼直接檢查這個元素是否就是我們搜尋的元素. 當給定的範圍中的元素數量多於一個, 那麼將序列一分為二, 檢查中間元素是否剛好為我們需要尋找的元素, 如果不是, 就在左側或者右側中搜尋. 在序列的左側或者右側中搜尋, 實際上就是給定左側和右側的範圍, 那麼我們只需要將範圍縮小就可以了. 這裡, 就體現了將大問題分解為小問題的思想. 將上述描述編寫為程式碼為 :

int *binary_search(int *begin, int *end, int value) {
    if(begin == end) {
        return nullptr;
    }
    if(end - begin == 1) {
        return *begin == value ? begin : nullptr;
    }
    auto mid {(end - begin) / 2};
    if(begin[mid] == value) {
        return begin + mid;
    }
    return begin[mid] > value ? binary_search(begin, begin + mid, value) : binary_search(begin + (mid + 1), end, value);
}

現在, 讓我們來考慮一些實例

例 1. [假幣問題] 一個袋子裡有 2^{n} 枚硬幣, 這些硬幣中有一枚是假幣. 現在已經知道假幣的重量要比真幣輕一些, 給定一台可用來比較重量的儀器, 找出這一枚假幣

例 2. [金塊問題] 一個老闆有一袋子金塊. 每個月有兩名僱員會因為優異表現分別獲得一個金塊獎勵, 排名第一的員工會得到最重的金塊, 排名第二的員工會得到最輕的金塊. 由於定期會有金塊加入到袋子中, 所以每個月都必須找出最重和最輕的金塊. 現在給定一台可以用來比較重量的儀器, 我們希望使用最少的次數找到最重和最輕的金塊

上面兩個問題給定的儀器並不能測定物品的重量, 而是比較物品的重量, 所以我們並不能通過測量重量數值進行比較. 因此, 我們通常使用分而治之的策略, 將問題的規模不斷細分. 在上面這兩個問題中, 我們可以將硬幣和金塊不斷細分. 在假幣問題中, 首先一分為二, 每一堆中都有 2^{n - 1} 枚硬幣, 輕一點的那一堆必定有假幣. 不斷地使用這個方法就可以了得到假幣. 在金塊問題中, 我們將金塊無限細分, 直到每一堆中有且唯有兩個或者一個金塊為止, 然後進行比較, 選出較大的那一塊放入最大的候選集合中, 選出最小的那一塊放入最小的候選集合中. 針對兩個最大最小候選集合, 採用同樣的方法, 最終候選集合中剩下的那一個金塊就是最大或者最小的金塊

對於分而治之演算法, 我們可以總結出以下步驟 :

  1. 對於一個問題, 我們將其進行細分為兩個或者兩個以上更小的子問題. 這些子問題除了要有原來問題的性質, 電腦還應該可以在 \Theta(1) 的時間內解決它
  2. 把這些子問題的解進行合併, 得到原問題的解

在步驟 1 中, 我們提到了電腦需要在 \Theta(1) 的時間內解決子問題, 這是使用分而治之演算法的其中一個核心. 考慮假幣問題和金塊問題, 在解決的途中, 最終的那個比較都是可以在 \Theta(1) 內完成的. 另外, 合併之後的解還是否為原問題的解, 這也是能否使用分而治之演算法的另一個核心. 如果這兩個條件都可以得到滿足, 那麼我們就可以採用分而治之演算法來解決問題

例 3. [殘缺棋盤覆蓋問題] 設有一個 2^{k} \times 2^{k} 個方格的棋盤, 但是這個棋盤中有一個方格是殘缺的. 當 k = 0 時, 棋盤中有且唯有一個方格, 那麼整個棋盤都是殘缺的. 當 k > 0 時, 棋盤中共有 2^{2k} 個方格, 那麼總共有 2^{2k} 種可能的殘缺棋盤. 如果我們使用灰色部分表示殘缺的棋盤, 那麼當 k = 0 時, 有

k = 1 時, 有

我們希望使用三格板覆蓋整個殘缺棋盤. 在覆蓋的過程中, 任意兩個三格板不能出現交疊, 任意三格板不能覆蓋殘缺的格子且必須覆蓋除殘缺格子之外所有的方格. 當 k = 0 時, 由於棋盤有且唯有一個方格, 因此它並不需要覆蓋; 當 k = 1 時, 我們可以使用下面四種三格板進行覆蓋 :

k > 1 時, 我們使用若干個上述四種三格板進行覆蓋. 下面是當 k = 2 時的一種殘缺情況 :

我們可以使用這樣的方式進行覆蓋 :

從全域來看, 我們很難決定某一個位置應該使用什麼樣的三個板, 但是使用分而治之的方法, 我們可以從局域開始選擇三格板, 逐漸擴散到全域, 使得將整個棋盤覆蓋. 要劃分一個 2^{k} \times 2^{k} 的棋盤, 我們自然可以想到將這個棋盤劃分為 4 個 2^{k - 1} \times 2^{k - 1} 的棋盤. 對於那個殘缺的格子, 它必定位於 4 個子棋盤中的其中一個. 對於剩下三個完整的子棋盤, 我們需要使用三格板進行覆蓋 :

這樣我們就得到了四個殘缺的子棋盤. 然後針對四個四個子棋盤, 我們再次運用相同的策略, 最終就可以將整個棋盤覆蓋. 那麼如何分析上述使用了分而治之策略的演算法的時間複雜度呢?

當一個演算法包含對其自身的遞迴呼叫時, 我們往往可以通過遞迴方程式來描述其運作時間. 令 T(n) 為一個使用了分而治之演算法的程式運作時間, 當問題的規模足夠小的時候, 例如對於某一個常數 c, 當 n \leq c 時, 其運作時間可以在常數時間內完成. 此時, 其時間複雜度可以使用 \Theta(1) 來表示; 當問題規模擴大, 以至於 n > c, 使用分而治之演算法將問題分解為 a 個子問題, 每一個子問題的規模都是原問題的 \frac {1}{b}. 為了求解一個規模為 \frac {n}{b} 的子問題, 需要 T(\frac {n}{b}) 的時間. 那麼, 總共需要 a \cdot T(\frac {n}{b}) 的時間來求解 a 個子問題. 若分解一個問題或者子問題的時間為 D(n), 合併子問題的解為原問題的解的時間為 C(n), 則可以得到 T(n) 的遞迴方程式 :

T(n)=\begin{cases} \Theta(1) & {n \leq c} \\ aT(\frac {n}{b}) + D(n) + C(n) & {n > c} \end{cases}

其中, n 是問題的規模

在殘缺棋盤覆蓋問題中, 當 k > 1 時, 我們將棋盤分為四個子棋盤. 在子棋盤中, 問題規模從覆蓋一個 2^{k} \times 2^{k} 的殘缺棋盤變成了覆蓋一個 2^{k - 1} \times 2^{k - 1} 的殘缺棋盤, 那麼需要 T(k - 1) 的時間. 我們總共需要處理四個子棋盤, 總的時間為 4T(k - 1). 將一個規模為 2^{k} \times 2^{k} 細分為 4 個 2^{k - 1} \times 2^{k - 1} 的子棋盤, 實際上是四次函式呼叫. 對於 k > 1, 總共需要 4^{k - 1} 次函式呼叫, 因此 D(k) = O(4^{k - 1}). 其中, D(k) 還包含了其它有關的處理需要的時間. 準確地來說, D(k) = 4^{k - 1} + c. 其中, c 為常數. 在所有子棋盤覆蓋完成之後, 並不需要進行合併, 棋盤就已經覆蓋完成了, 所以 C(k) = 0. 故使用分而治之演算法解決殘缺棋盤覆蓋問題的時間複雜度為 :

T(k)=\begin{cases} \Theta(1) & {k \leq 1} \\ 4T(k - 1) + 4^{k - 1} + c & {k > 1} \end{cases}

我們無法直接從遞迴方程式中得到問題時間複雜度的漸近記法表示, 因為我們需要求解這個遞迴方程式. 遞迴方程式的求解我將在下一篇關於分而治之的文章中進行講解. 求解遞迴方程式 T(k) 可以得到使用了分而治之演算法求解殘缺棋盤覆蓋問題的時間複雜度為 T(k) = \Theta(4^{k})