算法与程序设计课件

演算法與程式設計第1章演算法基礎學習要點:理解演算法的概念。理解什麼是程式，程式與演算法的區別和內在聯繫。掌握演算法的計算複雜性概念。掌握演算法漸近複雜性的數學表述。掌握用偽代碼描述演算法的方法。第1章演算法基礎1.1演算法（Algorithm）1.2演算法分析1.3演算法的運行時間1.1演算法(Algorithm)1.演算法的定義2.演算法的性質3.演算法的表示4.演算法舉例5.程式6.冒泡排序演算法7.演算法正確性證明演算法通常指可以用來解決的某一類問題的步驟，這些步驟必須是明確的和有效的，而且能夠在有限步之內完成的。1.演算法的定義一般來說，“用演算法解決問題”可以利用電腦幫助完成。1.1演算法(Algorithm)“演算法”的大陸中文名稱出自西元前1世紀成書的《周髀算經》；英文名稱Algorithm來自於9世紀波斯數學家al-Khwarizmi；歐幾裏得演算法被人們認為是史上第一個演算法。1.演算法的定義1.1演算法(Algorithm)2.演算法的性質1）可行性2）確定性3）有窮性4）有輸入資訊的說明5）有輸出結果的說明3.演算法的表示

描述演算法可以有不同的方式,常用的有自然語言、程式框圖、程式設計語言、偽代碼等.1.1演算法(Algorithm)可行性：演算法中描述的操作都可通過有限次的基本運算來實現。確定性：演算法中每個步驟含義明確，無二義性。有窮性：一個演算法必須保證在有限個操作步驟執行後終止。輸入：一個演算法應具有零個或多個輸入。輸出：一個演算法應具有一個或多個輸出。2.演算法的性質1.1演算法(Algorithm)自然語言就是人們日常使用的語言，可以是漢語或英語或其他語言。除了那些很簡單的問題外，一般不用自然語言描述演算法。（1）自然語言3.演算法的表示1.1演算法(Algorithm)1.1演算法(Algorithm)概念：偽代碼是用介於自然語言和電腦語言之間的文字和符號來描述演算法。特點：它如同一篇文章一樣，自上而下地寫下來。每一行(或幾行)表示一個基本操作。用處：適用於設計過程中需要反復修改時的流程描述。（2）偽代碼3.演算法的表示1.1演算法(Algorithm)偽代碼規則說明：見教材P3a）縮進形式表示塊結構，主要體現在迴圈和條件控制結構上。b）while,do-while,for迴圈結構，以及if-then-else條件結構採用類似高級語言中相應表示。c）符號“//”後是注釋部分。d）多重賦值表達為i←j←e。e）所有變數不經顯式說明均為局部變數。f）通過數組名後跟下標訪問數組元素；符號“..”表示數組中元素的範圍。A[i]A[i..j]3.演算法的表示1.1演算法(Algorithm)g）複合數據可以組織成由屬性或域組成的對象，通過功能變數名稱後跟方括號括住的對象名訪問某個特定域。Length[A]h）通過傳值將參數傳給一個過程；當傳遞一個對象時，只拷貝指向表示對象的數據的指針，不拷貝它的各個域。i）“and”和“or”是布爾運算符。j）break語句表示將控制轉移到含有break的最內層迴圈語句後面的第一條語句。3.演算法的表示令士兵從1～3報數，結果最後一個士兵報2；令士兵從1～5報數，結果最後一個士兵報3；令士兵從1～7報數，結果最後一個士兵報2；【例1】韓信點兵你能算出韓信至少有多少兵嗎？1.1演算法(Algorithm)4.演算法舉例【例1】韓信點兵1.列出除以3餘2的數：2，5，8，11，14，17，20，23，26…2.列出除以5餘3的數：3，8，13，18，23，28…3.這兩列數中，首先出現的公共數是8，3與5的最小公倍數是15。兩個條件合併成一個就是8＋15×整數，列出這一串數是8，23，38，…，4.列出除以7餘2的數

：9，16，23，30…5.得出符合題目條件的最小數是23。6.我們已把題目中三個條件合併成一個：被105除餘23的數。1.1演算法(Algorithm)4.演算法舉例【例1】韓信點兵演算法描述三人同行七十稀，五樹梅花廿一枝，七子團圓正半月，除百零五便得知。

這首詩的意思是：用3除所得的餘數乘上70，加上用5除所得餘數乘以21，再加上用7除所得的餘數乘上15，結果大於105就減去105的倍數，這樣就知道所求的數了。1.1演算法(Algorithm)4.演算法舉例最初記述這類演算法的是一本名叫《孫子算經》的書。這類演算法的名稱也很多，宋朝周密叫它“鬼穀算”，又名“隔牆算”；楊輝叫它“剪管術”；而比較通行的名稱是“韓信點兵”。這在數學史上是極有名的問題，外國人一般把它稱為“中國剩餘定理”。【例1】韓信點兵1.1演算法(Algorithm)4.演算法舉例【點評】瞭解一些經典演算法是我們的學習目標。

【例2】

求1+2+3+4+5+6累加和演算法1.按照逐一相加的演算法進行.第一步:計算1+2,得3;第二步:將第一步中的運算結果3與3相加得6;第三步:將第二步中的運算結果6與4相加得10;第四步:將第三步中的運算結果10與5相加得15;第五步:將第四步中的運算結果15與6相加得21.4.演算法舉例太繁瑣1.1演算法(Algorithm)演算法2.可以運用下麵公式直接計算.第一步:取n=6;第二步:計算;第三步:輸出計算結果.【點評】演算法1繁瑣,步驟較多;演算法2簡單，步驟較少。找出好的演算法是我們的學習目標。4.演算法舉例

【例2】

求1+2+3+4+5+6累加和1.1演算法(Algorithm)4.演算法舉例【例3】

求1×2×3×4×5S1：先求1×2，得到結果2S2：將步驟1得到的乘積2再乘以3，得到結果6S3：將6再乘以4，得24S4：將24再乘以5，得120如果要求1×2×…×1000，則要寫999個步驟太繁瑣1.1演算法(Algorithm)

S1：令p=1S2：令i=2S3：計算p×i，乘積仍放在變數p中，可表示為：p=p×iS4：i的值加1，即i=i+1。S5：如果i不大於5，返回重新執行步驟S3以及其後的步驟S4和S5；否則，演算法結束。最後得到p的值就是結果。4.演算法舉例【例3】

求1×2×3×4×51.1演算法(Algorithm)

如果題目改為：求1×3×5×……×1000：S1：p=1S2：i=3S3：p=p×iS4：i=i+2S5：若i≤1000，返回S3。否則，結束。演算法簡練4.演算法舉例1.1演算法(Algorithm)Jiechen(n)p←1i←2whilei<=ndop←p*ii=i+1returnpLianchen(n)p←1i←3whilei<=ndop←p*ii=i+2returnp*n4.演算法舉例1.1演算法(Algorithm)5.程式（program）程式是演算法用某種程式設計語言的具體實現。程式可以不滿足演算法的性質(3)。例如操作系統，是一個在無限迴圈中執行的程式，因而不是一個演算法。史上第一次編寫程式是AdaByron於1842年為巴貝奇分析機編寫求解伯努利方程的程式，因此AdaByron被大多數人認為是世界上第一位程式員。1.1演算法(Algorithm)6.冒泡排序（bubblesort）（1）自然語言描述將相鄰的兩個元素進行比較，如果左邊的元素大於右邊元素值，則將這兩個元素進行交換，否則不改變位置，重複這個過程，直到比較到最後一個元素為止。1.1演算法(Algorithm)6.冒泡排序（bubblesort）（2）偽代碼描述BUBBLE-SORT(A)1fori←1tolength[A]2doforj←lenth[A]downtoi+13doifA[j]<A[j-1]4thenexchangeA[j]↔A[j-1]1.1演算法(Algorithm)6.冒泡排序（bubblesort）【例】已知序列A={5，2，4，6，1，3}1524

631253

461235

4612345

612345

6用程式如何描述冒泡排序演算法？1.1演算法(Algorithm)6.冒泡排序（bubblesort）voidbubblesort(intA[],intn){inti,j,temp;for(i=0;i<n;i++)for(j=n-1;j>i;j--)if(A[j]<A[j-1]){temp=A[j];A[j]=A[j-1];A[j-1]=temp;}}1.1演算法(Algorithm)（3）程式描述7.演算法正確性證明迴圈中始終為真值的部分被稱為迴圈不變式。利用迴圈不變式的結果可以證明演算法的正確性。迴圈不變式1.1演算法(Algorithm)1.2演算法分析

演算法分析是對一個演算法所需的計算資源進行預測。最重要的計算資源是時間和空間資源。時間和空間資源=演算法複雜度演算法的時間複雜度T(n)；（所需時間資源）演算法的空間複雜度S(n)。（所需空間資源）其中n是問題的規模（輸入大小）。[注]不特別說明情況下，對演算法只分析時間複雜度。1.2演算法分析1.演算法分析的基本法則2.

冒泡排序演算法分析3.不同情況下的演算法時間複雜度1.演算法分析的基本法則（1）for/while迴圈循環體內計算時間*迴圈次數；（2）嵌套迴圈循環體內計算時間*所有迴圈次數；（3）順序語句各語句計算時間相加；（4）if-else語句if語句計算時間和else語句計算時間的較大者。1.2演算法分析2.

冒泡排序演算法分析BUBBLE-SORT(A)cost

1fori←1tolength[A]c12doforj←lenth[A]downtoi+1c13doifA[j]<A[j-1]c24thenexchangeA[j]↔A[j-1]c31.2演算法分析timesn+1sum(n-i+1)sum(n-i)ti3.不同情況下的演算法時間複雜度（1）最壞情況下的時間複雜度Tmax(n)=max{T(I)|size(I)=n}（2）最好情況下的時間複雜度

Tmin(n)=min{T(I)|size(I)=n}（3）平均情況下的時間複雜度

Tavg(n)=

其中I是問題的規模為n的實例，p(I)是實例I出現的概率。1.2演算法分析3.不同情況下的演算法時間複雜度BUBBLE-SORT(A)cost

1fori←1tolength[A]c12doforj←lenth[A]downtoi+1c13doifA[j]<A[j-1]c24thenexchangeA[j]↔A[j-1]c31.2演算法分析timesn+1sum(n-i+1)sum(n-i)ti演算法最壞情況下的運行時間是任一輸入運行時間的上界並且經常出現，所以對一個演算法我們關心的是最壞情況下的時間複雜度。3.不同情況下的演算法時間複雜度1.2演算法分析1.3演算法的運行時間1.演算法漸近複雜性2.漸近表示3.演算法分析中常見的複雜性函數4.演算法分類1.3演算法的運行時間T(n)

,asn

;(T(n)-t(n))/T(n)0

，asn;稱t(n)是T(n)的漸近性態，為演算法的漸近複雜度。在數學上，t(n)是T(n)的漸近運算式，是T(n)略去低階項留下的主項。它比T(n)簡單。1.演算法漸近複雜性1.演算法漸近複雜性舉例：T（N）=3N2+4NlogN+7t（N）=3N21.3演算法的運行時間2.漸近表示在下面的討論中，對所有n，f(n)

0，g(n)

0。（1）漸近上界記號OO(g(n))={f(n)|存在正常數c和n0使得對所有n

n0有：0

f(n)

cg(n)}（2）漸近下界記號

(g(n))={f(n)|存在正常數c和n0使得對所有n

n0有：0

cg(n)

f(n)}1.3演算法的運行時間（3）緊漸近界記號

(g(n))={f(n)|存在正常數c1,c2和n0使得對所有n

n0有：c1g(n)

f(n)

c2g(n)}

2.漸近表示1.3演算法的運行時間3.演算法分析中常見的複雜性函數1.3演算法的運行時間小規模數據大規模數據4.演算法分類多項式時間演算法（polynomialtimealgorithm)：用多項式來對計算時間限界的演算法。O(1)<O(lbn)<O(n)<O(nlbn)<O(n2)<O(n3)指數時間演算法（exponentialtimealgorithm)：計算時間用指數函數限界的演算法。O(2n)<O(n!)<O(nn)1.3演算法的運行時間第1章演算法基礎學習要點:理解演算法的概念。理解什麼是程式，程式與演算法的區別和內在聯繫。掌握演算法的計算複雜性概念。掌握演算法漸近複雜性的數學表述。掌握用偽代碼描述演算法的方法。練習1.下麵的程式段違反了演算法的()原則。

voidsam()

{intn=2;

while(!odd(n))n+=2;

printf(n);

}A.有窮性B.確定性C.可行性D.健壯性練習2.下面函數中漸進時間最小的是()。A.T1(n)=n+nlogn

B.T2(n)=2n+nlogn

C.T3(n)=n2-logn

D.T4(n)=n+100logn3.下述函數中漸進時間最小的是()。A.T1(n)=nlog2n+100log2n

B.T2(n)=2nlog2n-100log2n

C.T3(n)=n2-100log2n

D.T4(n)=4nlog2n-100log2n51第2章分治法2.1遞歸2.2分治法2.3分治法應用實例遞推與遞歸報數問題一隊士兵從排頭向排尾報數是一個遞推問題an=an-1+1如果要求從排尾向排頭報數呢？要求排頭報數為1是一個遞歸問題an=an-1+1a1=1德羅斯特效應德羅斯特效應（Drosteeffect）是指一張圖片的某個部分與整張圖片相同，如此產生無限迴圈。它是遞歸的一種視覺形式。2.1遞歸

2.1.1遞歸的概念【定義】若一個對象部分地包含它自己，或用它自己給自己定義，則稱這個對象是遞歸的；若一個過程直接地或間接地調用自己，則稱這個過程是遞歸的過程。2.1.1遞歸的概念2.1.1遞歸的概念二叉樹：二叉樹是數據元素的有窮集合，它或者為空集（空二叉樹），或者由一個根元素和其下的兩棵互不相交的二叉左子樹和右子樹構成。單鏈表結點：

typedefstructnode {datatypedata

structnode*Link; }slnode2.1.2遞歸的應用能採用遞歸解決的問題通常有這樣的特徵：為求解規模為N的問題，設法將它分解成一些規模較小的問題，這些規模較小的問題也能採用同樣的分解和綜合方法，分解為規模更小的問題，當N=1時，能直接得到解。下麵來看幾個實例。582.1.2遞歸的應用【例1】階乘函數

階乘函數可遞歸地定義為：邊界條件遞歸方程邊界條件與遞歸方程是遞歸的二個要素59【例1】階乘函數Factorial(n)ifn=0thenreturn1returnn*Factorial(n-1)Factorial(n)fn=f1=1fori←2tondofn=i*f1f1=fnreturnfn2.1.2遞歸的應用2.1.2遞歸的應用【例2】Fibonacci數列無窮數列1，1，2，3，5，8，13，21，34，55，……，稱為Fibonacci數列。它可以遞歸地定義為：邊界條件遞歸方程第n個Fibonacci數可遞歸地計算如下：

fibonacci(n)if(n<=1)thenreturn1returnfibonacci(n-1)+fibonacci(n-2)

斐波那契數列的遞歸調用樹Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)2.1.2遞歸的應用遞歸演算法的一般形式：p(參數表)if（遞歸結束條件）可直接求解步驟；-----邊界條件

elsep（較小的參數）；------遞歸方程2.1.2遞歸的應用【例3】整數劃分問題將正整數n表示成一系列正整數之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整數n的這種表示稱為正整數n的劃分。例如，正整數6有如下不同的劃分：

6；

5+1；

4+2，4+1+1；

3+3，3+2+1，3+1+1+1；

2+2+2，2+2+1+1，2+1+1+1+1；

1+1+1+1+1+1。整數劃分問題：求正整數n的不同劃分個數。

64(2)q(n,m)=q(n,n),mn;最大加數n1實際上不能大於n。因此，q(1,m)=1。(1)q(n,1)=1,n1;當最大加數n1不大於1時，任何正整數n只有一種劃分形式，即

(4)q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;正整數n的最大加數n1不大於m的劃分由n1=m的劃分和n1≤m-1的劃分組成。(3)q(n,n)=1+q(n,n-1);正整數n的劃分由n1=n的劃分和n1≤n-1的劃分組成。2.1.2遞歸的應用【例3】整數劃分問題如果設p(n)為正整數n的劃分數，難以找到遞歸關係。因此考慮增加一個引數：將最大加數n1不大於m的劃分個數記作q(n,m)。可以建立q(n,m)的如下遞歸關係。2.1.2遞歸的應用【例3】整數劃分問題如果設p(n)為正整數n的劃分數，難以找到遞歸關係。因此考慮增加一個引數：將最大加數n1不大於m的劃分個數記作q(n,m)。可以建立q(n,m)的如下遞歸關係。正整數n的劃分數p(n)=q(n,n)。

2.1.2遞歸的應用【例4】Hanoi塔問題

設A,B,C是3個塔座。開始時，在塔座A上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,…,n,現要求將塔座A上的這一疊圓盤移到塔座C上，並仍按同樣順序疊置。在移動圓盤時應遵守以下移動規則：規則1：每次只能移動1個圓盤；規則2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；規則3：在滿足移動規則1和2的前提下，可將圓盤移至A,B,C中任一塔座上。2.1.2遞歸的應用【例4】Hanoi塔問題hanoi(n,A,B,C)ifn=1thenmove(A,1,C)elsehanoi(n-1,A,C,B)move(A,n,C)hanoi(n-1,B,A,C)

2.1.2遞歸的應用當n=1時，問題比較簡單。此時，只要將編號為1的圓盤從塔座A直接移至塔座C上即可。當n＞1時，①借C塔將A上的n-1盤子移到B塔座上；②將A上的第n個盤子移到C塔座上；③借A塔將B上的n-1盤子移到C塔座上。由此可見，n個圓盤的移動問題可分為2次n-1個圓盤的移動問題，這又可以遞歸地用上述方法來做。69運行過程：⑴只有一個盤子的情況：(最簡1步)⒈A---->C⑵有二個盤子的情況：(最簡3步)⒈A---->B⒉A---->C⒊B---->C⑶有三個盤子的情況：(最簡7步)⒈A---->C⒌B---->A⒉A---->B⒍B---->C⒊C---->B⒎A---->C⒋A---->C

2.1.2遞歸的應用⑶有四個盤子的情況：(最簡15步)

不同的盤子數運行步驟是不一樣的，它是以一種2N-1的規律來遞增的。於是所以我們得出h(n)=2N-1，當n=64時，需要的時間為18446744073709551615=5849億年2.1.2遞歸的應用2.1.2遞歸的應用

漢諾塔演算法的時間複雜度計算公式如下：【例4】Hanoi塔問題該遞歸方程的解為O(2n)。遞歸小結優點：結構清晰，可讀性強，而且容易用數學歸納法來證明演算法的正確性，因此它為設計演算法、調試程式帶來很大方便。缺點：遞歸演算法的運行效率較低，無論是耗費的計算時間還是佔用的存儲空間都比非遞歸演算法要多。將要求解的較大規模的問題分割成k個更小規模的子問題。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=2.2分治法2.2.1分治法的基本思想2.2.1分治法的基本思想對這k個子問題分別求解。如果子問題的規模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規模足夠小，很容易求出其解為止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)2.2.1分治法的基本思想將求出的小規模的問題的解合併為一個更大規模的問題的解，自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)2.2.1分治法的基本思想將求出的小規模的問題的解合併為一個更大規模的問題的解，自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)

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

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

凡治眾如治寡，分數是也。

----孫子兵法2.2.2分治法的適用條件分治法所能解決的問題一般具有以下幾個特徵：該問題的規模縮小到一定的程度就可以容易地解決；該問題可以分解為若干個規模較小的相同問題；利用該問題分解出的子問題的解可以合併為該問題的解；該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。因為問題的計算複雜性一般是隨著問題規模的增加而增加，因此大部分問題滿足這個特徵。這條特徵是應用分治法的前提，它也是大多數問題可以滿足的，此特徵反映了遞歸思想的應用能否利用分治法完全取決於問題是否具有這條特徵，如果具備了前兩條特徵，而不具備第三條特徵，則可以考慮貪心演算法或動態規劃。這條特徵涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重複地解公共的子問題，此時雖然也可用分治法，但一般用動態規劃較好。DIVIDE&CONQUER(P)if(|P|<=c)thenreturnDSOLVE(P)//解決小規模的問題

elsedividePintoksmallersubinstancesP1,P2,...,Pk

//分解問題

fori←1tokdosi←DIVIDE&CONQUER(Pi)//遞歸的解各子問題

S←COMBINE(s1,...,sk)//將各子問題的解合併為原問題的解

returnS}2.2.3分治法的基本步驟將一個問題分成大小相等的k個子問題的處理方法出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規模不等的做法要好。792.2.4分治法的複雜性分析用分治法求解一個問題，所需的時間是由四部分組成：（1）子問題的個數k；（2）子問題的大小n/m；（3）把這個問題分解為子問題所需時間f(n)；（4）子問題合併為原問題所需時間f(n)。

當n等於m的冪時，通過迭代法求得該遞歸方程的解：2.2.4分治法的複雜性分析2.2.4分治法的複雜性分析對於T(n)=a*T(n/b)+c*nk;T(1)=c這樣的遞歸關係，有這樣的結論：當(a>bk)

T(n)=O(n^(logb(a)));

当(a=bk)

T(n)=O(nk*logn);

當(a<bk)

T(n)=O(nk);2.3分治法應用實例由分治法產生的子問題往往是原問題的較小模式，反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。分治與遞歸像一對孿生兄弟，經常同時應用在演算法設計之中，並由此產生許多高效演算法。下麵來看幾個實例。83【例1】二叉查找演算法給定已按昇冪排好序的n個元素a[1:n]，現要在這n個元素中找出一特定元素v。若找到了返回在表中的位置；否則返回NIL表示查找不成功。分析：該問題的規模縮小到一定的程度就可以容易地解決；該問題可以分解為若干個規模較小的相同問題;分解出的子問題的解可以合併為原問題的解；分解出的各個子問題是相互獨立的。2.3.1二叉查找演算法842.3.1二叉查找演算法【實例】已知序列A={5，7，12，25，34，37，43，46，58，80，92，105}，要求查找v=46。第一步：設定i=1，j=12mid=└(i+j)/2┘=6v=46>A[mid]=37第二步：設定i=7,j=12mid=└(i+j)/2┘=9v=46<A[mid]=58第三步:設定i=7,j=8mid=└(i+j)/2┘=7v=46>A[mid]=43第四步：設定i=8,j=8mid=└(i+j)/2┘=8v=46=A[mid]=46返回8，找到。下取整若要查找35呢？【例1】二叉查找演算法偽代碼BinarySearch描述演算法：BinarySearch(A,v,low,high)whilelow<=highdomid←(low+high)/2ifv=A[mid]thenreturnmidelseifv>A[mid]thenlow←mid+1elsehigh←mid-1returnNIL演算法複雜度分析86【例1】二叉查找演算法A={5，7，12，25，34，37，43，46，58，80，92，105}二叉查找演算法的運行過程可以形成是一棵二叉判定樹。試一下運行過程，查找v=25v=5763124597128101158374392468010512572534在含有n個不同元素的集合中同時找出最大值和最小值。MAXMIN(A)max←min←A[1]fori←2tondoifA[i]>maxthenmax←A[i]elseifA[i]<minthenmin←A[i]returnmax&min2.3.2找最大值與最小值【例2】【問題】最好情況下，最壞情況下，時間複雜度是？【例2】找最大值與最小值將分治策略應用於此問題，每次將問題分解為大致相等的兩部分，分別找出最大最小值，再將這兩個子問題的解組合成原問題的解。當每個子序列只含有1個或2個元素時，視為分解結束。子序列依次兩兩合併找出較長序列的最大最小值，直到合併成原始序列。【例2】找最大值與最小值給定元素集A={5，4，6，3，8}用分治演算法找出最大值和最小值。第一步：i=1,j=5mid=(1+5)/2=3第二步：i=1,j=3mid=(1+3)/2=2第三步：i=1,j=2

比較一次得到gmax=5,gmin=4第四步：i=3,j=3得到hmax=hmin=6邊界第五步：i=1,j=3

比較gmax和hmax

比較gmin和hmin

得到fmax=6，fmin=4第六步：i=4，j=5

比較一次，得到hmax=8,hmin=3第七步：i=1，j=5

比較得到全序列fmax=8，fmin=3【例2】找最大值與最小值合併【例2】找最大值與最小值Rec_MAXMIN(i,j,fmax,fmin)ifi=jthenfmax←fmin←A[i]ifi=(j-1)thenif(A[i]>A[j])thenfmax←A[i]fmin←A[j]elsefmax←A[j]fmin←A[i]【例2】找最大值與最小值elsemid←(i+j)/2Rec_MAXMIN(i,mid,gmax,gmin)Rec_MAXMIN(mid+1,j,hmax,hmin)fmax←max(gmax,hmax)fmin←min(gmin,hmin)【例2】找最大值與最小值該演算法元素比較次數即時間複雜度遞歸方程為：2.3.3Strassen矩陣乘法【例3】兩個n×n的矩陣A和B的乘積矩陣C中的元素C[i,j]定義為:

依此定義來計算矩陣A和B的乘積矩陣C，則每計算C的一個元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩陣C的n2個元素所需的計算時間為O(n3)。矩陣相乘傳統方法：O(n3)【例3】Strassen矩陣乘法使用與上例類似的技術，將矩陣A，B和C中每一矩陣都分塊成4個大小相等的子矩陣。由此可將方程C=AB重寫為：傳統方法：O(n3)分治法:由此可得：复杂度分析T(n)=O(n3)【例3】Strassen矩陣乘法傳統方法：O(n3)分治法:為了降低時間複雜度，必須減少乘法的次數。复杂度分析T(n)=O(nlb7)=O(n2.81)较大的改进【例3】Strassen矩陣乘法【例3】Strassen矩陣乘法傳統方法：O(n3)分治法:O(n2.81)更快的方法??在Strassen之後又有許多演算法改進了矩陣乘法的計算時間複雜性。目前最好的計算時間上界是O(n2.376)是否能找到O(n2)的演算法？992.3.4整數相乘【例4】請設計一個有效的演算法，可以進行兩個n位整數的乘法運算小學的方法：O(n2)

效率太低分治法:X=Y=X=a10n/2+bY=c10n/2+d

XY=ac10n+(ad+bc)10n/2+bd

abcd複雜度分析T(n)=O(n2)

沒有改進【例4】整數相乘請設計一個有效的演算法，可以進行兩個n位大整數的乘法運算小學的方法：O(n2)

效率太低分治法:XY=ac10n+(ad+bc)10n/2+bd

為了降低時間複雜度，必須減少乘法的次數。XY=ac10n+((a-b)(d-c)+ac+bd)10n/2+bdXY=ac10n+((a+b)(c+d)-ac-bd)10n/2+bd複雜度分析T(n)=O(nlb3)=O(n1.59)

較大的改進細節問題：兩個XY的複雜度都是O(nlb3)，但考慮到a+c,b+d可能得到m+1位的結果，使問題的規模變大，故不選擇第2種方案。101【例4】整數相乘【例4】整數相乘請設計一個有效的演算法，可以進行兩個n位大整數的乘法運算小學的方法：O(n2)

效率太低分治法:O(n1.59)

較大的改進更快的方法??如果將大整數分成更多段，用更複雜的方式把它們組合起來，將有可能得到更優的演算法。最終的，這個思想導致了快速傅利葉變換(FastFourierTransform)的產生。該方法也可以看作是一個複雜的分治演算法。在一個2k×2k個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。覆蓋一個2k×2k棋盤要用到多少個L型骨牌？怎麼放置骨牌？2.3.5棋盤覆蓋【例5】當k>0時，將2k×2k棋盤分割為4個2k-1×2k-1子棋盤(a)所示。遞歸地使用這種分割，直至棋盤簡化為棋盤1×1。

【例5】棋盤覆蓋2.3.6歸並排序【例6】基本思想：將待排序元素分成大小大致相同的2個子集合，分別對2個子集合進行排序，最終將排好序的子集合合併成為所要求的排好序的集合。【例】已知初始序列如下：（49，38，65，97，76，13，27）請利用歸併排序讓其昇冪有序。【例6】歸並排序歸併的遞歸過程可以消去。初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]107【例6】歸並排序基本思想：將待排序元素分成大小大致相同的2個子集合，分別對2個子集合進行排序，最終將排好序的子集合合併成為所要求的排好序的集合。

MergeSort(A,p,r)if(p<r)//至少有2個元素

thenq←(p+r)/2//取中點

MergeSort(A,p,q)MergeSort(A,q+1,r)Merge(A,p,q,r)複雜度分析T(n)=O(nlbn)漸進意義下的最優演算法歸併兩個已排好序的子序列Merge(A,p,q,r)n1←q-p+1n2←r-qcreatearraysL[1..n1+1]andR[1..n2+1]fori←1ton1doL[i]←A[p+i-1]forj←1ton2doR[j]←A[q+j]L[n1+1]←∞R[n2+1]←∞i←1j←1歸併兩個已排好序的子序列fork←ptordoifL[i]<R[j]thenA[k]←L[i]i←i+1elseA[k]←R[j]j←j+1時間複雜度分析：Merge過程的運行時間O(n)歸並排序複雜性最壞時間複雜度：O(nlbn)平均時間複雜度：O(nlbn)輔助空間：O(n)【基本思想】對給定的初始數組a通常存在多個長度大於1的已自然排好序的子數組段，將這些自然有序子數組段找出來，然後將相鄰的排好序的子數組段兩兩合併，構成更大的排好序的子數組段；繼續合併相鄰排好序的子數組段，直至整個數組已排好序。自然歸並排序【例6】歸並排序【練習】利用歸併排序使序列A={5,2,4,7,1,3,2,6}昇冪有序。排序過程演示：S1:{5，2，4，7}{1，3，2，6}S2:{5，2}{4，7}{1，3}{2，6}S3:{5}{2}{4}{7}{1}{3}{2}{6}S4:{2，5}{4，7}{1，3}{2，6}S5:{2,4,5,7}{1,2,3,6}S6:{1,2,2,3,4,5,6,7}2.3.7快速排序【例7】【基本思想】對輸入的數組a[p:r]，按以下三個步驟進行排序：（2）遞歸求解：通過遞歸調用快速排序演算法分別對A[p:q-1]和A[q+1:r]進行排序。（3）合併：由於對A[p:q-1]和A[q+1:r]的排序是就地進行的，所以在A[p:q-1]和A[q+1:r]都已排好的序後不需要執行任何計算，A[p:r]就已排好序。（1）劃分：以A[r]（或A[p]）為基準元素將A[p:r]劃分為3段A[p:q-1],A[q]和A[q+1:r]，使得A[p:q-1]中任何一個元素小於等於A[q],A[q+1:r]中任何一個元素大於等於A[q]。下標q在劃分過程中確定。【例7】快速排序【例】初始序列｛38，14，58，26，31｝，請利用快速排序使其昇冪有序。【例7】快速排序在快速排序中，關鍵字較大的記錄一次就能交換到後面單元，關鍵字較小的記錄一次就能交換到前面單元，記錄每次移動的距離較大，因而總的比較和移動次數較少。QuickSort(A，p,r)if(p<r)q←Partition(A,p,r)QuickSort(A,p,q-1)//對左半段排序

QuickSort(A,q+1,r)//對右半段排序

【例7】快速排序

Partition(A，p,r)x←A[r]//基準元素i←p-1forj←ptor-1doifA[j]<=xtheni←i+1exchangeA[i]↔A[j]exchangeA[i+1]↔A[r]returni+1快速排序示例初始

[722657884280724860]1：[26574248]60[80728872]2：[2642]48[57]60[80728872]3：[26]42485760[80728872]4：2642485760[72]72[8088]5：2642485760[72]72[80]886：[264248576072728088]快速排序可能會對相等值的記錄改變相對順序，所以是不穩定排序演算法。【例7】快速排序快速排序演算法的性能取決於劃分的對稱性。通過修改演算法partition，可以設計出採用隨機選擇策略的快速排序演算法。最壞時間複雜度：O(n2)平均時間複雜度：O(nlbn)輔助空間：O(n)或O(lbn)RANDOMIZED-PARTITION(A,p,r)i←RANDOM(p,r)exchangeA[r]↔A[i]returnPARTITION(A,p,r)【例7】快速排序【練習】已知初始序列如下：（49，38，65，97，76，13，27）請利用快速排序讓其昇冪有序。2.3.8線性時間選擇【例8】【元素選擇問題】給定線性序集中n個互不相同元素和一個整數i，1≤i≤n，要求找出這n個元素中第i小的元素。【例】已知序列A={2,8,9,10,1,5,3,20,6,12,35,14,18},要求找出第8小元素。2.3.8線性時間選擇【例8】【元素選擇問題】給定線性序集中n個互不相同元素和一個整數i，1≤i≤n，要求找出這n個元素中第i小的元素。

RandomizedSelect(A,p,r,i)if(p==r)thenreturnA[p]q←RandomizedPartition(A,p,r)k=q-p+1ifi=kthenreturnA[q]elseif(i<k)thenreturnRandomizedSelect(A,p,q-1,i)elsereturnRandomizedSelect(A,q+1,r,i-k)在最壞情況下，演算法RandomizedSelect需要O(n2)計算時間但可以證明，演算法RandomizedSelect可以在O(n)平均時間內找出n個輸入元素中的第i小元素。方法一將n個輸入元素劃分成

n/5個組，每組5個元素，只可能有一個組不是5個元素。用任意一種排序演算法，將每組中的元素排好序，並取出每組的中位數，共n/5個。遞歸調用select來找出這n/5

個元素的中位數。如果

n/5

是偶數，就找它的2個中位數中較大的一個。以這個元素作為劃分基準。【例8】線性時間選擇方法二122

Select(A,p,r,i)1.將n個元素分成

n/5個組，每組5個元素，另一組由剩餘的nmod5個元素組成。2.利用任一種排序演算法對

n/5個組進行排序，並找出每組元素的中值。

3.對第2步找出的

n/5個中值，利用select遞歸找出這

n/5個中值的中值x4.利用修改的partition過程，以中值的中值作為劃分元素，對輸入數組進行劃分。設k是劃分後左半部分元素數再加上1。因此，x是第k小元素，且右半部分有n-k個元素。

5如果i=k，則返回x；如果i<k，則利用select在劃分的左半部分找第i個最小元素；如果i>k，則在右半部分找第i-k個最小元素。複雜度分析T(n)=O(n)【例8】線性時間選擇【例】已知序列A={2,8,9,10,1,5,3,20,6,12,35,14,18},要求找出第8小元素。2.3.9最接近點對問題【例9】【最接近點對問題】給定n(n≥2)個點的集合Q，找集合Q中一對點p1，p2，使得它們的距離在歐氏距離意義下最小。集合中的兩個點有可能重合，在這種情況下，這兩個點的歐氏距離為0。應用在交通控制系統中，來檢測可能發生的碰撞。【例9】最接近點對問題先來考慮一維的情形：S中n個點化為x軸上的n個實數x1,x2,…,xn。最接近點對即為這n個實數中相差最小的2個實數。假設我們用x軸上某個點m將S劃分為2個子集S1和S2，基於平衡子問題的思想，用S中各點座標的中位數來作分割點。遞歸地在S1和S2上找出其最接近點對{p1,p2}和{q1,q2}，並設d=min{|p1-p2|,|q1-q2|}，S中的最接近點對或者是{p1,p2}，或者是{q1,q2}，或者是某個{p3,q3}，其中p3∈S1且q3∈S2。能否線上性時間內找到p3,q3？S1={x∈S|x≤m}；S2={x∈S|x>m}【例9】最接近點對問題如果S的最接近點對是{p3,q3}，即|p3-q3|<d，則p3和q3兩者與m的距離不超過d，即p3∈(m-d,m]，q3∈(m,m+d]。複雜度分析T(n)=O(nlbn)【例10】循環賽日程表有n=2k個運動員進行網球循環賽，設計一個滿足以下要求的比賽日程表：(1)每個選手必須與其他n-1個選手各賽一次；(2)每個選手一天只能賽一次；(3)循環賽一共進行n-1天。按分治策略，將所有的選手分為兩半，n個選手的比賽日程表就可以通過為n/2個選手設計的比賽日程表來決定。遞歸地用z這種對選手進行分割，直到只剩下2個選手時，比賽日程表的制定就變得很簡單。這時只要讓這2個選手進行比賽就可以了。1234567821436587341278564321876556781234658721437856341287654321學習要點理解遞歸的概念。掌握設計有效演算法的分治策略。通過下麵的範例學習分治策略設計技巧。（1）二分搜索技術；（2）找最大值與最小值；（3）Strassen矩陣乘法；（4）整數相乘；（5）歸併排序和快速排序；（6）線性時間選擇；（7）最接近點對問題；（8）循環賽日程表。練習1.若總是以待排序列的最後一個元素作為基準元素進行快速排序，那麼最好情況下的時間複雜度是（）

A.O(lbn)B.O(n)C.O(nlbn)D.O(n2)2.若對27個元素只進行三趟多路歸併排序，則選取的歸併路數是（）

A.2B.3C.4D.53.某演算法的計算時間可以用遞推式T(n)=2T(n/2)+n表示，則該演算法的時間複雜度為

A.O(lbn)B.O(nlbn)C.O(n)D.O(n2)練習4.演算法的有窮性指的是（）。

A.演算法程式的運行時間是有限的

B.演算法程式所處理的數據是有限的

C.演算法程式的長度是有限的

D.演算法只能被有限的用戶使用練習對於給定的一組關鍵字（18，2，16，30，8，28，4，10，20，6，12），按照下列演算法進行遞增排序，寫出每種演算法第一趟排序後得到的結果：快速排序（選最後一個記錄為基準元素）得到__5__，二路歸併排序得到__6__。(5)A.10,6,18,8,4,2,12,20,16,30,28

B.4,2,6,10,8,12,28,30,20,16,18

C.2,8,4,10,612,16,30,20,18,28

D.6,10,8,28,20,18,2,4,12,30,16(6)A.2,12,16,8,28,30,4,6,10,18,20

B.2,12,16,30,8,28,4,10,6,20,18

C.12,2,16,8,28,30,4,6,10,28,18

D.12,2.10,20,6,18,4,16,30,8,28

7.將兩個長度為n的遞增有序表歸併成一個長度為2n的遞增有序表，最少需要進行關鍵字比較()次。A.i

B.n-1

C.n

D.2n8.對n個元素進行快速排序時，最壞情況下的時間複雜度為()。A．O(1og2n)

B．O(n)

C．O(nlog2n)

D．O(n2)練習練習9.根據Hanoi問題的分治解決演算法，將下列程式補充完整。#include<iostream.h>(1);voidmain(){intm;cout<<"ThisApplicationistoHanoiproblem"<<endl;cout<<"Inputthenumberofplates"<<endl;

(2);cout<<"Thestepofmovingis:"<<endl;hanoi(m,'A','B','C');}練習voidhanoi(intn,charone,chartwo,charthree){if((3))cout<<"from"<<one<<"to"<<three;else{(4);cout<<"from"<<one<<"to"<<three;

(5);}}練習10.設A[0..n-1]是一個已經排好序的數組。請改寫二分查找演算法，使得當查找元素x不在數組中時，返回小於x的最大元素位置i和大於x的最小元素位置j。當查找元素在數組中時，i和j相同，均為x在數組中的位置。作業2-11，2-121.求整數5的劃分個數2.A={12，2，16，30，8，28，4，10，20，6}用分治法找出A中的最大和最小值。3.分別使用歸併排序和快速排序使下述序列昇冪有序A={12，2，16，30，8，28，4，10，20，6}。4.利用線性時間選擇演算法，求下列序列中的第8小元素。A={2,6,18,1,4,10,20,6,22,13,9,5,24,3,7,12,16,11,20,28,23,14,15,21,125,34,19}5.閱讀下麵C代碼，回答問題1至3。【說明】採用歸併排序對n個元素進行遞增排序時，首先將n個元素的數組分成各含n/2個元素的子數組，然後用歸併排序對兩個子數組進行遞歸排序，最後合併兩個已經排好序的子數組得到排序結果。下麵的C代碼是對上述歸併演算法的實現，其中的常量和變數說明如下：arr:待排序數組p,q,r：一個子數組的位置從p到q，另一個子數組的位置從q+1到r作業begin，end：待排序數組的起止位置left，right：臨時存放待合併的兩個子數組n1，n2：兩個子數組的長度i,j,k：迴圈變數mid：臨時變數作業【C代碼】#include<stdio.h>#include<stdlib.h>#defineMAX655536voidmerge(intarr[],intp,intq,intr){int*left,*right;intn1,n2,I,j,k;n1=q-p+1;n2=r-q;作業for(i=0;i<n1;i++){left[i]=arr[p+i];}left[i]=MAX;for(i=0;i<n2;i++){right[i]=arr[q+i+1];}right[i]=MAX;作業i=0;j=0;for(k=p;(1);k++){if(left[i]>right[j]){(2);j++;}作業else{arr[k]=left[i];i++;}}}voidmergesort(intarr[],intbegin,intend){intmid;if((3)){作業mid=(begin+end)/2;mergesort(arr,begin,mid);(4);merge(arr,begin,mid,end);}}【問題一】根據以上說明和C代碼，填充1-4。作業144通過應用範例學習動態規劃演算法設計策略（1）斐波那契數列；（2）0-1背包問題；（3）矩陣連乘問題；（4）最長公共子序列；（5）最優二分檢索樹；（6）裝配線調度問題；（7）凸多邊形最優三角剖分；（8）最大子段和問題。145動態規劃（DynamicProgramming）1957年，RichardBellman創造了這個名字該方法利用表格技術，用多項式複雜度代替指數複雜度。典型應用是組合優化問題，求解最優值和最優解。146動態規劃演算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題演算法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=147但是經分解得到的子問題往往不是互相獨立的。不同子問題的數目常常只有多項式量級。在用分治法求解時，有些子問題被重複計算了許多次。演算法總體思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)148如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重複計算，從而得到多項式時間演算法。演算法總體思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)149學習內容3.1用表代替遞歸3.2

0-1背包問題3.3矩陣鏈乘問題3.4動態規劃演算法的基本要素3.5