第8章縮小規模算法8.1分治與遞歸算法8.2動態規劃8.3貪心算法

8.1分治與遞歸算法

8.1.1遞歸算法設計

一個直接或間接調用自身的算法稱為遞歸算法。一個函數是用自身給出定義的函數稱為遞歸函數。在計算機算法設計中，使用遞歸策略往往使算法的描述和函數的定義簡潔，且易于理解。

1.排列問題

設R={r1，r2，…，rn}是要進行排列的n個元素，Ri=

R-{ri}。設集合X中元素的全排列記為Perm(X)；(ri)Perm(X)表示在全排列Perm(X)的每一個排列前加上前綴ri得到的排列。R的全排列可遞歸定義為

(1)當n=1時，Perm(R)=(r1)，r1是集合R中的唯一元素。

(2)當n＞1時，Perm(R)由(r1)Perm(R1)，(r2)Perm(R2)，

…，(rn)Perm(Rn)構成。

2.整數劃分問題

將一個正整數n表示為一系列正整數之和：

n=n1+n2+?…?+nk,

其中，n1≥n2≥…≥nk≥1，k≥1。該表示稱為n的一個劃分；不同劃分的個數稱為劃分數，記為p(n)。例如，6有如下11種不同的劃分：在正整數n的所有不同劃分中，將最大加數n1不大于m的劃分個數記為q(n，m)，則可以建立如下的遞歸關系：

(1)?q(n，1)=1，n≥1；

當最大加數n1不大于1時，任何正整數只有一種劃分形式：n=1+1+?…?+1。

(2)?q(n，m)=q(n，n)，m≥n；

最大加數n1不能大于n，因此q(1，m)=1。

(3)?q(n,n)=1+q(n,n-1)；

正整數n的劃分，由n1=n的劃分和n1≤n-1的劃分組成。

(4)?q(n,m)=q(n,m-1)+q(n-m,m),n＞m>1；

正整數n的最大加數n1不大于m的劃分，由n1=m的劃分和n1≤m-1的劃分組成。以上關系實際上給出了計算q(n,m)的遞歸計算式：

(8-1)

據此可得到計算q(n，m)的遞歸函數。8.1.2分治算法設計

分治算法的基本思想是將一個規模為n的問題分解為k個規模較小的子問題，這些子問題相互獨立且與原問題相同。遞歸地解這些子問題，然后將這些子問題的解合并，就得到了原問題的解。一般算法設計模式如下：

1.二分搜索技術

二分搜索技術是查找一個已排好序的表的最好方法，其查找效率較高。

給定一個排好序的n個元素R[0]～R[n-1]，現要在這n個元素中找出一個特定元素x。例如，已知數組元素的有序序列為：5，10，19，21，31，37，42，48，50，55，現要查找x分別為19及66的元素，其查找過程如下：由于low>high，因此說明查找失敗。

在二分搜索算法中，每進行一次比較，數組都縮小一半，從1/2，1/4，1/8，…，在第i次比較時，最多只剩下

n/2i

個記錄。最壞的情況是到最后只剩下一個記錄，即n/2i=1，所以i=lbn，即最壞情況下比較次數的復雜度是O(lbn)。

二分搜索中查找到每一個記錄的比較次數可通過二叉樹來描述：用當前查找區間中間位置上的記錄作為根，左子表和右子表中的記錄分別作為根的左子樹和右子樹，由此得到的二叉樹稱為折半查找判定樹；樹中結點內的數字表示該結點在有序表中的位置。例如，對長度為11的表進行折半查找時，其判定樹如圖8-1所示。圖8-1具有11個結點的折半查找判定樹可見，若查找的結點是表中第6個記錄，需要一次比較；若查找的是表中第3個或第9個記錄，需要兩次比較；若查找的是表中第11個記錄，需要三次比較，由此看出，折半查找的過程恰好是走了一條從根到被查找結點的路徑，關鍵字進行比較的次數即為被查找結點在樹中的層數。因此，折半查找成功時進行的比較次數最多不超過樹的深度。那么，二分搜索的平均查找長度是多少呢？為方便起見，不妨設結點總數n=2h-1，則判定樹的深度為h=lb(n+1)

的滿二叉樹，在等概率的條件下，折半查找的平均查找長

度為

(8-2)

當結點總數n很大時，ASLbin

lb(n+1)-1。

2.歸并排序

歸并排序(MergeSort)是將兩個或兩個以上的有序表合成一個新的有序表。歸并排序算法是使用分治策略實現對n個元素進行排序的算法。其基本思想是：當n=1時，終止排序；否則將待排序的元素分成大致相同的兩個子集合，分別對兩個子集合進行歸并排序。最終將排好序的子集合合并成所要求的排序結果。例如，對于一組待排序的記錄，其關鍵字分別為：47，33，61，82，72，11，25，47

，若對其進行兩路歸并排序，則先將這8個記錄看成長度為1的8個有序子文件，然后逐步兩兩歸并，直至最后達到全部關鍵字有序為止。其具體的歸并排序過程如圖8-2所示。圖8-2二路歸并排序示例

3.快速排序

快速排序算法是基于分治策略的排序算法之一。其基本思想是對輸入的數組R[l:h]按以下三個步驟進行排序：

步驟一：分解(Divide)。以R[l]為基準元素將R[l:h]劃分為三段：R[l:q-1]，R[q]和R[q+1:h]，且使R[l:q-1]中任何元素不大于R[q]，R[q+1:h]中任何一個元素大于R[q]，下標q在劃分過程中確定。

步驟二：遞歸求解(Conquer)。通過遞歸調用快速排序算法分別對R[l:q-1]和R[q+1:h]進行排序。

步驟三：合并(Merge)。由于對R[l:q-1]和R[q+1:h]的排序是就地進行的，因此實際上不需要進一步的合并計算。圖8-3快速排序示例一般來說，快速排序有非常好的時間復雜度，它優于各種排序算法。可以證明，對n個記錄進行快速排序的平均時間復雜度為O(nlbn)。但是，當待排序文件的記錄已按關鍵字有序或基本有序時，情況反而惡化了，原因是在第一趟快速排序中，經過n-1次比較之后，將第一個記錄仍定位在它原來的位置上，并得到一個包括n-1個記錄的子文件；第二次遞歸調用，經過n-2次比較，將第二個記錄仍定位在它原來的位置上，從而得到一個包括n-2個記錄的子文件；依次類推，最后得到的總比較次數為

(8-3)

這使快速排序蛻變為起泡排序，其時間復雜度為O(n2)。在這種情況下，通常采用“三者取中”的規則加以改進。即在進行一趟快速排序之前，對R[l]，R[h]?和R[

(l+h)/2

]?進行比較，再將三者中取中值的記錄和R[l]?交換，就可以改善快速排序在最壞情況下的性能。在最好情況下，每次劃分所取的基準都是無序區的中值記錄，劃分的結果是基準的左、右兩個無序子區的長度大致相等。設C(n)表示對長度為n的文件進行快速排序所需的比較次數，顯然它應該等于對長度為n的無序區進行劃分所需的比較次數n-1，加上遞歸地對劃分所得的左、右兩個無序子區(長度≤n/2)進行快速排序所需的比較次數。假設文件長度n=2k，那么總的比較次數為

(8-4)

其中，C(1)是一個常數；k=lbn。

8.2動態規劃

動態規劃法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適用于動態規劃法求解的問題，經分解得到的子問題往往不是互相獨立的。若用分治法解這類問題，則分解得到的子問題數量太大，以至于最后解決原問題需要耗費指數級的時間。另外，在用分治法求解時，有些子問題被重復計算了許多次。基于動態規劃法的算法設計通常按以下四個步驟進行：

(1)找出最優解的性質，并描述其結構特征。

(2)遞歸定義最優值。

(3)以自底向上的方式計算最優值。

(4)根據計算最優值時得到的信息構造一個最優解。

1.矩陣連乘問題

給定n個矩陣{A0，A1，…，An-1}，其中Ai和Ai+1是可

乘的，i=0，1，…，n-2。要求計算這n個矩陣的連乘積A0A1…An-1。

由于矩陣乘法滿足結合律，因此計算矩陣連乘可以有許多不同的計算次序，每種計算次序都可用不同的加括號方式確定。如果矩陣連乘完全加了括號，則說明計算矩陣連乘的次序也完全確定，這時就可以使用兩個矩陣相乘的標準算法計算矩陣的連乘積。完全加括號的矩陣連乘積可以遞歸定義為

(1)單個矩陣是完全加括號的。

(2)矩陣連乘積A是完全加括號的，則A可以表示為兩個完全加括號的矩陣B和C的乘積并加括號，即A=(BC)。

2.矩陣連乘積的最優計算次序

(1)分析最優解的結構。

設將矩陣連乘積A0A1…An-1記為A[0:n-1]，計算A[0:n-1]的一個最優計算次序。設一個計算次序在矩陣Ak和Ak+1之間斷開,0≤k＜n-1,則完全加括號方式為((A0…Ak)(Ak+1…An-1))。首先依此次序先分別計算A[0:k]和A[k+1:n-1]，然后將計算的結果相乘得到A[0:n-1]。它的總計算量為A[0:k]的計算量加上A[k+1:n-1]的計算量，再加上A[0:k]和A[k+1:n-1]相乘的計算量的和。這個問題的關鍵特征是：計算A[0:n-1]的一個最優計算次序，其所包含的計算矩陣子鏈A[0:k]和A[k+1:n-1]的計算次序也是最優的。

因此，矩陣連乘積計算次序問題的最優解包含著其子問題的最優解，該性質稱為最優子結構性質。一個問題是否具有最優子結構性質，是該問題是否可以用動態規劃法求解的重要前提。

(2)建立遞歸關系。

對于矩陣連乘積的最優計算次序問題，設計算A[i:j]

(0≤i≤j≤n-1)所需的最少數乘次數為m[i][j]，則原問題的最優值為m[0][n-1]。

①當i=j時，A[i:j]=Ai為單一矩陣，無須計算，因此m[i][i]=0，i=0，1，…，n-1。

②當i＜j時，可利用最優子結構性質計算m[i][j]。若計算A[i:j]的最優次序是在Ak和Ak+1之間斷開，i≤k＜j，則m[i][j]=m[i][k]+m[k+1][j]+pipk+1pj+1。由于計算時是不知道斷開點k的位置，因此k還未確定。不過k的位置只有j-i種可能，即k∈{i，i+1，…，j-1}，k是j-i個位置中使計算量達到最小的那個位置。因此，m[i][j]可以遞歸定義為

(8-5)

若將m[i][j]的斷開位置k記為s[i][j]=k，則在計算出最優值m[i][j]后，可由s[i][j]遞歸地構造出相應的最優解。

(3)計算最優值。

根據計算m[i][j]?的遞歸式(8-5)，容易編寫遞歸算法計算m[0][n-1]，但簡單地使用遞歸算法計算將耗費指數級的計算時間。事實上，在遞歸計算過程中，對于0≤i≤j≤n-1時，不同的有序對(i,j)對應于不同的子問題，不同的子問題個數只有個。由此可見，在遞歸計算時許多子問題被重復計算多次，這也是該問題可以用動態規劃法求解的顯著特征之一。例如，計算矩陣連乘積A0A1A2A3A4A5，其中各矩陣

的維數分別為30×35、35×15、15×5、5×10、10×20、20×25。

用動態規劃算法MatrixChain計算m[i][j]?的先后次序如圖8-4(a)所示，計算結果m[i][j]和s[i][j](0≤i≤j≤n-1)如圖8-4(b)和(c)所示。圖8-4計算m[i][j]的次序在計算m[1][4]?時，根據遞歸式(8-5)有

(8-6)

且k=3，因此s[2][5]=3。

(4)構造最優解。

MatrixChain算法的結果只給出了計算矩陣連乘積的最

少數乘次數，還不知道采用何種計算次序才能達到最少數

乘次數。8.2.1動態規劃算法的基本要素

1.最優子結構

設計動態規劃算法的第一步是分析最優解的結構，當問題的最優解包含了其子問題的最優解時，稱該問題具有最優子結構性質。

在矩陣連乘積最優計算次序問題中，若A0A1…An-1的最優完全加括號方式在Ak和Ak+1之間將矩陣鏈斷開，則由此確定的子矩陣鏈A0A1…Ak和Ak+1Ak+2…An-1的完全加括號方式也最優。

2.重疊子問題

可以用動態規劃算法求解的問題，應具有的另一個基本要素是子問題的重疊性質。在用遞歸算法自頂向下解此問題時，每次產生的問題并不總是新問題，有些子問題被反復計算多次。動態規劃算法正是利用了這種問題的重疊性質，對每個子問題只解一次，然后將其解保存在一個表格中，當再次需要解此子問題時，只是簡單地用常數時間查看所保存的結果即可。圖8-5計算A[1:4]的遞歸樹

3.備忘錄方法

動態規劃算法的一個變形是備忘錄方法。備忘錄方法使用一個表格記錄已解決子問題的結果，在下次需要解此子問題時，只須察看該子問題的結果，而不必重新計算。與動態規劃不同的是備忘錄方法的遞歸方式是自頂向下，而動態規劃算法則是自底向上的。因此，備忘錄方法的控制結構與直接遞歸方法的控制結構相同，區別在于備忘錄方法為每個解過的子問題建立備忘錄，避免了相同子問題的重復求解。8.2.2動態規劃應用之圖像壓縮

在計算機中常用像素點的灰度值序列{p0，p1，…，pn-1}表示圖像，其中整數pi(0≤i≤n-1)表示像素點i的灰度值。通常灰度值的范圍是0～255，因此需要用8個比特表示一個像素。

圖像的變位壓縮存儲格式是將所給的像素點序列{p0，p1，…，pn-1}分割成m個連續段S0，S1，…，Sm-1，第i個像素段Si(0≤i≤m-1)中有l[i]個像素，且該段中每個像素都由b[i]位表示。設t[i]=

(0≤i≤m-1)，則第i個像素段Si={pt[i],

…，pt[i]+l[i]-1}(0≤i≤m-1)。

設hi=?，則hi≤b[i]≤8，因此需要3個比特表示b[i](0≤i≤m-1)。如果限制1≤l[i]

≤255，則需要8個比特表示l[i](0≤i≤m-1)。這樣，第i個像素段所需的存儲空間為l[i]*b[i]+11比特，像素序列{p0，p1,

…，pn-1}所需的存儲空間為。圖像壓縮問題要求確定像素序列{p0，p1，…，pn-1}的一個最優分段，使得依此分段所需的存儲空間最少。其中，0≤pi≤255，0≤i≤n-1，每個分段的長度不超過256位。

(1)最優子結構。

設l[i]和b[i](0≤i≤m-1)是{p0，p1，…，pn-1}的一個最優分段，顯而易見，l[1]?和b[1]是{p0，p1，…，pl[1]-1}的一個最優分段，且l[i]?和b[i](1≤i≤m-1)是{pl[i]，pl[i]+1，…，pn-1}的一個最優分段，即圖像壓縮問題滿足最優子結構性質。

(2)遞歸計算最優值。

設s[i](0≤i≤m-1)是{p0，p1，…，pn-1}的最優分段所需的存儲位數，由最優子結構性質可知：

(8-7)

其中，bmax(i，j)=。

(3)構造最優解。

Compress算法中用l[i]和b[i]記錄了最優分段所需的信息，最優分段最后一個段的段長度和像素位數存儲于l[i]

和b[i]中，其前一段的段長度和像素位數存儲于l[n-l[n]]和

b[n-b[n]]中，依次類推，由計算得出的l[i]和b[i]可在時間

復雜度為O(n)以內構造出相應的最優解。

(4)計算復雜度。

Compress算法需要的空間復雜度為O(n)。

由于Compress算法中對j的循環次數不超過256，因此

對每一個確定的i，可在時間復雜度為以O(1)內完成

的計算，最終整個算法所需的計算時間復雜度為O(n)。8.2.3動態規劃應用之最優二叉搜索樹

設S={x1，x2，…，xn}是一個有序集，且x1＜x2＜…＜xn。有序集S的二叉搜索樹，利用二叉樹的結點存儲有序集中的元素，它具有下述性質：存儲于每個結點中的元素，大于其左子樹中任意結點所存儲的元素，小于其右子樹中任意結點所存儲的元素。二叉搜索樹的葉子結點是形如(xi，xi+1)的開區間。在表示S的二叉搜索樹中搜索一個元素x，其返回的結果有兩種情況：

(1)在二叉搜索樹的內結點中找到x=xi。

(2)在二叉搜索樹的內結點中確定。設在第一種情況中找到元素x的概率是bi，在第二種情況中確定的概率是ai，其中約定,

。顯然有

(8-8)

其中，(a0，b1，a1，…，bn，an)稱為集合S的存取概率分布。在表示S的二叉搜索樹T中，設存儲元素xi的結點深度為ci，葉子結點的深度為dj，則

(8-9)

其中，p表示在二叉搜索樹T中做一次搜索所需的平均比較次數，也稱為二叉搜索樹T的平均路長。一般情況下，不同二叉搜索樹的平均路長是不同的。

最優二叉搜索樹問題是有序集S及其存取概率分布(a0，b1，a1，…，bn，an)在所有表示有序集S的二叉搜索樹中，找出一棵具有最小平均路長的二叉搜索樹。

(1)最優子結構性質。

含有結點xi，…，xj和葉子結點(xi-1，xi)，…，(xj，xj+1)的二叉搜索樹T，可以看做是有序集{xi，…，xj}關于全集{xi-1，…，xj+1}的一棵二叉搜索樹，其存取概率是下面的條件概率：

(8-10)設Ti,j是有序集{xi，…，xj}關于存取概率

的一棵最優二叉搜索樹，其平均路長為pi,j；Ti,j的根結點存儲元素為xm，其左子樹Tl和右子樹Tr的平均路長分別為pl和pr。由于Tl和Tr中結點深度是它們在Ti,j中結點深度減去1，因此

(8-11)由于Tl是關于集合{xi，…，xm-1}的一棵二叉搜索樹，因此pl≥pi，m-1。若pl＞pi，m-1，則用Ti，m-1替換Tl可得到平均路長比Ti，j更小的二叉搜索樹，這與Ti，j是最優二叉搜索樹相矛盾，故Tl是一棵最優二叉搜索樹。同理可得，Tr也是一棵最優二叉搜索樹。因此，最優二叉搜索樹問題具有最優子結構性質。

(2)遞歸計算最優值。

設最優二叉搜索樹Ti,j的平均路長為pi,j，所求的最優值為p1，n。由最優二叉搜索樹的最優子結構性質可建立計算

pi,j的遞歸式如下：初始時pi,i-1=0，1≤i≤n。記wi,jpi,j為m(i，j)，則m(1，n)=w1,np1,n=p1,n為所求的最優值。

計算m(i，j)的遞歸式為

(8-12)

(3)構造最優解。

在OptimalBinarySearchTree算法中，用s[i][j]保存了最優子樹Ti,j根結點中的元素，當s[1][n]=k時，xk為所求二叉搜索樹的根結點元素；其左子樹為T1,k-1，因此i=s[1][k-1]?表示T(1,k-1)的根結點元素為xi；依次類推，由s中的信息可以在時間復雜度為O(n)以內構造出所求的最優二叉搜索樹。

(4)計算復雜度。

在OptimalBinarySearchTree算法中用到三個數組分別為m、s和w，故該算法所需的空間復雜度為O(n2)，它的主要計算量在于計算{m(i,k-1)+m(k+1,j)}的值。對于固定的r，它所需要的計算時間復雜度為O(j-i+1)=O(r+1)，因此該算法所耗費的總時間復雜度為。可以證明：

8.3貪心算法

當一個問題具有最優子結構性質時，可以用動態規劃算法求解，但有時會有更簡單有效的算法。例如，假設有四種硬幣，它們的面值分別是五角、一角、五分和一分，現在找給某顧客四角七分錢，該如何找零，誰都會！硬幣找零的計算方法實質上稱為貪心算法，其基本思想是：總是做出在當前看來是最好的選擇，即貪心算法并不從整體最優上考慮，而只考慮當前(局部)最優。硬幣找零的計算結果是整體(全局)最優解，但貪心算法的解并不都是最優的，可以認為是最優解的近似解。

活動安排問題是可以用貪心算法求解的一個很好的例子，該問題要求高效地安排一系列占用某一個公共資源的活動。8.3.1貪心算法與動態規劃算法的差異

在動態規劃算法中，每步所做出的選擇往往依賴于相關子問題的解，因此只有在求出相關子問題的解以后才能做出選擇。而貪心算法所做的貪心選擇是僅在當前狀態下做出的最好選擇，即局部最優選擇；然后再求解做出該選擇后所產生的相應子問題的解，即貪心算法所做出的貪心選擇可以依賴于“過去”所做出的選擇，但絕不依賴于將來所做出的選擇，也不依賴于子問題的解。貪心算法和動態規劃算法都具有最優子結構性質。下面通過事例說明這兩者之間的差別。

(1)?0-1背包問題。

(2)背包問題。圖8-60-1背包問題和背包問題差異之實例說明8.3.2貪心算法應用之哈夫曼編碼

哈夫曼編碼是用于數據文件壓縮的一個十分有效的編碼方法，它利用一個字符在文件中出現的頻率建立一個用0-1串表示各個字符的最優表示方法。

假設有一個數據文件包含100000個字符，其中共有六個字符形式，每個字符出現的頻率如表8-1所示。問題是：如何采用壓縮存儲方式存儲該文件。譯碼過程必須方便地獲取編碼的前綴，因此需要一個表示前綴碼的合適的數據結構，為此采用二叉樹作為表示前綴編碼的數據結構。在二叉樹中，葉子代表給定的字符，并將每個字符的前綴碼看做是從根到代表該字符的葉子的一條路經，代碼中的每一位0或1分別作為指示某結點到左孩子或右孩子的“路標”。例如，圖8-7中的兩棵樹分別表示表8-1中的編碼方案所對應的數據結構。圖8-7前綴碼的二叉樹表示給定編碼字符集C及其頻率分布f，C的一個前綴碼編碼方案對應一個二叉樹T，字符c∈C在樹T中的深度記為dT(c),其中dT(c)也是字符c的前綴碼長。該編碼方案的平均碼長定義為

(8-13)

使平均碼長達到最小的前綴編碼稱為C的一個最優前綴碼。下面考慮哈夫曼編碼的正確性。只要能夠證明最優前綴碼問題具有貪心選擇性質和最優子結構性質，就可以證明哈夫曼編碼是正確的。

(1)證明最優子結構性質。

設T表示字符集C的一個最優前綴碼的二叉樹，C中字符c的出現頻率為f(c)，x和y是樹T中的兩個兄弟葉子，z是x和y的雙親，若將z看做頻率為f(z)=f(x)+f(y)的字符，則樹T'=T-{x,y}表示字符集C'=C-{x,y}∪{z}的一個最優前綴碼。證明：T的平均碼長用T‘的碼長表示。

對于任意c∈C-{x,y}，有dT(c)=dT’(c)，故f(c)dT(c)=

f(c)dT‘(c)。另外，dT(x)=dT(y)=dT’(z)+1，故：

f(x)dT(x)+f(y)dT(y)=(f(x)+f(y))(dT‘(z)+1)

=f(x)+f(y)+f(z)dT’(z)

(8-14)

因此，B(T)=B(T')+f(x)+f(y)。若T'所表示的字符集C'的前綴碼不是最優的，則有T“?表示的C'?的前綴碼使得B(T'')<B(T')。由于將z看做C'中的一個字符，因此z在T“中是樹葉。若將x和y加入樹T''中作為z的孩子，則得到字符集C的前綴碼的二叉樹T'''，且有

(8-15)

這與T是最優前綴碼相矛盾，故T'所表示的前綴碼也是最優的。

(2)證明貪心選擇性質。

設C是編碼字符集，C中字符c的頻率為f(c)，x和y是C中具有最小頻率的兩個字符，則存在C的一個最優前綴碼使x和y具有相同的碼長且它們的最后一位編碼不同。

設二叉樹T表示C的任意一個最優前綴碼，我們要證明在對T做適當修改后可以得到一棵新的二叉樹T'，使得在新樹中x和y是最深葉子且互為兄弟，同時新樹T'表示的前綴碼也是C的一個最優前綴碼。如果能做到這一點，則x和y在T'表示的前綴碼中具有相同的碼長且僅最后一位編碼不同。證明：設b和c是二叉樹T的最深葉子且為兄弟，不失一般性，設f(b)≤f(c)，f(x)≤f(y)。由于x和y是C中具有最小頻率的兩個字符，因此f(x)≤f(b)，f(y)≤f(c)。

將樹T中的葉子x和b交換得到樹T‘，再將y和c交換得到樹T"，則