分治算法 —— 算法總結

分治算法 —— 總結

時間總是太快啦！我将近花費四天左右的時間來學習分治算法。總體上把大部分分治算法的經典例題都做啦，接近兩天的時間完成分治法相關的部落格撰寫來記錄題目心得與體會！

今天來對分治算法總結一下！！！

雖然分治算法的相關例題做的也不多也不少，但我仍舊不敢說我對分治算法了如指掌，胸有成竹啦！頂多算是入門啦吧！路漫漫其修遠兮，吾将上下而求索！

此處附上分治算法經典例題，來源以及題解。

（1）棋盤覆寫 來源 題解

（2）循環賽日程表 來源 題解

（3）快速排序 題解

（4）合并排序 題解

（5）最大子序列和 來源 題解

（6）逆序對個數 來源 題解

（7）光榮的夢想 來源 題解

（8）黑白棋子的移動 來源 題解

（9）快速幂 題解

（10）取餘運算 來源 題解

（11）麥森數 來源 題解

分治算法 ; 一般大規模問題化為小規模問題，最後由小規模問題的解合并得到大規模的解

（說明：有時候是不需要合并的，依題而定）

1. 二維平面的劃分(一分為四 或 一分為一)

棋盤覆寫将一個二維平面劃分為四個子問題，每一個子問題又可以接着劃分為四個子問題直到劃分到遞歸的邊界

循環比賽日常表雖不是劃分為四個子問題，由于其中的一個子問題與另三個子問題有緊密的關系。故可以将一個二維平面劃分為1個子問題，劃分後的子問題又可以繼續遞歸劃分一個子問題直到劃分到遞歸邊界

2.一維平面的劃分（歸并排序和快速排序）

歸并排序和快速排序都是将一個一維平面的問題劃分為兩個子問題，每一個子問題接着繼續劃分為兩個子問題直到劃分到元素的個數為一

3.歸并排序之最大連續子序列和

合并排序的最經典的用法，最大子序和的最大值要門出現在左右part和中間part三者之間，需要做的是如何求中間part，其他部分和歸并排序一模一樣,最後來個三者比較即可

4.歸并排序的應用 (逆序對個數 與 光榮的夢想)

逆序對個數和光榮的夢想其直接的思想是冒泡排序來記錄交換的次數，但是冒泡排序的效率較低。是以通常采取歸并排序的政策來記錄交換的次數

5.空間上一分為一劃分（黑白棋子的移動）

黑白棋子的移動屬 n規模的問題劃分為n-1規模問題直到劃分到n = 4的情況

6.空間上的一分為二劃分(快速幂)

快速幂采用分治的政策，a ^ b 直接拆成 a ^(b/2) * a^(b/2) * a ^ (b %2). a^(b/2) 繼續劃分，不斷在空間上不斷的分兩半往下一層遞進

7.快速幂應用 （取餘運算 和 麥森數）

取餘運算主要在快速幂的計算過程中不斷取餘，而不是用快速幂計算完再求餘

麥森數主要使用快速幂，不過此時的快速幂的類型不是整型資料而是自定義的大整數類型，額外涉及一些數論的相關知識

結語

分治算法 分治算法的核心就是分而治之,也就是将原問題劃分為若幹個規模更小但結構與原問題相似的子問題,遞歸地解決這些子問題然後進行合并,就可以得到原問題的解。

分治算法是一種算法政策，可以遞歸實作也可以非遞歸實作。但大部分是需要遞歸來實作的，因為遞歸本身就是一種分的展現呀！！！

分治算法

1. 在二維上 劃分四個子問題，兩個子問題或一個子問題(如棋盤覆寫，循環比賽日程表)
2. 在一維上 劃分為兩個子問題(左右兩個part，如遞歸排序和快速排序)
3. 在空間上 劃分為一個子問題，層層遞進(如 黑白棋子移動)
4. 在空間上 劃分為兩個子問題，層層遞進(如 快速幂)

以上都是4天分治經典題目學習與2天部落格撰寫的個人經驗總結！大佬勿噴