第一講算法基礎

第一章算法及基礎知識徐克奇xkq@教材

《算法設計與分析》王秋芬、呂聰穎等編著清華大學出版社2011年8月參考教材

1.《算法設計與分析》（第二版）王曉東編著清華大學出版社2008年1月

2.《算法設計與分析——c++語言描述》陳慧南編著電子工業(yè)出版社2006年5月《算法概論》(注釋版).SanjoyDasgupta等著，錢楓等注釋，機械工業(yè)出版社，2009《算法導論》（第二版影印版）．(美)Corrmen.T.H.北京：高等教育出版社，2002．5主要內容第1章 算法及基礎知識第2章 貪心法第3章 分治法第4章 動態(tài)規(guī)劃第5章 搜索法第6章 隨機化算法第7章線性規(guī)劃問題第8章數論算法及計算幾何算法第9章NP完全理論為什么要學習算法？算法是計算機科學的基石。沒有算法，計算機程序將不復存在學習算法可以提高人們的分析能力。算法可以看作是解決問題的一類特殊方法——它雖非問題的答案，但它是經過準確定義的，用來獲得答案的過程。無論是否涉及計算機，特定的算法設計技術都能看作是問題求解的有效策略。算法的魅力：思考程序=算法+數據結構

算法讓我們上一個更高的臺階一個皇室數學挑戰(zhàn)問題(1202)假設兔子出生一個月后能繁殖，以后每月產一個孩子，一直下去直到永遠。從一個兔子開始，問n個月后有多少個兔子？LeonardoFibonacci1170-1250兔子的繁殖成熟不成熟初始一個月二個月三個月四個月五個月兔子出生一個月后能繁殖，以后每月產一個孩子，一直下去……。設Fn是n個月時兔子的數量F1=1F2=1Fn=Fn-1+Fn-2Fibonaccinumbers:1,1,2,3,5,8,13,21,34,55,89,…數量增長非?？?F30>106!事實上,Fn≈20.694n

≈1.6n,指數級增長.可以證明(3/2)^n<Fn<(5/3)^n計算Fibonacci數functionFib1(n)ifn=1return1ifn=2return1returnFib1(n-1)+Fib1(n-2)一個遞歸算法關于算法我們總要問二個問題:它能正確工作嗎?能–它直接實現(xiàn)了Fibonacci數的定義.它要花多長時間?這不是很明顯的……運行時間分析functionFib1(n)ifn=1return1ifn=2return1returnFib1(n-1)+Fib1(n-2)設T(n)=計算F(n)的步數那么:T(n)>T(n-1)+T(n-2)但是Fn=Fn-1+Fn-2.因此T(n)>Fn指數級時間...這有多糟糕?例.計算F200大概需要2^140個運算.在一個快速計算機上要花多長時間?（在NECEarthSimulator上花2^92秒）指數級時間都那么糟糕嗎?Earthsimulator計算機需要292秒計算F200.TimeinsecondsInterpretation21017分22012日23032年240山洞繪畫作品

(一萬五千年到一萬七千年之間)245

直立人發(fā)現(xiàn)火251恐龍滅絕257地球形成260宇宙起源剖析為什么花這么長時間?讓我們剖析該遞歸…functionFib1(n)ifn=1return1ifn=2return1returnFib1(n-1)+Fib1(n-2)同一個子問題被反復求解!好的算法很重要！學習算法要點:理解算法的概念。理解什么是程序，程序與算法的區(qū)別和內在聯(lián)系。掌握算法的計算復雜性概念。掌握用C++/JAVA語言描述算法的方法。1.1 算法的基本概念算法（Algorithm）：即在有限步驟內解一個數學問題的過程，步驟中常常包括某一操作的重復。（韋氏詞典）一個算法是解決一個問題或實現(xiàn)某一目標的逐步過程。（廣義）算法是有窮規(guī)則的集合，規(guī)定了一個解決某一特定類型問題的運算序列。（D.E.Knuth唐納德.E.克努特)輸入性：有零個或多個外部量作為算法的輸入。輸出性：算法產生至少一個量作為輸出。確定性：算法中每條指令清晰，無歧義。有窮性：算法中每條指令的執(zhí)行次數有限，執(zhí)行每條指令的時間也有限。（計算過程，時效）可行性：算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算后即可完成。是算法用某種程序設計語言的具體實現(xiàn)。程序可以不滿足算法的性質(4)即有窮性。如操作系統(tǒng)

算法是滿足上述性質的指令序列。程序：1.1.1 算法的特征歐幾里德算法mnr例：歐幾里德算法——輾轉相除法求兩個自然數m和n的最大公約數①輸入m

和n；②求m除以n的余數r；③若r等于0，則n為最大公約數，算法結束；否則執(zhí)行第④步；④將n的值放在m中，將r的值放在n中；⑤重新執(zhí)行第②步。歐幾里德算法1.1.1 算法的4個標準正確性：在合理的數據輸入下，能在有限的時間內得出正確的結果?？勺x性：應易于人的理解，易于調試。健壯性：具備檢查錯誤和對錯誤進行適當處理的能力。效率：算法執(zhí)行時所需計算機資源的多少，包括運行時間和存儲空間。1.1.3算法的描述形式（1）自然語言優(yōu)點：容易理解缺點：冗長、不夠嚴謹、二義性使用方法：粗線條描述算法思想

注意事項：避免寫成自然段（2）算法框圖法

優(yōu)點：流程圖、盒圖，流程直觀、簡潔、明了，便于理解和交流缺點：缺少嚴密性、靈活性使用方法：描述簡單算法注意事項：注意抽象層次1.1.3算法的描述形式N開始輸入m和nr=m%nr=0m=n；n=r輸出n結束Y歐幾里德算法（3）偽代碼語言描述法偽代碼（Pseudocode）：介于自然語言和程序設計語言之間的方法，它采用某一程序設計語言的基本語法，操作指令可以結合自然語言來設計。（算法語言）優(yōu)點：表達能力強，抽象性強，容易理解1.1.3算法的描述形式

1.r=m%n;2.循環(huán)直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.輸出n;歐幾里德算法（4）高級程序設計語言描述法優(yōu)點：能由計算機執(zhí)行缺點：抽象性差，對語言要求高使用方法：算法需要驗證注意事項：將算法寫成子函數1.1.3算法的描述形式#include<iostream.h>intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){cout<<CommonFactor(63,54)<<endl;}歐幾里德算法1.2算法設計的一般過程充分理解要解決的問題數學模型擬制---建立符合要求數學模型，設計相關約束條件算法詳細設計---選擇算法設計策略，確定數據結構算法描述---描述工具將算法具體過程描述下來算法思路的正確性驗證算法分析---時間、空間復雜性算法的計算機實現(xiàn)和測試文檔資料的編制算法設計的一般過程

1．理解問題2．預測所有可能的輸入3.在精確解和近似解間做選擇

4.確定適當的數據結構

5．算法設計技術6．描述算法

7．跟蹤算法

8．分析算法的效率

9．根據算法編寫代碼

著名公式

Algorithm+DataStructure=Programming好的算法提高求解問題的效率節(jié)省存儲空間需要解決的問題問題一個求解算法：算法設計技術算法算法的評價：

算法分析技術1.3算法分析算法復雜性=算法運行時所需要的計算機資源的量時間復雜性、空間復雜性影響時間復雜性的因素問題規(guī)模n、輸入序列I、算法本身A影響空間復雜性的因素算法本身、輸入輸出數據、輔助變量算法復雜性的權衡時間復雜度和空間復雜度相互影響（時間換空間或空間換時間）1.3算法分析三種情況下的復雜性（結合順序查找操作）最好情況Tmin（N)1次最壞情況Tmax（N)N次平均情況Tavg（N)(N+1)/2算法復雜性分析

當問題規(guī)模增大時，復雜度的極限行為稱為算法的漸進時間復雜度。算法時間復雜度最大問題規(guī)模1秒1分1小時A1n10006*1043.6*106A2nlogn14048932.0*105A3N2312441897A4N31039153A52n91521算法時間復雜度加速前最大問題規(guī)模加速后最大問題規(guī)模A1nS110*S1A2nlognS2約為10*S2A3N2S33.16*S3A4N3S42.15*S4A52nS5S5+3.3假設下一代計算機的速度是目前的10倍，下表是計算機加速后在相同的時間內可以解決的問題規(guī)模增量。

算法漸近復雜性態(tài)設算法的運行時間為T(n)，如果存在T*(n)，使得

就稱T*(n)為算法的漸進復雜性態(tài)或漸進時間復雜性。舉例：假設算法A的運行時間表達式為T1(n)T1(n)=30n4+20n3+40n2+46n+100

假設算法B的運行時間表達式為T2(n)T2(n)=1000n3+50n2+78n+10隨著n的增大，對算法的執(zhí)行時間影響最大的是最高次方。算法A的運行時間可記為：T*1(n)≈n4算法B的運行時間可記為：T*2(n)≈n3漸近符號:O---上界---下界---精確界（上界和下界）漸進符號

1.大O符號(上界）定義1.1若存在兩個正的常數c和n0，對于任意n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))n0問題規(guī)模n執(zhí)行次數n0之前的情況無關緊要T(n)c×f(n)f(N)是T(N)的一個上界，即T(N)的階不高于f(N)的階根據O的定義，容易證明它有如下運算規(guī)則：(1)O(f)+O(g)=O(max(f,g))；(2)O(f)+O(g)=O(f+g)；(3)O(f)O(g)=O(fg)；(4)O(Cf(N))=O(f(N))，其中C是一個正的常數；

(5)f=O(f)2.大Ω符號（下界）定義1.2若存在兩個正的常數c和n0，對于任意n≥n0，都有T(n)≥c×g(n)，則稱T(n)=Ω(g(n))n0問題規(guī)模n執(zhí)行次數n0之前的情況無關緊要T(n)c×g(n)漸進符號（續(xù)）

g(N)是T(N)的一個下界，即T(N)的階不低于g(N)的階3.Θ符號（同階）定義1.3若存在三個正的常數c1、c2和n0，對于任意n≥n0都有c1×f(n)≥T(n)≥c2×f(n)，則稱T(n)=Θ(f(n))

n0問題規(guī)模n執(zhí)行次數n0之前的情況無關緊要T(n)c2×f(n)c1×f(n)漸進符號（續(xù)）

當且僅當f(N)=O(g(N))且f(N)=Ω(g(N))。稱f(N)與g(N)同階。例:

求T(n)=10n+4的漸進上界O(n)算法分析中常見的復雜性函數幾種常見的時間復雜度函數按數量級從小到大的順序依次是：Θ(1),Θ(logn)，Θ(sqrt(n))，Θ(n)，Θ(nlogn)，Θ(n2)，Θ(n3)，Θ(2n)，Θ(n!)在多項式中，n的最高次指數是最主要的決定因素，常數項、低次冪項和系數都是次要的。例：求T(n)=amnm+am-1nm-1+…+a1n+a0的上界、下界根據定理1T(n)=Θ(nm)時間復雜度分析的基本規(guī)則主要考慮可執(zhí)行語句的情況：輸入、輸出、賦值語句，為O（1）；順序結構，采用漸進式O的求和規(guī)則來進行計算；選擇結構，考慮判定后所執(zhí)行語句的執(zhí)行時間O（max(T(s1),T(s2))）；循環(huán)結構，考慮循環(huán)判定條件和循環(huán)體語句的執(zhí)行時間，采用漸進式O的乘積規(guī)則來進行計算；復雜算法，先分割，然后采用漸進式O的求和規(guī)則和乘法規(guī)則來計算整個算法的時間復雜度；基本語句—對算法運行時間貢獻最大的原操作語句。當算法時間復雜性只依賴于問題規(guī)模時，選擇基本語句執(zhí)行次數來作為運行時間T(n)建立的依據。例：求數組中元素最大值空間復雜度算法所占用的存儲空間包括算法自身輸入、輸出輔助空間空間復雜度S(n)=O(f(n))，以最壞情況來分析例：插入法升序排序voidinsert_sort(intn,ints[]){inta,i,j;for(i=1;i<n;i++){a=s[i];j=i-1;while(j>=0;&&s[j]>a){s[j+1]=s[j];j--;}s[j+1]=a;}}1.4遞歸（是算法設計與描述的有力工具）子程序（或函數）直接調用自己或通過一系列調用語句間接調用自已，稱為遞歸。直接或間接調用自身的算法稱為遞歸算法。采用遞歸算法來求解問題的一般步驟：分析問題，尋找遞歸關系找出停止條件構建函數體n的階乘停止條件遞歸關系停止條件與遞歸關系是遞歸函數的兩個要素，遞歸函數只有具備了這兩個要素，才能在有限次計算后得出結果。Longlongfun(intn){if(n<0){printf(“illegalnumber!\n”);break;}elseif(n==0)return1;elsereturnn*fun(n-1);}例：排列問題問題描述n個元素，它們的編號為1,2,…,n，排列問題的目的是生成這n個元素的全排列。解題步驟分析遞歸關系找出停止條件設計遞歸函數算法設計思路將規(guī)模為n的排列問題轉化為規(guī)模為n-1的排列問題。將規(guī)模為n-1的排列問題轉化為規(guī)模為n-2的排列問題將問題規(guī)模一級一級降至1，1個元素的排列是它本身，此時到達遞推的停止條件。數組中的元素即為1個排列，然后進行回歸依次得到其它的排列。共要遞歸K次（K=n，n-1,n-2，…，1)當k=1輸出一個排列如何將規(guī)模為n的排列問題轉化為規(guī)模為n-1的排列問題。步驟1：數組的首元素為第一個元素，還需生成后面n-1個元素全排列。步驟2：將數組的第一個元素和第二個元素交換，數組的首元素為第二個元素，還需生成后面n-1個元素全排列。步驟3：將數組的第一個元素和第三個元素交換，數組的首元素為第三個元素，還需生成后面n-1個元素全排列。步驟4：…步驟n:數據結構：

intA[n]-----按次序存放1~n個數排列算法voidperm(inta[],intk,intn)

{if(k==1){

輸出一個排列}else

for(i=n-k;i<n;i++)

{

swap(a[n-k],a[i]);

perm(a,k-1,

n);

swap(a[n-k],a[i]);}}時間復雜度：采用后向代入法計算可得到通項公式： T(n)=nT(n-1) =n(n-1)T(n-2)=……

=n(n-1)(n-2)......2T(1) =n!

時間復雜度：O(n!)遞歸算法的空間復雜度：算法的遞歸深度全排列算法perm共執(zhí)行了n次遞歸深度為n空間復雜度(遞歸)：O(n)回到Fibonacci數列問題functionFib1(n)ifn=1return1ifn=2return1returnFib1(n-1)+Fib1(n-2)同一個子問題被反復求解!Fibonacci數列一個較好的算法子問題:F1,F2,…,Fn.依次求解它們并保存它們的值!functionFib2(n)Createanarrayfib[1..n]fib[1]=1fib[2]=1fori=3ton:fib[i]=fib[i-1]+fib[i-2]returnfib[n][1]它返回正確的答案嗎？[2]它有多快?運算數與n成比例.[以前的方法:20.7n]F200現(xiàn)在可在合理時間內計算出來,F2000和F20000也一樣.啟示

:恰當的算法使事情徹底改觀

。第三個算法用矩陣重寫F0=0,F1=1,Fn=Fn-1+Fn-2如下:因此只需快速計算多項式級vs.指數級運行時間如n,n2,n3是多項式級。運行時間如2n,en,2n是指數級.多項式是適當的指數級是不適當的在算法分析中，這是最基本的一個分界線.1.5基本數據結構順序表——鏈表連續(xù)存儲——離散存儲定位、插入、刪除?！犃蠪ILO——FIFOTop、bottom——Front、Rear樹概念基本術語結點的度:樹的度:葉子結點:分支結點:分支的個數樹中所有結點的度的最大值度為零的結點度大于零的結點DHIJM孩子結點、雙親結點、兄弟結點、堂兄弟祖先結點、子孫結點結點的層次:樹的深度：ABCDEFGHIJMKL假設根結點的層次為1,它的孩子結點為第二層，依此類推一個結點所在的層次，為其雙親結點所在的層次加1。樹中葉子結點所在的最大層次任何一棵非空樹是一個二元組

Tree=（root，F(xiàn)）其中：root被稱為根結點，

F被稱為子樹森林森林：是m（m≥0）棵互不相交的樹的集合ArootBEFKLCGDHIJMF樹的存儲結構雙親存儲結構typedefstruct{ElemTypedata;intparent;}Ptree[MaxSize];鏈存儲結構typedefstructnode{ElemTypedata;structnode*sons[MaxSons];}TSonNode;圖定義

圖(Graph)G由兩個集合V(Vertex)和E(Edge)組成,記為G=(V,E),其中V是頂點的有限集合,記為V(G),E是連接V中兩個不同頂點(頂點對)的邊的有限集合,記為E(G)。EACBDBCAFED圖的基本術語鄰接點相關邊路徑