概念
分治算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。
分治法解題的一般步驟：
（1）分解，將要解決的問題劃分成若干規模較小的同類問題；
（2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；
（3）合併，按原問題的要求，將子問題的解逐層合併構成原問題的解。
當我們求解某些問題時，由於這些問題要處理的數據相當多，或求解過程相當複雜，使得直接求解法在時間上相當長，或者根本無法直接求出。對於這類問題，我們往往先把它分解成幾個子問題，找到求出這幾個子問題的解法後，再找到合適的方法，把它們組合成求整個問題的解法。如果這些子問題還較大，難以解決，可以再把它們分成幾個更小的子問題，以此類推，直至可以直接求出解為止。這就是分治策略的基本思想。
算法設計模式
它的一般的算法設計模式如下：
Divide-and-conquer(P)
1. if |P|≤n0
2. then return(ADHOc(P))
3. 將P分解為較小的子問題 P1 ,P2 ,...,Pk
4. for i←1 to k
5. do yi ← Divide-and-conquer(Pi) △ 遞歸解決Pi
6. T ← MERGE(y1,y2,...,yk) △ 合併子問題
7. return(T)
其中|P|表示問題P的規模；n0為一閾值，表示當問題P的規模不超過n0時，問題已容易直接解出，不必再繼續分解。ADHOC(P)是該分治法中的基本子算法，用於直接解小規模的問題P。因此，當P的規模不超過n0時，直接用算法ADHOc(P)求解。算法MERGE(y1,y2,...,yk)是該分治法中的合併子算法，用於將P的子問題P1 ,P2 ,...,Pk的相應的解y1,y2,...,yk合併為P的解。
根據分治法的分割原則，原問題應該分為多少個子問題才較適宜？各個子問題的規模應該怎樣才為適當？這些問題很難予以肯定的回答。但人們從大量實踐中發現，在用分治法設計算法時，最好使子問題的規模大致相同。換句話說，將一個問題分成大小相等的k個子問題的處理方法是行之有效的。許多問題可以取k=2。這種使子問題規模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規模不等的做法要好。
分治法的合併步驟是算法的關鍵所在。有些問題的合併方法比較明顯，有些問題合併方法比較複雜，或者是有多種合併方案，或者是合併方案不明顯，如例5。究竟應該怎樣合併，沒有統一的模式，需要具體問題具體分析。
分治法的複雜性分析
從分治法的一般設計模式可以看出，用它設計出的程式一般是一個遞歸過程。因此，分治法的計算效率通常可以用遞歸方程來進行分析。為方便起見，設分解閾值n0=1，且算法ADHOC解規模為1的問題耗費1個單位時間。又設分治法將規模為n的問題分成k個規模為n/m的子問題去解，而且，將原問題分解為k個子問題以及用算法MERGE將k個子問題的解合併為原問題的解需用f(n)個單位時間。如果用T(n)表示該分治法Divide-and-conquer(P)解規模為|P|=n的問題P所需的計算時間，則有:
（1） T(1) = 1
T(n) = kT(n/m) + f(n)
用算法的複雜性中遞歸方程解的漸進階的解法介紹的解遞歸方程的疊代法，可以求得(1)的解:
logm(n-1)
（2）T(n) = n^(logmK) + ∑ (k^j)*f(n/(m^j))
j=0
注意，遞歸方程(1)及其解(2)只給出n等於m的方冪時T(n)的值，但是如果認為T(n)足夠平滑，那么由等於m的方冪時T(n)的值可以估計T(n)的增長速度。通常，
我們可以假定T(n)是單調上升的，從而當mi≤nn0
由於我們關心的一般是最壞情況下的計算時間複雜度的上界，所以用等於號(=)還是小於或等於號(≤)是沒有本質區別的分治法的幾種變形。
幾種分治的方法
1.二分法 dichotomy一種每次將原問題分解為兩個子問題的分治法，是一分為二的哲學思想的套用。這種方法很常用，由此法產生了許多經典的算法和數據結構。
2.分解並在解決之前合併法 divide and marriage before conquest一種分治法的變形，其特點是將分解出的子問題在解決之前合併。
3.管道傳輸分治法 pipelined divide and conquer一種分治法的變形，它利用某種稱為“管道”的數據結構在遞歸調用結束前將其中的某些結果返回。此方法經常用來減少算法的深度
舉例
分治算法西洋棋棋盤上某個位置的一隻馬它是否可能只走63步正好走過除起點外的其他63個位置各一次?試設計一個分治算法
算法步驟：
1 ：從左上角起，給棋盤編號（1，1），（1，2），。。。。。。（8，8），計為集合qp。tracks記錄走過的每個點. （可以想像為坐標（x,y））
2：設起點為（1，1），記為 當前位置 cp，
3：搜尋所有可走的下一步，根據“馬行日”的走步規則，可行的點的坐標是x坐標加減1，y坐標加減2，
或是x加減2，y加減1； （例如起點（1，1），可計算出（1+1，1+2），（1+1，1-2），（1-1，1+2），（1-1，1-2），（1+2，1+1），（1+2，1-1），（1-2，1+1），（1-2，1-1） 共8個點）， 如果沒有搜到可行點，程式結束。
4：判斷計算出的點是否在棋盤內，即是否在集合qp中；判斷點是否已經走過，即是否在集合tracts中，不在才是合法的點。（在上面的舉例起點（1，1），則合法的下一步是（2，3）和 （3，2））
5：將前一步的位置記錄到集合tracts中，即tracts.add（cp）；選擇一個可行點，cp=所選擇點的坐標。
6：如果tracts里的點個數等於63，退出程式，否則回到步驟3繼續執行。
經典計算機算法介紹
| 算法是計算機科學中一門古老而常新的學科，就像一個人的思維能力一樣，其重要性對於計算機性能的分析、套用與改進有著至不言而喻的地位。而隨著計算機科學技術的發展，新的算法也隨著新的套用漸漸出現，但總有一些算法由於其本身具有的特點以及對計算機科學發展做出的卓越貢獻而成為經典，本任務就是要介紹這些經典算法。 |
