分治法的理解

1. 什么是分治法？

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

2. 何時(shí)能，何時(shí)用分治法來(lái)解決這些問(wèn)題比較好呢？

   這些問(wèn)題應(yīng)當(dāng)具備這幾個(gè)特征：

   （1）問(wèn)題的規(guī)?？s小到一定程度就可以容易的解決了。

   （2）問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同子問(wèn)題。

   （3）問(wèn)題所分解成各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。

   （4）問(wèn)題分解出的子問(wèn)題的解可以合并為原問(wèn)題的解。

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

3. 分治法的基本步驟：

   divide-and-conquer(P)

    {

   if ( | P | <= n0) adhoc(P);   //解決小規(guī)模的問(wèn)題

      divide P into smaller subinstances P1,P2,...,Pk；//分解問(wèn)題

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

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

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

          }

        如果問(wèn)題足夠小能夠直接解決，則解決，如果不能夠在進(jìn)行分治。

4.分治法與遞歸，分治法與循環(huán)

分治法是一種思想，遞歸和循環(huán)都只不過(guò)是一種手段，來(lái)幫助問(wèn)題來(lái)進(jìn)行分治。

示例如下：

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

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

{

int low=0,high=n-1;

//通過(guò)循環(huán)手段來(lái)進(jìn)行分治

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);

}