【算法學習筆記】之分治算法

版權聲明：本文為部落客原創文章，轉載請注明出處http://blog.csdn.net/u013132758。 https://blog.csdn.net/u013132758/article/details/50956439

引言

“分治”顧名思意：分而治之。《孫子兵法》有雲：“凡治衆如治寡,分數是也 。”分治法在我們日常生活中也最為常見。比如管理一個國家:先把國家劃分為許多省份，再把每個省份劃分為若幹個市，依此類推，市===》縣（區） ===》鄉（鎮）===》村。這就是分治。在算法設計領域我們有一種算法稱為分治算法。

1、分治算法的基本思想及步驟

分治算法的總體設計思想就是”分、治、合“。所對應的步驟也是”分、治、合“。

分：即将一個大的問題依據一種規則分成若幹份小的問題。

治：若問題規模足夠小，用較簡單的方法來解決。若問題規模還是較大則遞歸調用”分“來繼續劃分，直至問題規模足夠小。

合：按照原問題的要求，将子問題的解按照一定的政策逐層合并，并構成原問題的解。

2、分治算法的适用條件

分治法所能解決的問題一般具有以下幾個特征：

1) 該問題的規模縮小到一定的程度就可以容易地解決

2) 該問題可以分解為若幹個規模較小的相同問題，即該問題具有最優子結構性質（很重要）。

3) 利用該問題分解出的子問題的解可以合并為該問題的解（能否用分治法可以說完全取決于這點）；

4) 該問題所分解出的各個子問題是互相獨立的，即子問題之間不包含公共的子子問題（分治法的效率）。

3、分治算法的時間複雜度

分治算法的時間複雜度分析我們可以用遞推公式和遞歸樹。

例如：一個規模為n的問題，每次将其分解為k個子問題，直至子問題的規模為1,合并k個子問題的時間複雜度為O(n).

則原問題的時間複雜度T(n)=kT(n/k)+O(n).由此可求得起時間複雜度為 O（nlogn）.

遞歸樹如下：

由于logk為常數，是以可以忽略。則它的時間複雜度為O（n log n).

4、分治算法的經典問題

（1）二分搜尋

（2）大整數乘法

（3）Strassen矩陣乘法

（4）棋盤覆寫

（5）合并排序

（6）快速排序

（7）線性時間選擇

（8）最接近點對問題

（9）循環賽日程表

（10）漢諾塔

其中我們最熟悉的莫過于二分搜尋及合并排序了。

下面是合并排序的參考代碼。

/*************************************
*
*   Megre_Sort()
* 輸入:兩個數組及長度
*************************************/
void Megre_sort(int *A,int p,int *C,int q)
{
	int *B; 
	int s=0,t=0,k=0,i = 0,r=p+q;
	B = (int *)malloc(sizeof(int)*(p+q));
	
     while( s <= p && t <= q )
		 
	 {
		 if(A[s] <= C[t])
		 {
			 B[k] = A[s];
			 s++;
		 }
		 else
		 {
			 B[k] = C[t];
			 t++;
		 }
		 k++;
	 }
	 if (s = q +1)
		 for( i = 0; i <= (r-k);i++)
			 B[k+i] = C[t+i];
		 else
			 for( i = 0; i <= (r-k);i++)
			 B[k+i] = A[s+i];
for(i = 0; i < p+q ; i++)
{
	printf("%d ",B[i]);
}
}
/*************************************
*
*   BottomUp_Sort()
* 輸入:數組及長度
*************************************/
void BottomUp_Sort(int n)
{
	int i = 1,s,j;
	int *A;
	A = (int*)malloc(sizeof(int)*n);
   srand( (unsigned)time( NULL ) );  
   for(i = 0;i < n; i ++)
   {
	   A[i] = rand();
   }
    while ( i < n)
	{ 
		s = i;
		i = 2*s;
		j = 0;
		while ( j + i <= n)
		{
			Megre_sort(A,s,A+s,i);
			j++;
		}
		if ( j + s < n)
			Megre_sort(A,s,A+s,n-j);
	}
}
           

快速排序參考代碼：

/*************************************
*
*       Quick_Sort()
* 輸入:數組及長度
*************************************/
void Quick_Sort(int *A,int low,int high)
{
	
    if (A == NULL || low >= high)
        return ;
    int part = SPLIT(A, low, high);
    Quick_Sort(A, low, part-1);
    Quick_Sort(A, part+1, high);
    
   
}
/*************************************
*
*       SPLIT()
* 輸入:劃分數組 
*************************************/
int SPLIT(int *a, int beg, int end)
{
    int i,c,x,j;
         i = beg;
         x = a[beg];
        for(j = beg+1; j <= end; ++j)
        {
            if(a[j] <= x)
            {
			     ++i;
			     if(i != j)
			     {
    				c= a[i];
				  a[i]=a[j];
				  a[j] =c;
     			 }    
            }
        }
        x = a[beg];
		 a[beg]=a[i];
		 a[i] = x;
        return i;
}