算法設(shè)計(jì)技巧與分析 算法分析的基本方法

2024/3/21Algorithms:

DesignTechniquesandAnalysis

算法設(shè)計(jì)技巧與分析1課程信息

學(xué)習(xí)目標(biāo)熟悉算法分析的常用方法掌握算法設(shè)計(jì)的基本方法——分治法、貪心法、動態(tài)規(guī)劃法、回溯法等熟悉計(jì)算機(jī)科學(xué)中經(jīng)常出現(xiàn)的某些問題的精巧求解算法

——例如，快速排序算法、求最小生成樹的prim算法等等初步具有能針對所給實(shí)際問題來設(shè)計(jì)和實(shí)現(xiàn)算法，以及評價算法的能力。逐步養(yǎng)成對于所要解決的問題，總是努力去設(shè)計(jì)出盡可能好的算法的良好習(xí)慣2課程信息教學(xué)方式課堂講授（50學(xué)時）上機(jī)實(shí)驗(yàn)（6學(xué)時）考核方法期末閉卷考試70%實(shí)驗(yàn)作業(yè)30%3課程信息教材與教學(xué)參考資源教材：《算法設(shè)計(jì)技巧與分析》，電子工業(yè)出版社，2004.(Algorithms:DesignTechniquesandAnalysis,M.H.Alsuwaiyel)4課程信息教材與教學(xué)參考資源參考教材：[1]

算法導(dǎo)論（第二版影印版）高等教育出版社

,2007(IntroductiontoAlgorithms(SecondEdition),theMITPress,2001)

[2]計(jì)算機(jī)算法設(shè)計(jì)與分析，王曉東，電子工業(yè)出版社，2001。5課程主要學(xué)習(xí)內(nèi)容1.算法分析的基本方法2.算法設(shè)計(jì)的基本方法

分治法動態(tài)規(guī)劃法貪心法回溯法分枝限界法3.算法設(shè)計(jì)的其它方法6

1.

算法分析的基本方法1.1.算法及其特性1.2.衡量一個算法性能的好壞的標(biāo)準(zhǔn)1.3.算法的時間和空間復(fù)雜度1.4.算法分析(AlgorithmAnalysis)1.4.1.分析算法時間復(fù)雜度的基本步驟1.4.2.算法時間復(fù)雜度的有關(guān)概念1.4.3.幾種典型算法舉例1.4.4.分析、求解算法復(fù)雜度的方法1.5.最優(yōu)算法(optimalalgorithm)7

1.1.算法及其特性算法（algorithm）：算法就是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類型問題的一系列運(yùn)算。算法的五個特性：確定性：組成算法的每條指令是清晰的，無歧義的。能行性：算法中的任何計(jì)算步都可以在有限時間內(nèi)完成。有窮性：算法必須能在執(zhí)行有限個步驟之后終止。輸入：有0個或多個由外部提供的量作為輸入。輸出：算法產(chǎn)生至少一個量作為輸出。8

1.2.

衡量算法性能的標(biāo)準(zhǔn)衡量算法性能一般有下面幾個標(biāo)準(zhǔn)正確性：算法能夠正確地完成所要解決的問題。易讀性：算法清晰易懂。健壯性：算法除了能對合法的輸入數(shù)據(jù)得到正確的結(jié)果外, 還應(yīng)對非法的輸入數(shù)據(jù)做出正確合理的處理。

算法的時間和空間性能：高效率和低存儲空間我們這里主要討論算法的時間和空間性能，并以此作為衡量算法性能的重要標(biāo)準(zhǔn)。而且我們主要側(cè)重于時間方面。9

1.3.算法的時間和空間復(fù)雜度時間復(fù)雜度（TimeComplexity）算法的時間復(fù)雜度：在算法運(yùn)行期間所花費(fèi)的時間。通常用漸進(jìn)形式表示比如，T(n)=

(n2)、

(n2)或

(n2)空間復(fù)雜度（SpaceComplexity）

算法的空間復(fù)雜度：在算法運(yùn)行期間所需要的內(nèi)存空間。一般是指，除開容納輸入數(shù)據(jù)之外的附加空間（auxiliaryspace,orworkspace）。通常用漸進(jìn)形式表示比如，S(n)=

(n2)、

(n2)或

(n2)10

1.4.算法分析(AlgorithmAnalysis)算法分析：對于算法的時間和空間復(fù)雜度進(jìn)行定量分析。分析算法時間復(fù)雜度的基本步驟算法時間復(fù)雜度的有關(guān)概念分析、求解算法復(fù)雜度的基本方法111.4.1.分析時間復(fù)雜度的基本步驟一、選取一種運(yùn)算作為基本運(yùn)算

二、表示出在算法運(yùn)行期間基本運(yùn)算執(zhí)行的總頻數(shù)三、漸近時間復(fù)雜度（asymptotictimecomplexity）12漸近表示的記號—O-記號設(shè)f(n)和g(n)均是從自然數(shù)集到非負(fù)實(shí)數(shù)集上的函數(shù)。如果存在常數(shù)c>0和一個自然數(shù)n0，使得對于任意的n

n0

，均有

f(n)

cg(n),

則f(n)=O(g(n))13漸近表示的記號—

-記號設(shè)f(n)和g(n)均是從自然數(shù)集到非負(fù)實(shí)數(shù)集上的函數(shù)。如果存在常數(shù)c>0和一個自然數(shù)n0，使得對于任意的n

n0

，均有

f(n)

cg(n),

則f(n)=

(g(n))14漸近表示的記號—

-記號設(shè)f(n)和g(n)均是從自然數(shù)集到非負(fù)實(shí)數(shù)集上的函數(shù)。如果存在一個自然數(shù)n0和兩個正常數(shù)c1，c2，使得對于任意的n

n0

，均有

c1g(n)

f(n)

c2

g(n),

則f(n)=

(g(n))15[例1]

設(shè)f(n)=10n2+20n。則有f(n)=O(n2)f(n)=

(n2)f(n)=

(n2)[例2]

設(shè)f(n)=aknk+ak-1nk-1+…+a1n+a0,(ak>0)。則有f(n)=O(nk)f(n)=

(nk)：f(n)=

(nk)

由此可見，復(fù)雜度的漸近表示可以簡潔地表示出復(fù)雜度的數(shù)量級別。漸近表示—Examples16漸近表示—Examples17漸近表示—Examples18漸近表示—Examples191.4.2.算法時間復(fù)雜度的有關(guān)概念

對于算法的時間復(fù)雜度，通常分平均、最壞、最好幾種情形來衡量，尤其是前兩種。算法的平均復(fù)雜性

算法的最壞復(fù)雜性算法的最好復(fù)雜性

201.4.2.算法時間復(fù)雜度的有關(guān)概念[例1]

檢索問題的順序查找算法以元素的比較作為基本操作?？紤]成功檢索的情況。最好情況下的時間復(fù)雜度：

(1)最壞情況下的時間復(fù)雜度：

(n)在等概率前提下，平均情況下的時間復(fù)雜度：

(n)[例2]

直接插入排序算法以元素的比較作為基本操作。最好情況下的時間復(fù)雜度：

(n)最壞情況下的時間復(fù)雜度：

(n2)在等概率前提下，平均情況下的時間復(fù)雜度：

(n2)211.4.3.幾種典型算法舉例二分搜索合并兩個已排序的表選擇排序插入排序自底向上合并排序22二分搜索問題：設(shè)A[1..n]為n個元素的數(shù)組，判定給定元素x是 否在A中。 即：尋找索引j，1≤j≤n，如果x在A中，有x=A[j]，否則j=0。算法1：掃描A中的所有項(xiàng)目，將每個項(xiàng)目與x比較，如果在j次比較后搜索成功，即x=A[j]，則返回j的值，否則返回0。這種方法稱為順序搜索或線性搜索。算法如下：23二分搜索如果A中的元素按升序排列，則有：24二分搜索25二分搜索算法分析算法分析 假定每個三向比較(if-then-else)記為一次比較，顯然最小的比較次數(shù)是1，即被搜索的元素x在序列的中間位置。 對于最大的比較次數(shù)，可以假定x大于等于將要搜索的序列中的所有元素。因此，第二次迭代A[mid+1…n]中元素恰好是。類似地，第三次迭代時，要搜索的剩余元素的數(shù)目是。依次類推，經(jīng)過j次循環(huán)后的剩余元素是。此時，或者找到x，或者要搜索的子序列的長度為1。故搜索x的最大循環(huán)數(shù)就是滿足條件=1時的j值。26二分搜索算法分析

根據(jù)底函數(shù)的定義，有 即 有:

因?yàn)閖是整數(shù)，可得：

27二分搜索算法分析定理1.1

對于一個大小為n的排序數(shù)組，算法BINARYSEARCH執(zhí)行比較的最大次數(shù)為 。28合并兩個已排序的表問題： 假定有一個數(shù)組A[1..m]，p,q,r為它的三個索引，并有1≤p≤q<r≤m，兩個子數(shù)組A[p…q]和A[q+1…r]各自按升序排列，要求重新安排A中元素的位置，使得子數(shù)組A[p…r]也按升序排列。29合并兩個已排序的表思路：

這其實(shí)就是合并A[p…q]和A[q+1…r]的過程。使用兩個指針s和t，初始化時各自指向A[p]和A[q+1]，再用一個空數(shù)組B[p…r]做臨時變量。每一次比較元素A[s]和A[t]，將小的元素添加到輔助數(shù)組B，如果相同就把A[s]添加進(jìn)行。然后更新指針，如果A[s]A[t]，則s加1，否則t加1，當(dāng)條件s=q+1或t=r+1成立時過程結(jié)束。在第一種情況下，我們把數(shù)組A[t…r]中剩余的元素添加到B，而在另一種情況下，把數(shù)組A[s…q]中剩余的元素添加到B。最后，把數(shù)組B[p…r]復(fù)制回A[p….r]。30合并兩個已排序的表31合并兩個已排序的表32合并兩個已排序的表33選擇排序思路

設(shè)A[1…n]為一個有n個元素的數(shù)組，選擇排序的思路如下：首先找到最小元素，將其存放在A[1]中，然后找到剩下的n-1個元素中的最小元素，將其存放在A[2]中，重復(fù)此過程直至找到第二大的元素，并將其存放在A[n-1]中。34選擇排序35選擇排序36插入排序思路

插入排序方法如下：從大小為1的子數(shù)組A[1]開始，它自然是排好序的，接下來將A[2]插入到A[1]的前面或后面，則取決于A[2]比A[1]小還是大。對于第i次執(zhí)行，依次掃描序號從i-1到1的元素，每次都將A[i]和當(dāng)前位置的元素比較。這樣，或者找到一個小于等于A[i]的元素，或者前面已排序數(shù)組的元素都已掃描過。此時，A[i]已被插入到合適的位置。37插入排序38插入排序39插入排序40自低向上合并排序例：假定要對如下8個數(shù)字的數(shù)組排序

可以按下面的方法進(jìn)行：41自低向上合并排序思路42自低向上合并排序43自低向上合并排序分析44自低向上合并排序分析45自低向上合并排序分析461.4.4.分析、求解算法復(fù)雜度的方法數(shù)學(xué)基礎(chǔ)典型的求和公式積分近似求和遞歸關(guān)系47典型的求和公式

0i

n

f(i)

1i

n

i=n(n+1)/2=

(n2)

1i

n

(a+bi)=na+bn(n+1)/2=

(n2)

1i

n

i2=n(n+1)(2n+1)/6=

(n3)

1i

n

ik=

(nk+1)

0i

n

ai=(1–an+1)/(1–a)=

(an)(a

1)

特別地，

0i

∞

ai=1/(1–a)(|a|<1)

0i

n

ai=

(1)(|a|<1)

0i

n

iai=

(nan)(a

1)48

積分近似求和如果連續(xù)函數(shù)f(n)是單調(diào)遞減的，則有

mn+1

f(x)

m

j

n

f(j)

m-1n

f(x)如果連續(xù)函數(shù)f(n)是單調(diào)遞增的，則有

m-1n

f(x)

m

j

n

f(j)

mn+1

f(x)49

積分近似求和[例1]

1

j

njk(k>1)50

積分近似求和51

積分近似求和[例2]

1

j

n

1/j=

(logn)52

積分近似求和53

積分近似求和[例3]

1

j

n

logj=

(nlogn)54

遞歸關(guān)系(I)線性齊次遞歸方程

T(n)=a1T(n-1)+a2T(n-2)+…+akT(n-k),(n

k)(II)線性非齊次遞歸方程

T(n)=a1T(n-1)+a2T(n-2)+…+akT(n-k)+f(n),(n

k)(III)分而治之型遞歸方程

T(n)=a1T(n/c1)+a2T(n/c2)+…+apT(n/cp)+f(n),(n>n0)55

遞歸關(guān)系

常用方法差分方程法展開法換元法數(shù)學(xué)歸納法56(I)線性齊次遞歸方程

T(n)=a1T(n-1)+a2T(n-2)+…+akT(n-k),n

k

初始條件（略）。

主要解法：差分方程法

遞歸關(guān)系57[例1]

f(n)=3f(n1)+4f(n2),n>1；初始條件：f(0)=1，f(1)=4

遞歸關(guān)系tn是遞歸方程的解(忽略初始條件)

t是對應(yīng)特征方程的根Step1Step2Step3Step4

特征方程為：t2

3t

4=0。解得t1=4,t2=

1。于是，f(n)=c1·4n+c2·(

1)n（n

0），其中c1,c2待定。所以，f(n)=4n

（n

0）解：

由f(0)=1,f(1)=4有：c1+c2=14c1

c2=4由此得c1=1,c2=0。58

遞歸關(guān)系[例2]

f(n)=4f(n

1)

4f(n

2),n>1；初始條件：f(0)=6,f(1)=8。解：

特征方程為：t2

4t+4=0。解得t1=t2=2。于是，f(n)=c1·2n+c2·n·2n

（n

0），其中c1，c2待定。由f(0)=6，f(1)=8有：c1=6，

2c1+2c2=8。由此得c1=6,c2=

2。所以，f(n)=3·2n+1

n·2n+1（n

0）59

遞歸關(guān)系(II)線性非齊次遞歸方程

T(n)=a1T(n-1)+a2T(n-2)+…+akT(n-k)+f(n),(n

k)

初始條件（略）。主要解法：差分方程法60

遞歸關(guān)系[例3]

T(n)=T(n-1)+T(n-2)+b,n>1，初始條件：T(1)=T(0)=a,這里a，b均為非負(fù)常數(shù)。tn是遞歸方程齊次部分的解

(忽略初始條件)

t是對應(yīng)特征方程的根解：

特征方程為：t2

t

1=0，解得t1=(1+51/2)/2,t2=(1

51/2)/2。顯然，T(n)=

b是方程的一個特解。于是，T(n)=c1·t1n+c2·t2n

b(n

0)

，其中c1，c2待定。由T(0)=a，T(1)=a有：c1+c2

b=a

c1·t1+c2·t2

b=a

由此得c1=？c2=？所以，T(n)=c1·t1n+c2·t2n

b

（n

0）其漸近表示為：T(n)=(((1+51/2)/2)n)Step1Step2Step3Step4Step561說明：與上例相關(guān)的一個算法例子是，F(xiàn)ibonacci數(shù)列的第n+1項(xiàng)該數(shù)列的定義為：

F0=F1=1,Fi=Fi-1+

Fi-2，i2。由這一數(shù)學(xué)定義自然地導(dǎo)出一個遞歸算法。

intF(intn){ if(n==0||n==1)return1;elseif(n>=2)returnF(n

1)+F(n

2);}

該算法計(jì)算時間T(n)滿足的遞歸方程呈上例形式。

遞歸關(guān)系62

[例4]河內(nèi)塔問題的遞歸求解算法如下(C++描述)：voidHanoi(intn,chara,charb,charc){if(n>0){ Hanoi(n

1,a,c,b);cout<<“MoveDiskNo.”<<n<<“fromPile”<<a<<“to”<<c<<endl;Hanoi(n

1,b,a,c);}}

遞歸關(guān)系63遞歸關(guān)系

使用輸出語句為基本操作。若用T(n)表示該算法的計(jì)算時間，則有

T(n)=2T(n

1)+1,n>1T(1)=1。

使用展開法、差分法或數(shù)學(xué)歸納法可得：

T(n)=2n

1,

即T(n)=(2n)。64(III)分而治之型遞歸方程

e.g.

f(n)=af(n/b)+g(n),n>1，初始條件：f(1)=c,這里的a,b,c均是正常數(shù)。說明：考慮這樣的遞歸過程：它把大小為n的問題分成了a個大小為n/b的子問題去解。設(shè)大小為1的問題需要c個單位時間，把a(bǔ)個子問題的解合并成原問題的解需要g(n)個單位時間。用f(n)表示大小為n的問題的計(jì)算時間，則得上述遞歸方程。

遞歸關(guān)系65[例5]

解遞歸方程

f(n)=2f(n/2)+bnlogn,n>1;

初始條件：f(1)=d

。其中b和d都是非負(fù)實(shí)數(shù)，n=2k。解法1：（展開法）令g(n)=bnlogn，則f(n)=f(2k)=2f(2k-1)+g(2k)=22f(2k-2)+2g(2k-1)+g(2k)……=2kf(20)+∑i=0k-12ig(2k-i)=2kd+∑i=0k-12i·b·2k-i·log2k–i=n·d+b·2k∑i=0k-1(k-i)

=n·d+b·n∑i=1ki

=n·d+b·n·k(k+1)/2

=n·d+b·n·logn·(logn+1)/2（注意：由n=2k

有k=logn）所以，

f