算法設(shè)計與分析課件

算法設(shè)計與分析云南大學(xué)廖鴻志2024/12/292內(nèi)容計算模型和計算復(fù)雜性的測度數(shù)據(jù)結(jié)構(gòu)與遞歸技術(shù)分治與平衡排序動態(tài)規(guī)劃貪心法回溯法分枝限界法2024/12/293第一章計算模型和計算復(fù)雜性的測度2024/12/2941.1引言1.算法的概念基本上幾乎所有的程序都是為了實現(xiàn)某種算法，簡言之算法就是處理問題的步驟與邏輯，它是有窮規(guī)則的有序集合。算法分為數(shù)值算法與非數(shù)值算法。數(shù)值算法有：概率統(tǒng)計計算、線性代數(shù)計算、數(shù)值逼近、數(shù)值微分、數(shù)值積分、數(shù)學(xué)規(guī)劃等。數(shù)值算法是通用的，一般可用解析式表示：而非數(shù)值算法只是思想或思路，要根據(jù)具體問題按這種思想或思路進行設(shè)計。2024/12/2951.1引言2算法的特征(1)有窮性：算法應(yīng)該是有窮規(guī)則，在有窮步驟后終止。(2)確定性：算法的任何一步都應(yīng)該有且僅有一個解釋。(3)能行性：算法應(yīng)該符合問題的要求，應(yīng)該在有限時間內(nèi)完成。(4)輸入與輸出：有零個或多個外部量作為算法的輸入，算法產(chǎn)生至少一個量作為輸出。2024/12/2961.1引言程序與算法不同，程序是算法用某種程序設(shè)計語言的具體實現(xiàn)。程序可以不滿足算法的有限性。例如操作系統(tǒng)，它是在無限循環(huán)中執(zhí)行的程序，因而它并不是算法。然而可以將它的各種任務(wù)看成一些單獨的問題。每一個問題由操作系統(tǒng)的一個子程序通過特定的算法實現(xiàn)。該子程序在得出輸出結(jié)果后便終止。2024/12/2971.1引言3算法設(shè)計與分析的步驟(1)問題的描述：明確輸入與輸出。(2)建立模型：將核心內(nèi)容模型化，邏輯化。(3)算法設(shè)計與正確性證明：對所有正確的輸入都能得到正確的輸出（一般需要用謂詞邏輯來證明）。(4)程序?qū)崿F(xiàn)：用某種程序設(shè)計語言來實現(xiàn)。(5)算法分析：在程序?qū)崿F(xiàn)之前進行。2024/12/2981.2計算復(fù)雜性的測度算法的計算復(fù)雜性(computationalcomplexity)是衡量算法計算難度的尺度，使用最普遍的標準是一個算法需要耗費的時間和空間。算法所需要的時間或空間，通常是問題規(guī)模的函數(shù)，這個函數(shù)就叫做算法的時間或空間復(fù)雜度。在實際中用算法主操作的重復(fù)次數(shù)來表示算法的時間復(fù)雜度。2024/12/2991.2計算復(fù)雜性的測度問題的規(guī)模：也就是該問題所謂的體積，或者說是大小。一個問題的體積可以用一個整數(shù)來表示，它是對問題的輸入數(shù)據(jù)或初始數(shù)據(jù)的多少的一種量度。定義：如果一個問題的體積是n，解決這一問題的某一算法所需要的時間為T(n)，它是n的某一函數(shù)，T(n)稱作這一算法的“時間復(fù)雜性”。當(dāng)輸入量n逐漸增大時，T(n)的極限情形就稱作算法的“漸近時間復(fù)雜性”，類似可定義算法的空間復(fù)雜性。但實際上人們主要是研究算法的時間復(fù)雜性而很少討論它們的空間耗費。2024/12/29101.2計算復(fù)雜性的測度一個算法的復(fù)雜性函數(shù)的量級是反映算法效能的重要標準。當(dāng)輸入量急劇地增大時，如果設(shè)有高效能的算法，單純依靠提高計算機的速度，有時是很不理想的。設(shè)有五個算法A1，A2，A3，A4，A5，它們的時間復(fù)雜性函數(shù)如下表所示：表中，一個算法的時間復(fù)雜性是它處理完一個大小為n的輸入所需要的的單位時間數(shù)。2024/12/2911例例1.39個景點的全排列

39！=2.04×1046

用每秒處理1億次（108）邏輯的計算機，需耗時6.5×1022億年例2.下圍棋

3361=1.74×10172=5.52×10146億年例3.電梯從1樓到10樓，有多少種可能的方式？

2024/12/2912算法時間復(fù)雜性函數(shù)A1T1(n)=nA2T2(n)=nlog2n(nlogn)A3T3(n)=n2A4T4(n)=n3A5T5(n)=2?1.2計算復(fù)雜性的測度2024/12/2913算法時間復(fù)雜性一秒鐘內(nèi)所能處理的最大輸入量一分鐘內(nèi)所能處理的最大輸入量一小時內(nèi)所能處理的最大輸入量A1A2A3A4A5nn㏒2nn2n32?1000140311096×104489324439153.6×1062.0×1051897153211.2計算復(fù)雜性的測度2024/12/2914算法時間復(fù)雜性速度提高前單位時間里所能處理的數(shù)據(jù)量速度提高十倍后單位時間里所能處理的數(shù)據(jù)量速度提高一萬倍后單位時間里所能處理的數(shù)據(jù)量A1A2A3A4A5nn㏒2nn2n32?S1S2S3S4S510S1(S2很大)10S23.16S32.15S4S5+3.3210000S1(㏒2S2≥9㏒29000)>9000S2100S321.54S4S5+13.321.2計算復(fù)雜性的測度2024/12/29151.2計算復(fù)雜性的測度現(xiàn)有問題可以分為以下三類：無法寫出算法的問題；有以多項式為界的算法存在的問題，即Ｐ類問題；介于前兩類問題之間的問題，“ＮＰ——完全”問題。2024/12/29161.3隨機存取模型自學(xué)2024/12/2917第二章數(shù)據(jù)結(jié)構(gòu)和遞歸技術(shù)2024/12/2918表、樹、圖表：a1,a2,a3,…,ai,ai+1,…an是一個數(shù)據(jù)元素，ai-1為ai的前驅(qū)，ai+1為其后繼。第一個元素沒有前驅(qū)，最后一個數(shù)據(jù)元素沒有后繼。順序存儲：數(shù)組鏈式存儲：鏈表2024/12/29192.1圖和圖的表示鄰接矩陣鄰接表鄰接向量關(guān)聯(lián)矩陣一般有以上幾種圖的常用表示法2024/12/29202.2樹僅有一個沒有邊進入的頂點，這個頂點稱為這棵樹的根；除根以外的其它任何頂點，有且只有一條邊進入該頂點；從根到每一個頂點都有一條唯一的道路。2024/12/29212.2樹二叉樹：根最多有兩個孩子，若有左子，左孩子為二叉樹；若有右孩子，右孩子為二叉樹。完全二叉樹：結(jié)點深度最多差1，除沒有孩子的結(jié)點所在層為滿二叉樹，沒有孩子的結(jié)點集中在左邊。滿二叉樹：所有葉片的深度都相等的完全二叉樹。2024/12/29222.2樹樹的遍歷先序遍歷中序遍歷后序遍歷2024/12/29232.3遞歸技術(shù)一個直接或間接地調(diào)用自身的過程稱為遞歸過程(recursiveprocedure)；一個直接或間接地調(diào)用自身的算法稱為遞歸算法。一個使用函數(shù)自身給出定義的函數(shù)叫做遞歸函數(shù)(recursivefunction)。在算法設(shè)計與分析中，使用遞歸技術(shù)往往使函數(shù)的定義和算法的描述簡潔且易于理解。有些數(shù)據(jù)結(jié)構(gòu)如二叉樹等，由于其本身固有的遞歸特性，特別適合用遞歸的形式來描述。還有一些問題，雖然其本身并沒有明顯的遞歸結(jié)構(gòu)，但用遞歸技術(shù)來求解使設(shè)計出的算法簡潔易懂且易于分析。2024/12/29242.3遞歸技術(shù)例2.5階乘函數(shù)階乘函數(shù)可以遞歸地定義為：2024/12/29252.3遞歸技術(shù)定義式的左右兩邊都引用了階乘記號，是一個遞歸定義式，可遞歸地計算如下：intFactorial(intn){ if(n==0) return1; else returnn*Factorial(n-1);}2024/12/29262.3遞歸技術(shù)例2.6Fibonacci數(shù)列無窮數(shù)列1,1,2,3,5,8,13,21,34,55,...，稱為Fibonacci數(shù)列或級數(shù)。它可以遞歸地定義為：2024/12/29272.3遞歸技術(shù)第n個Fibonacci數(shù)可以遞歸地計算如下：intFibonacci(intn){ if(n≤1) return1; else returnFibonacci(n-1)+Fibonacci(n-2);}2024/12/29282.3遞歸技術(shù)上述兩例中的函數(shù)也可以用如下的非遞歸方式定義：2024/12/29292.3遞歸技術(shù)并非一切遞歸函數(shù)都能用非遞歸方式定義。為了對遞歸函數(shù)的復(fù)雜性有更多的了解，我們再介紹一個雙遞歸函數(shù)——Achkerman函數(shù)。當(dāng)一個函數(shù)及它的一個變量是由函數(shù)自身定義時，稱這個函數(shù)是雙遞歸函數(shù)。2024/12/29302.3遞歸技術(shù)Acheman函數(shù)A(n,m)有兩個獨立的整變量m≥0和n≥0，其定義如下：

2024/12/29312.3遞歸技術(shù)A(n,m)的自變量m的每一個值都定義了一個單變量函數(shù)。由遞歸式的第三式可知m=0定義了函數(shù)“加2”。當(dāng)m=1時，由于A(1,1)=A(A(0,1),0)=A(1,0)=2以及A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2(n>1)，則A(n,1)=2n(n≥1)，即A(n,1)是函數(shù)“乘2”當(dāng)m=2時由于A(n,2)=A(A(n-1,2),1)=2A(n-1,2)以及A(1,2)=A(A(0,2),1)=A(1,1)=2，則有A(n,2)=2的n次方2024/12/29322.3遞歸技術(shù)大家可以試著算一下A(2,10)和A(3,4)答案分別是：222```2｝10個2222```2｝65536個22024/12/29332.3遞歸技術(shù)2.3.1整數(shù)劃分把一個正整數(shù)n表示成如下形式的一系列正整數(shù)的和，叫做n的一個劃分。2024/12/29342.3遞歸技術(shù)正整數(shù)n的不同劃分個數(shù)稱為正整數(shù)n的劃分數(shù)，記作P(n)，P(n)是一個數(shù)論函數(shù)。例如：正整數(shù)6有如下11種不同的劃分，所以P(6)=11。這11個劃分分別是：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。2024/12/29352.3遞歸技術(shù)

將最大加數(shù)n1不大于m的劃分個數(shù)記作Q(m,n)。我們可以建立如下的遞歸關(guān)系。Q(n,1)=1,n≥1;當(dāng)最大加數(shù)n1不大于1時，任何正整數(shù)n只是有種切分形式，即n=1+1+...+1，n個1相加。Q(n,m)=Q(n,n),m≥n;最大加數(shù)n1實際上不能大于n。因此，Q(1,m)=1。Q(n,n)=1+Q(n,n-1);正整數(shù)n的劃分由n1=n的劃分和n1≤n-1的劃分組成。Q(n,m)=Q(n,m-1)+Q(n-m,m),n>m>1;正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1≤m-1的劃分組成。2024/12/29362.3遞歸技術(shù)以上的關(guān)系實際上給出了計算Q(n,m)的遞歸式如下：2024/12/29372.3遞歸技術(shù)可以設(shè)計出計算Q(n,m)的遞歸算法如下：intQ(intn,intm){ if((n<1)||(m<1)) return0; if((n==1)||(m==1)) return1; if(n<m) returnQ(n,n); if(n==m) returnQ(n,m-1)+1; else returnQ(n,m-1)+Q(n-m,m);}2024/12/29382.3遞歸技術(shù)Hanoi塔問題設(shè)a,b,c是3個塔座。開始時，在塔座a上一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,...,n2024/12/29392.3遞歸技術(shù)現(xiàn)在要求將塔座a上的這些圓盤移到b上，并仍按有序位置疊置。在移到圓盤時應(yīng)該遵守以下規(guī)則：每次只能移動一個圓盤；任何時刻都不允許將大盤壓在小盤上；在滿足規(guī)則1和規(guī)則2的前提下，可將圓盤移至a,b,c中任何一個塔座上。2024/12/29402.3遞歸技術(shù)這人問題有一個簡單的解法。假設(shè)塔座a,b,c排成一個三角形，a->b->c->a構(gòu)成順時針循環(huán)。在移動圓盤的過程中，若是奇數(shù)次移動，則將最小的圓盤移到順時針方的下一塔座上；若是偶數(shù)次移動，則保持最小的圓盤不動。而在其他兩個塔座這間較小的圓盤移到另一塔座上去。2024/12/29412.3遞歸技術(shù)當(dāng)n=1時，問題比較簡單，只要將編號為1的圓盤從塔座a直接移至b上即可。當(dāng)n>1時，需要利用塔座c作為輔助塔座。此時若能設(shè)法將n-1個較小的圓盤按規(guī)則從塔座a移至塔座c，然后將剩下的最大圓盤從塔座a移至塔座b，最后再設(shè)法將n-1個較小的圓盤按規(guī)則從塔座c移至塔座b。由此可見，n個圓盤的移動問題可以分為兩次n-1個圓盤的移動問題。2024/12/29422.3遞歸技術(shù)可以設(shè)計出解Hanoi塔問題的遞歸算法如下：voidHanoi(intn,inta,intb,intc){ if(n>0) { Hanoi(n-1,a,c,b); move(a,b); Hanoi(n-1,c,b,a); }}2024/12/29432.3遞歸技術(shù)二叉樹中序遍歷遞歸算法VoidMidOrder(root){ if(root!=null) { MidOrder(root->lchild); treat(root); MidOrder(root->rchild); }}2024/12/29442.3遞歸技術(shù)算法Hanoi以遞歸形式給出，每個圓盤的具體移動方式不清楚，因此很難用手工移動來模擬這個算法。但該算法易于理解，也容易證明其正確性，而且易于掌握它的設(shè)計思想。由昆可見，用遞歸技術(shù)來設(shè)計算法很方便，而且設(shè)計出的算法往往比通常的算法有效。2024/12/29452.3遞歸技術(shù)2.3.3遞歸過程的實現(xiàn)像Hanoi這們的遞歸算法，在執(zhí)行時需要多次調(diào)用自身。實現(xiàn)這種遞歸調(diào)用的關(guān)鍵是為算法建立遞歸調(diào)用工作棧。2024/12/29462.3遞歸技術(shù)通常，在一個算法中調(diào)用另一個算法時，系統(tǒng)需要在運行被調(diào)用算法之前先完成3件事：將所有實參指針，返回地址等信息傳遞給被調(diào)用算法；為被調(diào)用算法的局部變量分配存儲區(qū)；將控制轉(zhuǎn)移到被調(diào)用算法的入口2024/12/29472.3遞歸技術(shù)在從被調(diào)用算法返回調(diào)用算法時，系統(tǒng)也相應(yīng)地完成3件事：保存被調(diào)用算法的計算結(jié)果；釋放根本給被調(diào)用算法的數(shù)據(jù)區(qū)；依照被調(diào)用算法保存的返回地址將控制轉(zhuǎn)移到調(diào)用算法。2024/12/29482.3遞歸技術(shù)當(dāng)有多個算法構(gòu)成嵌套調(diào)用時，按照后調(diào)用先返回的原則進行。遞歸算法之間的信息傳遞和控制轉(zhuǎn)移必須通過棧來實現(xiàn)，即系統(tǒng)閨怨整個程序運行時所需要的數(shù)據(jù)空間安排在一個棧中，每調(diào)用一個算法，就為它在棧頂分配一個存儲區(qū)，每退出一個算法，就釋放它在棧頂?shù)拇鎯^(qū)。當(dāng)前正在運行的算法的數(shù)據(jù)一定在棧頂。2024/12/29492.3遞歸技術(shù)2024/12/29502.4解遞歸方程對于k階齊次方程

F(n)=a1F(n-1)+a2F(n-2)+…+akF(n-k)，已知：F(0),F(1),…,F(k-1)共k個初值特征方程為：

xk-a1xk-1-a2xk-2-…-ak-1x–ak=0；有k個根q1,…,qk2024/12/29512.4解遞歸方程qi(i=1…k)互不相同，通解如下：

F(n)=C1q1n+C2q2n+…+Ckqkn若有重根q1≠q2≠…≠qi=…=qi+r-1≠qi+r≠…≠qk

，通解為：

F(n)=C1q1n+C2q2n+…+ Ci-1qi-1n+(Ci+Ci+1n+…+Ci+r-1nr-1)qin

+Ci+rqi+rn+…+Ckqkn2024/12/29522.4解遞歸方程對于k階非齊次方程

F(n)=a1F(n-1)+a2F(n-2)+… +akF(n-k)+f(n)通解為：F(n)=F,(n)+F*(n)。其中F’(n)為無f(n)時的通解，即k階齊次方程的通解，F(xiàn)*(n)為特解

2024/12/29532.4解遞歸方程先寫出特征方程然后根據(jù)k個初值求出待定參數(shù)Ci最后驗證2024/12/29542.4解遞歸方程練習(xí)1F(n)=7F(n-1)–12F(n-2);F(0)=4,F(1)=0解：特征方程為x2-7x+12=0； 解得：x1=3，x2=4；F(n)=C13n+C24n ∵F(0)=4,F(1)=0

∴C1=16，C2=-12

∴F(n)=16×3n-12×4n2024/12/29552.4解遞歸方程練習(xí)2F(n)=6F(n-1)–9F(n-2)+3 F(0)=0,F(1)=1解：特征方程為x2-6x+9=0； 解得：x1=x2=3；F(n)=(C1+nC2)3n+C3×3

∵F(0)=0,F(1)=1,F(2)=6,F(1)-9F(0)+3=9

∴C1=-3/4，C2=5/6，C3=1/4

∴F(n)=-3/4×3n+5/6×3n+3/42024/12/29562.4解遞歸方程練習(xí)3F(n)=7F(n-1)–10F(n-2)+3n F(0)=0,F(1)=1解：特征方程為x2-7x+10=0； 解得：x1=2，x2=5；

F(n)=C12n+C25n+C33n ∵F(0)=0,F(1)=1,F(2)=7F(1)-10F(0)+32=16

∴C1=8/3，C2=11/6，C3=-9/2

∴F(n)=8/3×2n+11/6×5n-9/2×3n2024/12/2957第三章分治與平衡

楊素勤（１２００６００９８５）2024/12/2958分治與平衡的思想把一個問題分成k個同類子問題處理的分治思想和子問題規(guī)模大體相等的平衡思想（balancing）相結(jié)合,即為分治與平衡算法.2024/12/2959兩個非遞減序列的合并下面將介紹兩個有序非遞減序列如何合并為一個有序序列：給定兩個非遞減有序數(shù)列和把這兩個序列按非遞減有序合并入。分別取出兩個序列中的第一個元素，對這兩個元素進行比較。如果a1不大于b1,則將a1存入c1，取出a2與b1進行比較。如果a1大于b1則將b1存入c1取出b2與a1進行比較。重復(fù)上述步驟，直到兩個序列完全合并。2024/12/2960兩個非遞減序列合并的算法將：和合并存入ProcedureMERGEI

i=1;j=1;k=1;While(i<=m)and(j<=n)doIfA[i]<=B[j]thenbeginC[k]=A[i];i=i+1;k=k+1;end;2024/12/2961兩個非遞減序列合并的算法elseC[k]=B[j];j=j+1;k=k+1;end;ifi>mthen{將bj、bj+1、…、bn

依次賦值給Ck}Else{將ai、ai+1、…、am依次賦值給Ck}算法中，最大的比較次數(shù)為m+n-1.2024/12/2962合并排序思想設(shè)給定集合S={x1,x2,……,xn},且n=2k。當(dāng)n>2時，把S分成兩個不相交的子集合S1={x1,x2,……xn/2}和集合S2={xn/2+1,xn/2+2,……,xn}。直到集合S分解到每個子集合的元素不超過2時為止。比較1次即可將只有兩個元素的子集排序.調(diào)用前面的MERGEI算法將各個子集合合并。2024/12/2963合并排序算法procedureMERGESORTinteger:n;array:A[1:n]ofinteger;procedureSORT(A,i,j);integer:i,j,m;array:A[i:j]ofinteger;beginifj-i=1thenifA[i]>A[j] 2024/12/2964合并排序算法elsebeginm=(i+j-1)/2; SORT(A,i,m); SORT(A,m+1,j); MERGEI(A[i:m]，A[m+1:j]) end;end;begin read(n,A); SORT(A,1,n); write(A);end2024/12/2965用二叉樹來表示排序a>=bb>=ca>=ca>=cb>=ca,b,ca,c,bc,a,bb,c,ac,b,ab,a,cYNYNYNYNYN2024/12/2966用二叉樹來表示排序左圖為一棵平衡二叉樹，平均比較次數(shù)(時間復(fù)雜度)為(2×2+3×4)÷6=2.67。原始數(shù)據(jù)的狀態(tài)會影響排序的效率。2024/12/2967用二叉樹來表示排序N個數(shù)排序，有n！種結(jié)果，對應(yīng)的二叉樹有n！片樹葉。如果算法對應(yīng)一棵平衡二叉樹一定存在一個k使K對應(yīng)平衡二叉樹中深度小的結(jié)點，而k+1則對應(yīng)二叉樹中深度大的結(jié)點。若，任何需要比較進行的排序算法，已經(jīng)是最好的算法數(shù)量級。2024/12/2968快速排序?qū)⒓蟂={a1,a2,……,an}分成小于a，等于a，大于a的三個子集合S1，S2，S3。分別將S1與S3排序，最后將S1，S2和S3連接起來。 優(yōu)點：（1）劃分以后就減少了待排序元素的數(shù)量。 （2）子集合排序后采用連接而不用比較就可以歸并。 缺點：a難以確定恰當(dāng)?shù)卮_定，因此平衡的思想就難以體現(xiàn)。

2024/12/2969快速排序算法先要解決如何在同一數(shù)組中劃分子集合：a1，a2，a3，……，an-1，anwhilei<jdobeginwhileai<adoi=i+1;whileaj<adoj=j-1;

交換ai和ajend;2024/12/2970快速排序算法procedureQUICKSORT(S); if||S||<=2then begin

將S中的元素直接排序；

return(S) end else begin

從集合S中隨機選取一個元素a； 把S中的元素分成小于a，等于a和大于a三個子集合S1,S2,S3; return(QUICKSORT(S1)接著S2接著QUICKSORT(S3)) end2024/12/2971課后作業(yè)考慮分治—合并排序算法，重新設(shè)計MERGEI(A,B)，考慮ｎ不一定等于實現(xiàn)快速排序算法。第四章排序2024/12/2973目錄4.1排序的定義4.2基數(shù)排序4.3比較排序的時間下界4.4堆選排序4.5插入法2024/12/29

2024/12/29744.1排序的定義半序的定義

定義如果集合S上的一個關(guān)系R，對于S中的任何元素a，b，c，若

1.aRa為真（自反性）；

2.由aRb和bRc可得aRc（傳遞性）；

3.由aRb和bRa可得a=b

（反對稱性）；則稱R為集合S上的一個半序(partiaorder)。2024/12/29

2024/12/29754.1排序的定義排序的定義

給定一個從有線性序R的集合中抽出來的n個元素a1，a2，…，an。所謂將這n個元素排序就是要找出1，2，…，n的一個特定排列

∏(1)，∏(2)

，…，∏(n)，使得對于任何i，

1≤i＜n，有a∏(i)Ra∏(i+1)。當(dāng)關(guān)系R是“≤”時，既有

a∏(i)≤

a∏(i+1)≤…≤a∏(n)。2024/12/29

2024/12/29764.2基數(shù)排序待排序元素a1，a2，…，an，將其置于一個桶（隊列）Q中。ak均為k元組，每一元由m個不同的符號而組成,另設(shè)m個不同的桶分別對應(yīng)m個符號。將Q中元素按元分裝到m個桶中，再將m個桶中的元素歸并到Q中，如此進行k次，即可使Q中的元素有序。2024/12/29

2024/12/29774.2基數(shù)排序例用桶排序法將以下6個數(shù)排序：

379，258，731，432，913，455

0號桶1號桶2號桶3號桶4號桶5號桶6號桶7號桶8號桶9號桶按各位數(shù)置桶731432913455258379第一次合并后隊列731432913455258379按十位數(shù)置桶913731432455258379第二次合并后隊列913731432455258379按百位數(shù)置桶258379432455731913結(jié)果2583794324557319132024/12/29

2024/12/29784.2基數(shù)排序算法4.1桶排序法

輸入一個序列A1，A2，…，An；這里每個元素Ai是一個K元組（ai1ai2…aik），其中，對一切i,，j；1≤i≤n，

1≤j≤k，有0≤aij≤m-1。輸出序列A∏(1)≤

A∏(2)≤

…

≤A∏(n)，它是A1，A2，…，An的一個排列。方法使用隊列QUEUE存放“當(dāng)前的元素序列”，還有m個桶Q[0]，Q[1]，…，Q[m-1]，它們都是一個先進先出的對列。用Q[i]來存放當(dāng)前的分量是正數(shù)i的那些元素。（參見過程BUCKETSORT）。2024/12/29

2024/12/29794.2基數(shù)排序基數(shù)排序算法（算法4.1）

procedureBUCKETSORTbegin

置A1，A2，…，An到隊列QUEUE中；

fori←jstep-1until1dobeginforI←0tom-1do置Q[I]為空；

whileQUEUE非空do把QUEUE中的第一個元素Ai置入桶Q[aij]中；

forl←0tom-1do依次置Q[l]中的元素到QUEUE中

endend定理4.1

算法BUCKETSORT將n個元素排序所需的時間是O(k(m+n))，其中k是每個元素的長度，每個分量是介于0到m-1之間的整數(shù)。2024/12/29

2024/12/2980問題能否用基數(shù)排序法對不超過k元的多元組進行排序?若回答肯定,對元組分別為多數(shù)字和字符串時如何處理?2024/12/29814.3比較排序的時間下界引理4.1

一棵高為h的二叉樹，最多有2h個葉。定理4.3

將n個不同元素排序的任一判定樹的高不小于「log2n!」。2024/12/29

2024/12/29824.4堆選排序堆選排序堆是一棵完全二叉樹且

ai>=a2i,ai>=a2i+1

把所有要排序的元素建成一個堆，然后刪去根節(jié)點上的元素。將最大深度的最右邊的葉元素移至根結(jié)點，將這棵樹再建成一個堆。重復(fù)上述過程，直到這棵樹只剩一個頂點為止。從這個堆的根節(jié)點上刪去的元素序列（按刪去的先后順序排列起來）就是一個排序好的非遞增序列2024/12/29

2024/12/29834.4堆選排序堆排序的過程是，把初始數(shù)據(jù)“堆化”后，重復(fù)執(zhí)行如下兩個步驟：1.刪除根節(jié)點的元素；2.將最深最右的葉元素移到根節(jié)點并刪去這個葉，重新堆化。在實際處理時，只需將根節(jié)點元素和待刪葉元素互換，就能達到刪除根節(jié)點元素和把最深最右的葉元素移至根節(jié)點上的雙重目的，然后對剩下的元素重新堆化。例對50，24，30，20，21，18，3，12，5，6進行堆排序。2024/12/29

2024/12/29844.4堆選排序例對50，24，30，20，21，18，3，12，5，6進行堆排序。下列的圖表示刪去根元素和重新堆化的過程。50242012530211836(i)624201253021183(ii)刪去50，將6移至根部2024/12/29

2024/12/29854.4堆選排序如果用數(shù)組記錄上述過程，數(shù)組元素的變化如下：(i)50，24，30，20，21，18，3，12，5，6(ii)6，24，30，20，21，18，3，12，5，50(iii)30，24，6，20，21，18，3，12，5，50(iv)6，24，18，20，21，6，3，12，5，50302420125621183(iii)將6與它的最大兒子30交換302420125182163(iv)將6與它的最大兒子18交換2024/12/29

2024/12/29864.4堆選排序算法4.3構(gòu)造一個堆輸入數(shù)組A[i]，1≤i≤n。輸出把A的元素變成一個堆，即使得對于1＜i≤n，

A[i]≤A[「i/2

」]。方法見過程BUILDHEAP。2024/12/29

2024/12/29874.4堆選排序構(gòu)造一個堆（算法4.3）

procedureBUILDHEAPbeginprocedureHEAPIFY(i,j)beginif2i<jthenifA[2i]≤A[2i+1]且A[i]≤A[2i+1]thenbegin

交換A[i]和A[2i+1]；

HEAPIFY(2i+1,j);endif2i=jthenifA[i]<A[j]then交換A[i]和A[j]endbeginread(A[1]，A[2]，…，A[n]);fori←「n/2」step-1until1doHEAPIFY(i,n)end2024/12/29

2024/12/29884.4堆選排序算法4.4

堆選排序算法。輸入數(shù)組A[1:n]。輸出按非遞減序排列的結(jié)果。方法見過程HEAPSORT

procedureHEAPSORT:beginBUILDHEAP;fori←nstep-1until2dobegin

交換A[1]和A[i]；

HEAPIFY(1,i-1);endend

2024/12/29

2024/12/29894.4堆選排序定理4.5

算法HEAPSORT對n個元素排序所需的時間是O(nlog2n)。2024/12/29

2024/12/29904.5插入法分段逆序插入法

設(shè)A={a1，a2，…，am}是一個非遞減序列。B={b1，b2，…，bm+∈}是序列A的伴隨序列，即對一切1≤i≤m，有bi≤ai，其中∈的值是0或1。將B中的元素插入到序列A中，使A、B合并為一個大的非遞減的序列。因為已知bi≤ai，所以對任何bi，只要能把它插入到a1，a2，…，ai-1的合適位置即可。如果在bi插入前，已有某個bj(j≠i)

已插入到a1，a2，…，ai-1中，bi同樣可以插入到ai左部的部分序列中。2024/12/29

2024/12/29914.5插入法bi插入的方法就是所謂的分段逆序插入法。對較小的m，序列B中元素的插入順序和所需比較的次數(shù)見下表。Aa1a2a3a4a5a6a7a8a9a10a11a12a13…a21a22a23…a43a44…Bb1b2b3b4b5b6b7b8b9b10b11b12b13…b21b22b23…b43b44…bi插入順序13254111098762120…124342…2285…最大的比較次數(shù)0223344444455…566…67…Bi插入的順序和所需的比較次數(shù)2024/12/29

2024/12/29924.5插入法bi的插入順序和所需比較次數(shù)是這樣得到的。因為b1≤a1，直接把b1置于a1的前面。當(dāng)m+∈≥3時，先將b3按折半查找插入序列b1a1a2中，需要兩次比較。插入的結(jié)果，即使b3小于a2，再插入b2時，也不過是將它插入b1a1和b3構(gòu)成的長度為三的序列中，仍然只要兩次比較。至此，a4以前一共有6個元素。如果m+∈≥則先插b5，后查b4，它們最多時插入一個7元序列中，各需三次比較等等。為嚴格描述分段逆序折半插序，定義了一個遞歸函數(shù)f(n)

（稱做分段函數(shù)）。它是f(n)=1,當(dāng)n=1時2n+f(n-1),當(dāng)n=1時2024/12/29

2024/12/29934.5插入法算法4.5

分段逆序插入法

輸入非遞減序列A=={a1，a2，…，am}和它的伴隨序列B={b1，b2，…，bm+∈}，對一切1≤i≤m，有bi≤ai，其中∈的值是0或1。輸出由A和B的全體元素組成的一個非遞減序列。方法見過程BYFINSERT

procedureBYFINSERT(‖B‖,A,B)begin

將b1插到a1的前面；找到一個整數(shù)k≥2，使得f(k-1)<m+∈≤f(k);

按b3，b2；b5，b4；…；bf(k-2)，bf(k-1)-1，…，bf(k-2)+1；bm+∈，…，bf(k-1)+1的順序?qū)i折半插入序列A中。

end2024/12/29

2024/12/29944.5插入法插入排序法

把要排序的n個元素，分成兩個一對分別比較，把各對中較大的元素記入子序列S1中，較小的序列記入子序列S2中，即S1和S2中的元素有一對一的大小關(guān)系。當(dāng)n為奇數(shù)時，S中的第n個元素記入S2的末尾。然后，將S1中的元素排序（遞歸的應(yīng)用插入法）。最后，使用分段逆序插入法把S2中的元素插入已排序的S1中，就得到n個元素的有序序列（當(dāng)元素個數(shù)較少時（n≤4），就直接排序）。2024/12/29

2024/12/29954.5插入法例用排序法將以下11個元素排序，它們是

11，127，43，574，5，560，700，708，9，20，31第一步：11~127，43~574，5~560，700~708，9~20，31，得

S1={127，574，560，708，20}S2={11，43，5，700，9，31}第二步：將S1的元素排序。因為‖S1‖=5>4，做127~574，560~708，得

S1′={574，708}S2′={127，560，20}

對S1′排序。因為‖S1′‖=2<4，用“”比較“直接排序，得排序的S1′為574，7082024/12/29

2024/12/29964.5插入法

由S1′和S2′的關(guān)系，有

574<708

↓↓12756020

按分段逆序插入法，用兩次比較（20~574，20~127）先將20插入序列

127<574<708

之中，然后將560插入序列

20<127<574<708

之中，也只需兩次比較（560~127，560~574），得到S1的排序結(jié)果為

20<127<560<574<7082024/12/29

2024/12/29974.5插入法第三步：用逆序插入法將S2插入S1。根據(jù)S1和S2的元素對應(yīng)關(guān)系，有

20<127<560<574<708

↓↓↓↓↓91154370031按分段逆序插入法，插入順序依次是5，11，700，43，31。各插入結(jié)果是：

5<9<20<127<560<574<708

↓↓↓1143700312024/12/29

2024/12/29984.5插入法

5<9<11<20<127<560<574<708

↓↓4370031

5<9<11<20<127<560<574<700<708

↓43315<9<11<20<43<127<560<574<700<708315<9<11<20<31<43<127<560<574<700<708累計總的比較次數(shù)，最多要26次。2024/12/29

2024/12/29994.5插入法算法4.6

插入排序輸入數(shù)組A=={a1，a2，…，an}

輸出元素a1，a2，…，an的一個非遞減序列。

方法見過程INSERT(S1i,i)。在應(yīng)用時，只要執(zhí)行語句調(diào)用INSERT(S10,0)。這里S10=A。

2024/12/29

2024/12/291004.5插入法procedureINSERT(S1i,i)if‖S1i‖≥4thenbegin

把S1i中的元素分成「‖S1i‖/2」對兩兩比較；各組中的較大元素依次記入S1i+1中；各組中的較小元素依次記入S2i+1中。當(dāng)‖S1i‖為奇數(shù)時，將S1i中最末的一個元素記入S2i+1的末尾；

INSERT(S1i+1,i+1);return(BYFINSERT(「‖S1i‖/2」,S1i+1,S2i+1)endelsebegin

直接將S1i中的元素排序；

return(S1i)end2024/12/29

2024/12/29101第五章動態(tài)規(guī)劃2024/12/29102引言所謂動態(tài)規(guī)劃（Dynamicprogramming）常常能得到一個比窮舉法有效的算法。動態(tài)規(guī)劃的指導(dǎo)思想是，在每種情況下，列出各種可能的局部解，然后按某些條件，從局部解（或中間結(jié)果）中挑選出那些有可能產(chǎn)生最佳解的結(jié)果而揚棄其余。從而大大縮減了計算量。動態(tài)規(guī)劃遵循所謂“最佳原理”的原則。即“不論前面的狀態(tài)和策略如何，后面的最優(yōu)策略只取決于由最初策略所確定的當(dāng)前狀態(tài)。”即“最優(yōu)化從當(dāng)前狀態(tài)開始”.2024/12/29103引言動態(tài)規(guī)劃所適用的問題：1）優(yōu)化問題2）分階段處理的問題3）狀態(tài)之間有確定次序的問題。不能跨越2024/12/291045.1單源最短路徑問題1.多級圖

G={V,E}其中V是頂點的集合,E是邊(弧)的集合

Vi也是頂點的集合,Ei是邊的集合,如果

V=∪Vi∩iVi為空當(dāng)(vl,vt)屬于Ei且vl屬于Vi時,必有Vt屬于Vi+1,則G為多級圖2024/12/291055.1單源最短路徑問題最短路徑：是按道路上的代價函數(shù)來判定的。如果是兩個城市，道路上的代價函數(shù)可能是城市間的里程，或者旅差費用等。2024/12/291065.1單源最短路徑問題COST（i,j）第i級頂點vj到匯點的最短路徑長度C(i,j)邊(vi,vj)上的權(quán)值COST（i,j）=min{c(j,l)+COST（i+1，l）},其中l(wèi)屬于頂點集Vi+12024/12/291075.1單源最短路徑問題2024/12/291085.1單源最短路徑問題對于圖5.1，計算過程如下：COST（3,6）=min{6+COST（4,9）,5+COST（4,10）}=min{6+4,5+2}=7COST（3,7）=min{4+COST（4,9）,3+COST（4,10）}=min{4+4,3+2}=5COST（3,8）=72024/12/291095.1單源最短路徑問題COST（2,2）=min{4+COST（3,6）,2+COST（3,7）,1+COST（3,8）}=min{11,7,8}=7COST（2,3）=9COST（2,4）=11+COST（3,8）=18COST（2,5）=15COST（1,1）=min{9+COST（2,2）,7+COST（2,3）,3+COST（2,4）,2+COST（2,5）}=min{16,16,21,17}=162024/12/291105.1單源最短路徑問題因此，從S到T的一條最短路徑的代價是16。只要我們每次記下使COST（i,j）達到最小的第j+1級的頂點號，這條路徑也就找到了。2024/12/291115.1單源最短路徑問題算法：兩點間的最短路算法(由后向前)_用cost(j)代替cost(i,j),即不記錄頂點所在級,存儲多級圖時應(yīng)如何處理?____________________________________PROCEDUREFGRAPHBeginFori←1tondoCOST[i]←0;Forj←n-1to1do//計算COST[j]//2024/12/291125.1單源最短路徑問題Begin設(shè)L是這樣一個頂點，邊（j,L）屬于E且c(j,L）+COST[L]最?。籆OST[j]←c(j,L）+COST[L];D[j]←L;End2024/12/291135.1單源最短路徑問題//找最小代價的道路//P[1]←1，P[k]←n;Forj←2tok-1doP[j]←D[P[j-1]]End________________________________2024/12/29114第六章貪心法任何問題，通常都有n個輸入和一些約束條件。任何滿足這些約束條件的子集可稱為一個可能解。最佳解是滿足目標函數(shù)達到最大值或最小值的一個可能解，而目標函數(shù)是問題中給定的。貪心法是一個多步?jīng)Q策法，每一步的選擇都使得能構(gòu)成問題的一個可能解（即滿足問題的全部約束條件），同時使目標函數(shù)的值增加最快或增加最小。貪心法的選擇過程是以某些最優(yōu)化量度為根據(jù)，而最優(yōu)化量度有時可以是目標函數(shù)本身，有時也可能是別的量度。最優(yōu)化量度的選擇是貪心法的關(guān)鍵。2024/12/291156.1背包問題背包問題的來源：設(shè)某港口有n種不同的貨物送往某地，每種貨物的總重量是已知的，各種不同貨物的運價也是確定的。某支船隊承運部分貨物，船隊的總噸位是確定的。每種貨物允許分批發(fā)送。考慮這支船隊?wèi)?yīng)裝運哪些貨物才能使它一次獲得的運費最多？2024/12/291166.1背包問題背包問題的一般描述：給定n種不同的物品和一個背包。物品i的重量是Wi，背包容量為M。假定物品i的一部分xi(0≤xi≤1)，被放進背包里，就會得到利潤

Pixi。因為背包的容量為M，要求被裝進的物品的總重量不超過M（若只考慮物重而不考慮其形狀和體積）。問應(yīng)怎樣選擇物品的種類和數(shù)量，使背包裝滿，而獲得最大的利潤。2024/12/291176.1背包問題背包類問題還可形式化描述為：給定M>0，Wi>0，Pi>0，1≤i≤n，使之滿足：使：達到最大。滿足0≤xi≤1的任何向量（x1,x2,…xn）都是一個可能解。這樣的解顯然有無窮多個。而最佳解必需是使式（6.2）的值達到最大的一個可能解。（6.1）（6.2）2024/12/291186.1背包問題例：給定n=3，M=40，（W1,W2,W3）=（28,15,24）,(p1,p2,p3)=(35,25,24)。以下是此例的五個可能解：

（x1,x2,x3）∑Wixi∑pixi（1）（1,4/5,0）4055（2）（1/2,1,1/3）3750.5（3）（1/28,1,1）4050.25（4）（5/7,1,5/24）4055（5）（25/28,1,0）4056.252024/12/291196.1背包問題對于這個簡單的實例，因為它的可能解有無窮多個，所以用組合的方法求最佳解是行不通的?？紤]，如果成立，最佳解將取xi=1。因此，不妨假定成立。這就不可能取一切xi=1。在此前提下，任何最佳解都必須將背包裝滿。同時，由于pi>0，使利潤增加。這樣得到的解比原來的解要好。2024/12/291206.1背包問題人們可能會想到的貪心的策略：（1）按pi遞減順序裝包（效益增長最快）每次選擇利潤Pi最大的物品裝包，使得目標函數(shù)增加最快。當(dāng)放不下時，才選擇一個適當(dāng)?shù)膞i<1，使物品裝滿，可求出每一種貨物裝入背包的比例X(x1,x2,x3)x1=1，CU=M-28=40-28=12，

x2=CU/W2=12/15=4/5，CU=0，

x3=0

所以，X=(1,4/5,0)，2024/12/291216.1背包問題（2）按Wi非遞減順序裝包（背包容量消耗最慢）

x2=1，CU=M-15=40-15=25，

x3=1，CU=25-24=1x1=1/28

所以，X=(1/28,1,1)。（3）按Pi/Wi（單位重量效益）遞減順序裝包每次選擇利潤與重量比最大的物品先裝包。先算出每種貨物的單位重量效益：(35/28,25/15,24/24)x2=1，CU=25x1=25/28

2024/12/291226.1背包問題總結(jié)：由上面的結(jié)果可看出，策略(1)顯然不是最佳解，因為這種選擇方法雖然每一步都使目標函數(shù)得到最大的增量，但由于背包也很快背裝滿了，加入目標函數(shù)的Pi的個數(shù)少了，不一定能使目標函數(shù)達到最大。策略(2)也不是最佳解，雖然背包的重量上升很慢，卻沒有兼顧利潤的增長速度，不能保證得到最佳解。策略(3)考慮到利潤增長和容量消耗二者的綜合效果，因此可以得到一個相對的最佳解。

2024/12/29123背包問題的貪心算法：Input:P(1,2…n),W(1,2…n),MOutput:x1,x2…xnVoidGreedy(){ floatP[],W[],X[],M,CU;inti,n;

輸入P[1,2…n],W[1,2…n],M;//按p[i]/w[i]從大到小的順序輸入

for(i=1;i<=n;i++){x[i]=0;}CU=M//CU是背包的剩余容量

intI=1；

while(W[I]<=CU){//背包未滿

x[I]=1;CU=CU-W[I];I=I+1;}x[I]=CU/W[I];}2024/12/291246.2多處理機調(diào)度設(shè)有n臺相同的處理機P1,P2,…,Pn，處理m個獨立的作業(yè)J1,J2,…,Jm，以互不相關(guān)的工作方式工作。規(guī)定：任何作業(yè)可以在任何一臺處理機上運行，但未完工前不允許中斷作業(yè)；作業(yè)也不能折分成更小的子作業(yè)。多處理機調(diào)度：已知作業(yè)Ji需要的處理機時間為ti，i=1,2,…,m。我們的任務(wù)是給出一種作業(yè)調(diào)度方案，使m個作業(yè)在盡可能短的時間內(nèi)，由n臺處理機完成。2024/12/291256.2多處理機調(diào)度例：設(shè)有三臺處理機和九個作業(yè)，這些作業(yè)需要的運行時間分別是81，40，26，4，65，98，53，71，15。按上述調(diào)度法則，各處理機分配的作業(yè)表將如下圖所示?？偼旯r間是166。

P1P2P3J181J753J44J240J698J871J326J565J915（a）一種簡單的多處理機調(diào)度方案2024/12/291266.2多處理機調(diào)度P1P2P3J698J240J44J181J753J326J271J565J915（a）先長后短調(diào)度方案（a）是按作業(yè)花費時間的長短進行調(diào)度的，把需時較長的作業(yè)優(yōu)先安排，先將作業(yè)按運行時間的長短從大到小排成非遞增序，然后給空閑的處理機依次分配作業(yè)?？偼旯r間是160。2024/12/291276.2多處理機調(diào)度P1P2P3J698J753J181J240J326J44J871J565J915（b）最佳調(diào)度方案（b）是本例的一個最佳調(diào)度方案。它們的完工時間是151。由此可見貪心算法得到的不一定是最佳方案。2024/12/29128第七章回溯法問題描述算法思想狀態(tài)空間樹皇后問題算法復(fù)雜度分析2024/12/291297.1問題分析求一個n元向量（x1,x2,……,xn）,使之滿足對問題的某個判定函數(shù)B（x1,x2,……,xn

）規(guī)定的條件。若Xi∈i,||Si||=Mi,則所有可能的選擇有mi種,對Xi的取值有明確要求，稱為顯約束。判斷函數(shù)規(guī)定的約束成為隱約束。2024/12/291307.2算法思想

從部分分量（x1,x2,…,xi）出發(fā)（i=1，2，…，n-1),選擇xi+1,如果（x1,x2,…,xi+1）滿足判定函數(shù)規(guī)定的條件，且i+1=n，則得到一個解；若（x1,x2,…,xi+1）滿足判定函數(shù)，但i+1<n,繼續(xù)選擇xi+2，若（x1,x2,…,xi）不滿足判定函數(shù)，則另選xi+1，如果可供選擇的xi+1均不滿足判定條件，則重新選擇xi（回溯）.2024/12/291317.2算法思想注意：判定函數(shù)的設(shè)計應(yīng)使其部分向量可計算！2024/12/291327.3狀態(tài)空間樹為了我們敘述的方便，我們在這里先介紹一些相關(guān)的概念，回溯法是采用體統(tǒng)地搜索給定問題的解空間的方法來確定問題的解。使用一種所謂解空間的樹形結(jié)構(gòu)將使這種搜索容易實現(xiàn)。對于一個解空間，可能有很多樹形結(jié)構(gòu)與之相對應(yīng)。相關(guān)的例子請參照課本。我們現(xiàn)在來定義解空間樹形結(jié)構(gòu)的一些術(shù)語。2024/12/291337.3狀態(tài)空間樹樹上的每一個節(jié)點定義了一個“問題狀態(tài)”；從根到每個節(jié)點的所有路徑定義了這一問題的“狀態(tài)空間“；“問題狀態(tài)”集的子集S組成了問題的“解狀態(tài)集”；可以生孩子的節(jié)點成為“活節(jié)點”，存儲活節(jié)點的表成為活節(jié)點表；2024/12/291347.3狀態(tài)空間樹正在生孩子的節(jié)點稱為擴展節(jié)點；不能生孩子的節(jié)點稱為死節(jié)點。2024/12/291357.4皇后問題介紹完相關(guān)的概念后，我們將介紹一個關(guān)于回溯法的例子，當(dāng)然，這個例子具有廣泛的代表性，這就是皇后問題。2024/12/291367.4皇后問題問題：

n個皇后，置于n*n的方格內(nèi)，如果任何兩個皇后處于同一行，同一列，或處于與邊線成45°角的斜線上，都會遭到對方攻擊，求一種互不遭到攻擊的狀態(tài)。2024/12/291377.4皇后問題我們規(guī)定第i個皇后位于第i行，n個皇后所在的列構(gòu)成一個n元向量（x1,x2,…,xi），xi∈{1，2，…，n}.2024/12/291387.4皇后問題皇后甲（i,j）皇后乙（k,l）

|(i-k)/(j-l)|≠1B=(i-k)/(j-l)2024/12/291397.4皇后問題下面我們已四皇后問題為例：首先：i=1（放置第1個皇后）（12024/12/291407.4皇后問題i=2

（1，2×（因（1-2）/（1-2）=1）故（1，32024/12/291417.4皇后問題i=3（1，3，2×（1，3，4×

我們發(fā)現(xiàn)第三個皇后已經(jīng)沒有合適的位置，此時需要重新放置第（i-1）個（