算法詳解之分治法具體實現

2020-01-26 15:36:45

字體：大中小

來源：轉載

供稿：網友

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

分治法解題的一般步驟：

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

（2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；

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

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

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

關于遞歸,這里舉一個最簡單的例子，求N！；

我們只需要定義函數

復制代碼代碼如下:

int calculate(int n)

{

if(n==1)

return 1;

else

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

}

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

基本思想：

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

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

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

MERGE-SORT (A, p, r)

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

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

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

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

5. MERGE (A, p, q, r) // 合并當前結果

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

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

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

MERGE (A, p, q, r )

1.      n1 ← q − p + 1                                                          //計算A[p->q]的長度
2.      n2 ← r − q                                                                //計算A[q+1->r]的長度
3.      Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]       //創建兩個數組
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行是將原數組中A[p->r]的元素取出到新創建的數組，我們的操作是基于臨時數組的操作
8.      L[n1 + 1] ← ∞
9.      R[n2 + 1] ← ∞                   //8-9行設置界限..
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行進行排序合

這里我還是提供一個具體的實現，請見下面的代碼

C語言代碼

關于代碼注釋，請見博客上面的偽代碼注釋..

復制代碼代碼如下:

#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]);
    }

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

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

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

下面來一張算法時間復雜度的與n規模的關系圖..