算法詳解之分治法具體實(shí)現(xiàn)

更新時(shí)間：2014年02月17日 15:29:16 作者：

這篇文章主要介紹了算法詳解之分治法具體實(shí)現(xiàn),需要的朋友可以參考下

分治算法的基本思想是將一個(gè)規(guī)模為N的問題分解為K個(gè)規(guī)模較小的子問題，這些子問題相互獨(dú)立且與原問題性質(zhì)相同。求出子問題的解，就可得到原問題的解。

分治法解題的一般步驟：

（1）分解，將要解決的問題劃分成若干規(guī)模較小的同類問題；

（2）求解，當(dāng)子問題劃分得足夠小時(shí)，用較簡單的方法解決；

（3）合并，按原問題的要求，將子問題的解逐層合并構(gòu)成原問題的解。

一言以蔽之：分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。

在認(rèn)識(shí)分治之前很有必要先了解一下遞歸，當(dāng)然，遞歸也是最基本的編程問題，一般接觸過編程的人都會(huì)對(duì)遞歸有一些認(rèn)識(shí).為什么要先了解遞歸呢？你看，根據(jù)上面所說的，我們就要將一個(gè)問題分成若干個(gè)小問題，然后一一求解并且最后合并，這就是一個(gè)遞歸的問題，遞歸的去分解自身，遞歸的去解決每一個(gè)小問題，然后合并…

關(guān)于遞歸,這里舉一個(gè)最簡單的例子，求N??；

我們只需要定義函數(shù)

復(fù)制代碼代碼如下:

int calculate(int n)

{

if(n==1)

return 1;

else

return n*calculate(n-1); //調(diào)用自身…

}

好了，有了遞歸的鋪墊，我們下來來看一看一個(gè)分治算法的問題，歸并排序問題…

基本思想：

將待排序元素分成大小大致相同的2個(gè)子集合(遞歸直到最小的排序單元），分別對(duì)2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。

下面我們用一張圖來展示整個(gè)流程,最下面的（姑且叫他第一層）是原始數(shù)組分成了8個(gè)最小排序問題，各自只有一個(gè)元素，故不需要排序，大家可以看到，我們通過分而治之的思想把對(duì)最初數(shù)組的排序分為了若干個(gè)只有一個(gè)元素的小數(shù)組的排序,然后第二層,我們進(jìn)行了合并，將每兩個(gè)最小排序結(jié)果合并為有兩個(gè)元素的數(shù)組,然后逐層往上進(jìn)行合并，就有了最后的結(jié)果…

下面我們來看一下這個(gè)算法的具體實(shí)現(xiàn)，下面的MERGE-SORT (A, p, r)表示對(duì)數(shù)組A[p->r]的排序過程.其中p->r代表從p到r.

MERGE-SORT (A, p, r)

1. IF p < r // 進(jìn)行A[p->r]的排序過程自然需要p<r的前提條件

2. THEN q = [(p + r)/2] // 將當(dāng)前的排序問題一分為二，分別進(jìn)行處理

3. MERGE-SORT (A, p, q) //繼續(xù)遞歸看能不能將問題繼續(xù)一分為二，處理A[p->q]的排序

4. MERGE-SORT (A, q + 1, r) // 繼續(xù)遞歸看能不能將問題繼續(xù)一分為二處理A[q+1->r]的排序

5. MERGE (A, p, q, r) // 合并當(dāng)前結(jié)果

到這里，分治算法的精髓已經(jīng)出來了，我們通過遞歸將問題進(jìn)行分解到足夠小…繼而進(jìn)行結(jié)果計(jì)算…然后再將結(jié)果合并.

下面來處理一下邊角料的工作，呵呵，讓大家看到一個(gè)完整的歸并排序的例子，整個(gè)算法總結(jié)系列我都沒有很好的使用偽代碼，而是使用我認(rèn)為廣泛使用的C語言代碼來進(jìn)行代碼詮釋.實(shí)際上，描述算法最好還是使用偽代碼比較好，這里我對(duì)我前面的四篇文章沒有使用偽代碼而小小的鄙視一下自己，太不專業(yè)了..呵呵

以下算法MERGE (A, p, q, r )表示合并A[p->q]和A[q+1->r]這兩個(gè)已經(jīng)排序好的數(shù)組

MERGE (A, p, q, r )

1.      n1 ← q − p + 1                                                          //計(jì)算A[p->q]的長度
2.      n2 ← r − q                                                                //計(jì)算A[q+1->r]的長度
3.      Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]       //創(chuàng)建兩個(gè)數(shù)組
4.      FOR i ← 1 TO n1
5.            DO L[i] ← A[p + i − 1]
6.      FOR j ← 1 TO n2
7.            DO R[j] ← A[q + j ]        //4-7行是將原數(shù)組中A[p->r]的元素取出到新創(chuàng)建的數(shù)組，我們的操作是基于臨時(shí)數(shù)組的操作
8.      L[n1 + 1] ← ∞
9.      R[n2 + 1] ← ∞                   //8-9行設(shè)置界限..
10.    i ← 1
11.    j ← 1
12.    FOR k ← p TO r
13.         DO IF L[i ] ≤ R[ j]
14.                THEN A[k] ← L[i]
15.                        i ← i + 1
16.                ELSE A[k] ← R[j]
17.                        j ← j + 1                //12-17行進(jìn)行排序合

這里我還是提供一個(gè)具體的實(shí)現(xiàn)，請(qǐng)見下面的代碼

C語言代碼

關(guān)于代碼注釋，請(qǐng)見博客上面的偽代碼注釋..

復(fù)制代碼代碼如下:

#include<stdio.h>
int L[100],R[100];
void merge(int numbers[],int left, int mid, int right)
        {
            int n1=mid-left+1;
            int n2=right-mid;
            int i,j,k;
            for(i=1;i<=n1;i++)
             L[i]=numbers[left+i-1];
            for( j=1;j<=n2;j++)
             R[j]=numbers[mid+j];
            L[n1+1]=99999;
            R[n2+1]=99999;

            i=1;
            j=1;

            for(k=left;k<=right;k++)
            if(L[i]<=R[j])
               {
                   numbers[k]=L[i];
                   i++;
                   }
                 else
                  {
                       numbers[k]=R[j];
                       j++;
                  }
        }

void mergeSort(int numbers[],int left, int right)

{
    if(left<right)
    {
                int mid;
            mid = (right + left) / 2;
            mergeSort(numbers, left, mid);
            mergeSort(numbers, mid+1, right);
            merge(numbers,left, mid, right);
        }

}

int main()
{
    int numbers[]={5,2,4,6,1,3,2,6};
    mergeSort(numbers,0,7);
    for(int i=0;i<8;i++)
    printf("%d",numbers[i]);
    }

歸并排序算法的時(shí)間復(fù)雜度是O（nlogn）,對(duì)于冒泡排序的O(n*n),效率還有有比較好的提高..

其實(shí)本人原來在學(xué)習(xí)的時(shí)候好長一段時(shí)間不理解為什么時(shí)間復(fù)雜度會(huì)是O（nlogn）,像冒泡排序就比較好理解，有兩個(gè)for循環(huán)，問題的規(guī)模隨著n變大而變大，算法時(shí)間復(fù)雜度自然就是O(n*n),后面花了一些時(shí)間來閱讀一些資料才明白其原理，這里我已經(jīng)將資料地址放到了本文最后，有興趣的也可以去看看.簡單的描述一下為什么會(huì)是O（nlogn）

大家看看，我們的例子，解一個(gè)8個(gè)元素的數(shù)組，我們用到了幾層？是四層，假設(shè)我們這里有n個(gè)元素，我們會(huì)用到多少層？根據(jù)一定的歸納總結(jié)，我們知道我們會(huì)用到(lgn)+1層..(lgn)+1層需要用到lgn層次的合并算法.現(xiàn)在再看看MERGE (A, p, q, r )的復(fù)雜度是多少，毫無疑問O（n），故其歸并排序的算法時(shí)間復(fù)雜度是O（nlogn）.當(dāng)然這個(gè)結(jié)果還可以通過其他的方法計(jì)算出來，我這里是口語話最簡潔的一種..

下面來一張算法時(shí)間復(fù)雜度的與n規(guī)模的關(guān)系圖..