算法分析之分治法學習總結（一）
一）解決問題的類型：當我們要解決一個輸入規模(n)很大的問題時，直接處理往往比較困難或者根本無法
求解，我們希望把輸入規模縮小，即分成很多份，分別解決了，并且這些小問題容易合起來從而解決整個問
題。
二）解題關鍵：
1)如何分:我們往往先把輸入分成兩個與原來相同的子問題，如果規模還太大，我們
對這些子問題再做上述處理，直到這些子問題容易解決為止.
2)合并子問題:往往分治法的難點在于分完之后怎么合并.合并策略決定了算法的優劣,合并問題根據具體問題而
定,沒有固定的方法
3)分治問題往往用到遞歸算法.
三)幾種類型的分治問題:
1)把問題分成字問題后,如果某個子問題解決了則整個問題也就解決了,無須合并.
典型事例:二分檢索問題(前提是一組按照關鍵碼排好順序對象,不妨設按升序排列)
二分檢索的解題思路是先看看中間那個數,如果這個數是要查找的,那么ok,問題解決,否則如果比key大,那么
在前一半繼續上述過程,否則在后一半繼續上述過程,直到找到或者查找失敗.
程序代碼:(設為int型數)

      void BinarySearch(int a[],int low,int high,int key)
{
 
 if(low >= high) return;
 int mid =  (low + hight) / 2;
 if(a[mid] == key) return mid;
 else if(a[mid] > key) 
       return BinarySearch(a[],low,mid,key);
 else if(a[mid] < key) 
       return BinarySearch(a[],mid,low,key);
}

    

2)把問題分了之后,再經過合并最終解決問題.
典型事例:歸并排序問題:
這個問題就象我們在一個很長的隊,現在要按大小個排好,我們把這個隊分成兩個(如果還是太長,可以再分,
先看分成兩個的問題,這樣容易看清合并過程),我們把這兩隊分別排好,然后合成一隊,合并的過程很簡單,就
是弄一個新的隊,從那兩個個隊的排頭分別出列,比一下矮的站在第一個位置,高的在一邊等著,等另一個隊現
在的排頭出列,再比一下,矮的排在第二個位置,高的站在一邊,重復上述過程,直到有一個隊變空,然后把另一個
隊拉過來接在新隊的隊尾,這就排好了整個隊了.
歸并排序,就是把一組待排的關鍵值可比的東西,我們把他分成兩個小組,如果問題規模還不夠小,我們繼續
分,直到容易解決為止,然后把小的組排好續,然后合并成一組.
算法過程: