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

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