算法原理

對于一個規模為 $n$ 的子問題，若該問題可以容易地解決則直接解決，否則將其分解為 $k$ 個規模較小的子問題，這些子問題相互獨立且與原問題形式相同。遞歸地解決這些子問題，然后將各子問題的解合并得到原問題的解，這種算法設計策略叫分治法。

分治法所能解決的問題一般具有以下特征：

• 該問題的規模縮小到一定的程度就可以容易地解決。
• 該問題可以分解為若干個規模較小的相似問題。
• 利用該問題分解出的子問題的解可以合并為該問題的解。
• 該問題所分解出的各子問題是相互獨立的，即子問題之間不包含公共的子問題。

分治法的一般算法設計如下：

SolutionType Solve(ProblemType P) {if(Small(P)) return Result(P);else {Divector<int>de(P，P1，P2，…，Pk);return Merge(Solve(P1), Solve(P2),..., Solve(Pk));}
}

其中 $Small(P)$ 用來判斷問題 $P$ 的規模是否已經足夠小，當問題 $P$ 的規模足夠小時，直接進行求解并返回結果 $Result(P)$，否則，將問題 $P$ 分解為若干子問題，并逐個進行求解，最后將所有子問題的解 $Ri$ 合并得到問題 $P$ 的解并返回。

冒泡排序的交換次數

題目描述

給定一個數列 $a$，求對這個數列進行冒泡排序所需要的交換次數（此處冒泡排序指每次找到滿足 $a_i>a_{i+1}$ 的 $i$，交換 $a_i$ 和 $a_{i+1}$，直到這樣的 $i$ 不存在為止的算法）。

輸入輸出

輸入：數列元素個數 $n$ 和 $n$ 個數列元素。

輸出：交換次數。

解題思路

求所需交換次數等價于求滿足 $i＜j$ 且 $a_i＞a_j$ 的 $(i,j)$ 數對的個數，也即求數列 $a$ 的逆序數。

假設要統計數列 $A$ 中逆序對的個數，為此，可以將數列 $A$ 分成兩半得到數列 $B$ 和數列 $C$，于是，對于數列 $A$ 中所有的逆序對 $(a_i,a_j)$，必然屬于以下情況之一：

• ① $(a_i,a_j)$屬于數列 $B$ 的逆序對；
• ② $(a_i,a_j)$ 屬于數列 $C$ 的逆序對；
• ③ $a_i$ 屬于數列 $B$ 而 $a_j$ 屬于數列 $C$。

對于情況①和②，可以通過遞歸求得。對于情況③，需要做的就是對于 $C$ 中的每一個元素，統計在數列 $B$ 中比它大的元素的個數，再把結果相加。最后再將③中情況所得結果相加，便得到數列 $A$ 的逆序數。

情況③進行統計時，如果采用普通方法，即使用兩個 $for$ 循環逐個比較，時間復雜度較高。因此，借鑒歸并排序的思想，在進行統計的同時邊將兩個子數列進行歸并，由遞歸的特性可知，進行歸并時，兩子數列也是有序的，如此，情況③統計只需掃描一遍數列。

代碼實現

typedef vector<int> vi;int main() {// 輸入int n;cin >> n;vi A(n);for (int i = 0; i < n; ++i)cin >> A[i];// 求解并輸出cout << solve(A);
}

/*** 求數列a的逆序數* @param a 數列* @return 	逆序數*/
int solve(vector<int> &a) {int n = a.size();// 數列元素個數小于等于1，逆序數為0if (n <= 1)return 0;// 二分vector<int> b(a.begin(), a.begin() + n / 2);vector<int> c(a.begin() + n / 2, a.end());// 情況1與情況2（子問題）int cnt = solve(b) + solve(c);// 情況3int ai = 0, bi = 0, ci = 0;while (ai < n) {if (bi < b.size() && (ci == c.size() || b[bi] <= c[ci])) {a[ai++] = b[bi++];} else {// b[bi..n/2-1] 都比 c[ci] 大cnt += n / 2 - bi;a[ai++] = c[ci++];}}// 返回合并所得解return cnt;
}

時間復雜度：$O(nlog(n))$。

空間復雜度：$O(nlog(n))$，歸并排序的空間復雜度實際可降至 $O(n)$。

最近點對問題

題目描述

給定平面上的 $n$ 個點，求距離最近的兩個點的距離。

輸入輸出

輸入：第一行輸入點的個數 $n$，第二行輸入 $n$ 個點的橫坐標 $x_i$，第三行輸入 $n$ 個點的縱坐標 $y_i$。

輸出：距離最近的兩個點的距離。

解題思路

將所有點按x坐標（按y坐標也可）分成左右兩半，那么最近點對的距離就是下面三者的最小值。

• ① $p$ 和 $q$ 同屬于左半邊時，點對 $(p,q)$ 距離的最小值；
• ② $p$ 和 $q$ 同屬于右半邊時，點對 $(p,q)$ 距離的最小值；
• ③ $p$ 和 $q$ 屬于不同區域時，點對 $(p,q)$ 距離的最小值。

對于情況①和②可以遞歸求解，情況③稍微復雜。假設情況①和②所求得的最小距離為 $d$，所以在情況③中便不需要考慮距離顯然大于等于 $d$ 的點對。

先考慮 $x$ 坐標。假設將點劃分為左右兩半的直線為 $l$，其 $x$ 坐標為 $x_0$，只需考慮那些到直線 $l$ 距離小于 $d$ 的點，也即 $x$ 坐標滿足 $x_0?d＜x＜x_0+d$ 的點。

再考慮 $y$ 坐標。對于每個點，只考慮那些 $y$ 坐標相差小于 $d$ 的點，同時，為了避免重復計算，規定只考慮與 $y$ 坐標不比自己大的點組成的點對。因此，對于每個點 $p$，只需要考慮與 $y$ 坐標滿足 $y_p?d＜y＜y_p$ 的點組成的點對。

為了將所有點按 $x$ 坐標分成左右兩半，需要先將所有點按 $x$ 坐標排序。為了避免重復考慮，在處理情況③前，需要將待考慮的點按 $y$ 坐標排序（由于分治法求解最近點對問題與歸并排序在結構上的相似性，此處借鑒歸并排序的思想）。

代碼實現

#define INF 1.79E+308
typedef pair<double, double> pdd;int main() {// 輸入int n;cin >> n;pdd *ps = new pdd[n];for (int i = 0; i < n; ++i)cin >> ps[i].first;for (int i = 0; i < n; ++i)cin >> ps[i].second;// 按x坐標排序sort(ps, ps + n, compX);// 求解并輸出最近點對的距離cout << solve(ps, n);
}

/*** 求最近點對的距離* @param ps 所有點* @param n 點的個數* @return 最近點對的距離*/
double solve(pdd *ps, int n) {if (n <= 1)return INF;// 中線int m = n >> 1;double x = ps[m].first;// 處理情況1和2，得到目前距離最小值ddouble d = min(solve(ps, m), solve(ps + m, n - m));// 按y坐標從小到大進行排序（歸并排序）inplace_merge(ps, ps + m, ps + n, compY);// 處理情況3vector<pdd> pl;for (int i = 0; i < n; ++i) {// 排除到直線l的距離大于等于d的點if (fabs(ps[i].first - x) >= d)continue;// 從后往前檢查b中y坐標相差小于d的點for (int j = pl.size() - 1; j >= 0; --j) {double dy = ps[i].second - pl[j].second;if (dy >= d)break;double dx = ps[i].first - pl[j].first;d = min(d, sqrt(dx * dx + dy * dy));}// 記錄到直線l的距離小于d的點pl.push_back(ps[i]);}return d;
}

// 按x坐標從小到大排序
bool compX(const pdd &p1, const pdd &p2) {return p1.first < p2.first;
}// 按y坐標從小到大排序（歸并排序）
bool compY(const pdd &p1, const pdd &p2) {return p1.second < p2.second;
}

時間復雜度：$O(nlog(n))$。

空間復雜度：$O(n)$。

經驗總結

由于遞歸特別適合解決結構自相似問題，故分治法通常采用遞歸實現，但并非只能采用遞歸實現。當采用遞歸實現時，在每層遞歸中，需要完成“分”、“治”、“合”三個步驟。

“分”指的是，將原問題分解為若干規模較小、相互獨立、與原問題形式相同的子問題。子問題的規模應大致相同，子問題的個數 $k$ 視具體情況而定，一般來說，$k$ 可以取 $2$。“分”這一步尤為重要，若不能將原問題分解為若干符合要求的子問題，說明此問題不適合采用分治法，若分解不恰當，會降低算法效率，甚至得出錯誤結果。數列通常按中點位置進行二分，樹通常按重心分割（重心指使得刪除該頂點后得到的最大子樹的頂點數最少的頂點），平面通常按照坐標進行分割。

“治”指的是，若子問題規模 $n$ 足夠小則直接求解，否則，遞歸求解子問題。子問題規模 $n$ 究竟小到何種程度才算足夠小需要視具體問題而定。

“合”指的是，合并各個子問題的解，得到原問題的解。需要注意的是，當子問題所考慮到的解對于原問題來說不完整時，還需要考慮遺漏的解，如最近點對問題中的情況③。

當遞歸體中需要使用到排序時，可以借鑒歸并排序的思想，從而做到邊求解邊排序，降低排序的時間復雜度。分治法的基本思想較為簡單，就是不斷地將問題劃分成子問題，直到子問題能夠快速求解，當然，需要滿足實驗原理中所列的條件。

需要注意的就是，劃分子集時需要做到不遺漏、不重復。對于最值問題（最大值、最短距離等），有時為了代碼編寫方便，可以允許部分重復，但如果重復考慮的情況太多，可能會提高時間復雜度，這需要權衡，對于計數類問題（方案數等），一般情況下是不允許重復的，如果重復考慮某些情況，很可能就會得出錯誤的結果。

END

文章文檔：公眾號 字節幺零二四 回復關鍵字可獲取本文文檔。