C++分治算法

「分治 divide and conquer」，全稱分而治之，是一種非常重要且常見的算法策略。分治通?；谶f歸實(shí)現(xiàn)，包括“分”和“治”兩個(gè)步驟。

1. 分（劃分階段）：遞歸地將原問題分解為兩個(gè)或多個(gè)子問題，直至到達(dá)最小子問題時(shí)終止。
2. 治（合并階段）：從已知解的最小子問題開始，從底至頂?shù)貙⒆訂栴}的解進(jìn)行合并，從而構(gòu)建出原問題的解。

如圖 12-1 所示，“歸并排序”是分治策略的典型應(yīng)用之一。

1. 分：遞歸地將原數(shù)組（原問題）劃分為兩個(gè)子數(shù)組（子問題），直到子數(shù)組只剩一個(gè)元素（最小子問題）。
2. 治：從底至頂?shù)貙⒂行虻淖訑?shù)組（子問題的解）進(jìn)行合并，從而得到有序的原數(shù)組（原問題的解）。

圖 12-1   歸并排序的分治策略

如何判斷分治問題

一個(gè)問題是否適合使用分治解決，通常可以參考以下幾個(gè)判斷依據(jù)。

1. 問題可以被分解：原問題可以被分解成規(guī)模更小、類似的子問題，以及能夠以相同方式遞歸地進(jìn)行劃分。
2. 子問題是獨(dú)立的：子問題之間是沒有重疊的，互相沒有依賴，可以被獨(dú)立解決。
3. 子問題的解可以被合并：原問題的解通過合并子問題的解得來。

顯然，歸并排序是滿足以上三條判斷依據(jù)的。

1. 問題可以被分解：遞歸地將數(shù)組（原問題）劃分為兩個(gè)子數(shù)組（子問題）。
2. 子問題是獨(dú)立的：每個(gè)子數(shù)組都可以獨(dú)立地進(jìn)行排序（子問題可以獨(dú)立進(jìn)行求解）。
3. 子問題的解可以被合并：兩個(gè)有序子數(shù)組（子問題的解）可以被合并為一個(gè)有序數(shù)組（原問題的解）。

通過分治提升效率

分治不僅可以有效地解決算法問題，往往還可以帶來算法效率的提升。在排序算法中，快速排序、歸并排序、堆排序相較于選擇、冒泡、插入排序更快，就是因?yàn)樗鼈儜?yīng)用了分治策略。

那么，我們不禁發(fā)問：為什么分治可以提升算法效率，其底層邏輯是什么？換句話說，將大問題分解為多個(gè)子問題、解決子問題、將子問題的解合并為原問題的解，這幾步的效率為什么比直接解決原問題的效率更高？這個(gè)問題可以從操作數(shù)量和并行計(jì)算兩方面來討論。

操作數(shù)量優(yōu)化

以“冒泡排序”為例，其處理一個(gè)長度為 $n$ 的數(shù)組需要 $O(n^2)$ 時(shí)間。假設(shè)我們按照?qǐng)D 12-2 所示的方式，將數(shù)組從中點(diǎn)分為兩個(gè)子數(shù)組，則劃分需要 $O(n)$ 時(shí)間，排序每個(gè)子數(shù)組需要 $O((n/2{)}^2)$ 時(shí)間，合并兩個(gè)子數(shù)組需要 $O(n)$ 時(shí)間，總體時(shí)間復(fù)雜度為：

圖 12-2   劃分?jǐn)?shù)組前后的冒泡排序

接下來，我們計(jì)算以下不等式，其左邊和右邊分別為劃分前和劃分后的操作總數(shù)：

這意味著當(dāng) $n>4$ 時(shí)，劃分后的操作數(shù)量更少，排序效率應(yīng)該更高。請(qǐng)注意，劃分后的時(shí)間復(fù)雜度仍然是平方階 $O(n^2)$ ，只是復(fù)雜度中的常數(shù)項(xiàng)變小了。

進(jìn)一步想，如果我們把子數(shù)組不斷地再從中點(diǎn)劃分為兩個(gè)子數(shù)組，直至子數(shù)組只剩一個(gè)元素時(shí)停止劃分呢？這種思路實(shí)際上就是“歸并排序”，時(shí)間復(fù)雜度為 $O(n\log ?n)$ 。

再思考，如果我們多設(shè)置幾個(gè)劃分點(diǎn)，將原數(shù)組平均劃分為 $k$ 個(gè)子數(shù)組呢？這種情況與“桶排序”非常類似，它非常適合排序海量數(shù)據(jù)，理論上時(shí)間復(fù)雜度可以達(dá)到 $O(n+k)$ 。

2.   并行計(jì)算優(yōu)化?

我們知道，分治生成的子問題是相互獨(dú)立的，因此通?？梢圆⑿薪鉀Q。也就是說，分治不僅可以降低算法的時(shí)間復(fù)雜度，還有利于操作系統(tǒng)的并行優(yōu)化。

并行優(yōu)化在多核或多處理器的環(huán)境中尤其有效，因?yàn)橄到y(tǒng)可以同時(shí)處理多個(gè)子問題，更加充分地利用計(jì)算資源，從而顯著減少總體的運(yùn)行時(shí)間。

比如在圖 12-3 所示的“桶排序”中，我們將海量的數(shù)據(jù)平均分配到各個(gè)桶中，則可所有桶的排序任務(wù)分散到各個(gè)計(jì)算單元，完成后再進(jìn)行結(jié)果合并。

圖 12-3   桶排序的并行計(jì)算

分治常見應(yīng)用

一方面，分治可以用來解決許多經(jīng)典算法問題。

• 尋找最近點(diǎn)對(duì)：該算法首先將點(diǎn)集分成兩部分，然后分別找出兩部分中的最近點(diǎn)對(duì)，最后再找出跨越兩部分的最近點(diǎn)對(duì)。
• 大整數(shù)乘法：例如 Karatsuba 算法，它是將大整數(shù)乘法分解為幾個(gè)較小的整數(shù)的乘法和加法。
• 矩陣乘法：例如 Strassen 算法，它是將大矩陣乘法分解為多個(gè)小矩陣的乘法和加法。
• 漢諾塔問題：漢諾塔問題可以視為典型的分治策略，通過遞歸解決。
• 求解逆序?qū)?/strong>：在一個(gè)序列中，如果前面的數(shù)字大于后面的數(shù)字，那么這兩個(gè)數(shù)字構(gòu)成一個(gè)逆序?qū)?。求解逆序?qū)栴}可以通過分治的思想，借助歸并排序進(jìn)行求解。