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

分治法解題的一般步驟：

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

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

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

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

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

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

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

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

基本思想：

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

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

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

MERGE-SORT (A, p, r)

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

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

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

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

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

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

下面來(lái)處理一下邊角料的工作，呵呵，讓大家看到一個(gè)完整的歸并排序的例子，整個(gè)算法總結(jié)系列我都沒有很好的使用偽代碼，而是使用我認(rèn)為廣泛使用的C語(yǔ)言代碼來(lái)進(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]的長(zhǎng)度
2.      n2 ← r − q                                                                //計(jì)算A[q+1->r]的長(zhǎng)度
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語(yǔ)言代碼

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

其實(shí)本人原來(lái)在學(xué)習(xí)的時(shí)候好長(zhǎng)一段時(shí)間不理解為什么時(shí)間復(fù)雜度會(huì)是O（nlogn）,像冒泡排序就比較好理解，有兩個(gè)for循環(huán)，問(wèn)題的規(guī)模隨著n變大而變大，算法時(shí)間復(fù)雜度自然就是O(n*n),后面花了一些時(shí)間來(lái)閱讀一些資料才明白其原理，這里我已經(jīng)將資料地址放到了本文最后，有興趣的也可以去看看.簡(jiǎn)單的描述一下為什么會(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ù)雜度是多少，毫無(wú)疑問(wèn)O（n），故其歸并排序的算法時(shí)間復(fù)雜度是O（nlogn）.當(dāng)然這個(gè)結(jié)果還可以通過(guò)其他的方法計(jì)算出來(lái)，我這里是口語(yǔ)話最簡(jiǎn)潔的一種..

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

最新評(píng)論