分治法的理解

1. 什么是分治法？

   分治法的基本思想是將一個難以直接解決的大問題，分解成一些規模較小的相同問題，以便各個擊破，分而治之。

2. 何時能，何時用分治法來解決這些問題比較好呢？

   這些問題應當具備這幾個特征：

   （1）問題的規模縮小到一定程度就可以容易的解決了。

   （2）問題可以分解為若干個規模較小的相同子問題。

   （3）問題所分解成各個子問題是相互獨立的，即子問題之間不包含公共的子問題。

   （4）問題分解出的子問題的解可以合并為原問題的解。

   上述的第一條特征是絕大多數問題可以滿足的，因為問題的計算復雜性一般是隨著問題規模的增大而增加；第二條特征是引用分治法的前提，它也是大多數問題可以滿足的，此特征反映了遞歸思想的應用；第三條特征涉及分治法的效率，涉及許多不必要的工作-重復求解公共的子問題，第四條特征是關鍵，能否利用分治法完全取決于問題是否具有第四條特征。

3. 分治法的基本步驟：

   divide-and-conquer(P)

    {

   if ( | P | <= n0) adhoc(P);   //解決小規模的問題

      divide P into smaller subinstances P1,P2,...,Pk；//分解問題

     for (i=1,i<=k,i++)

      yi=divide-and-conquer(Pi);  //遞歸的解各子問題

   return merge(y1,...,yk);  //將各子問題的解合并為原問題的解

          }

        如果問題足夠小能夠直接解決，則解決，如果不能夠在進行分治。

4.分治法與遞歸，分治法與循環

分治法是一種思想，遞歸和循環都只不過是一種手段，來幫助問題來進行分治。

示例如下：

（1）二分查找算法的非遞歸形式

 int NBinarySearch(int n,int s[n],int x)

{

int low=0,high=n-1;

//通過循環手段來進行分治

while(low<=high)

{

int middle=(low+high)/2;

if(x==s[middle]) return middle;

else if(x>s[middle]) low=middle+1;

else high=middle-1;

}

}

(2)二分查找算法的遞歸形式

int BinarySearch(int s[n],int x,int low,int high)

{

if(low>high) return -1;

int middle=(low+high)/2;

if(x==s[middle]) return middle;

else if(x>middle)

return BinarySearch(s,x,middle,high)

else

return BinarySearch(s,x,low,middle-1);

}