分治法的基本思想

總體思想

定義：講一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。

1. 将待求解的較大規模問題分割成k個更小規模的問題
2. 對這k個子問題分别求解
3. 如果子問題的規模仍然不夠小，再劃分為k個子問題，如此遞歸，直到問題規模足夠小，可以直接求出解為止

分治法的适用條件

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

1. 該問題的規模縮小到一定的程度就可以容易解決
2. 該問題可以分解為若幹個規模較小的相同問題，即該問題具有最優子結構性質
3. 利用該問題分解出的子問題的解可以合并為該問題的解（如果隻具備上述兩個條件，但是這個條件不滿足的話，則考慮使用貪心算法或動态規劃）

4. 該問題所分解出的各個子問題是互相獨立的，即子問題之間不包含公共的子問題（重複地解公共子問題用動态規劃比較好）

   注：建議使用分治法時要将子問題的規模劃分的較為一緻，即平衡子問題

分治法的複雜度分析

概述：

1. 一個分治法将規模為n的問題分成a個規模為n/b的子問題去解
2. 當 n 0 n_{0} n0​=1,且可以直接求解時，時間機關為1

3. 設将原問題分解為a個子問題以及用merge将a個子問題的姐合并為原問題的解需要用f(n)個機關時間

   用T(n)表示該分治法解規模為|P|=n的問題所需的計算時間

T ⁡ ( n ) = { O ( 1 ) n = 1 aT ⁡ ( n / b ) + f ( n ) n > 1 \operatorname{T}(\mathrm{n})=\left\{\begin{array}{cl} O(1) & \mathrm{n}=1 \\ \operatorname{aT}(\mathrm{n}/b)+\mathrm{f(n)} & \mathrm{n}>1 \end{array}\right. T(n)={O(1)aT(n/b)+f(n)​n=1n>1​

（PS：這個求導公式太複雜了，計算麻煩，直接給出最終的情況）

分治法算法複雜度分析的情況

T ( n ) = { O ( n ) a < b O ( n l o g b n ) a = b O ( n l o g b a ) a > b T(n)=\left\{ \begin{aligned} O(n) & & a < b\\ O(nlog_{b}n) & & a = b \\ O(n^{log_{b}a}) & & a > b \end{aligned} \right. T(n)=⎩⎪⎨⎪⎧​O(n)O(nlogb​n)O(nlogb​a)​​a<ba=ba>b​

分治法之二分查找

二分查找要求被查找數組必須是有序的，首先從中點位置開始查找mid=(high+low)/2，然後和key進行比較

（1）若key==a[mid]，則查找成功并傳回該元素下标

（2）若key<a[mid]，則查找左子表a[low……mid-1]

（3）若key>a[mid]，則查找右子表a[mid+1……high]

注：記得往子表進行查找時，mid一定要+1/-1，因為mid已經與key進行對比了，是以不必要再次算入

二分查找的時間複雜度很好計算O(logn)

（PS：我覺得二分查找這個東西應該挺好了解，而且也很簡單實作，就不在過多描述了）