第一講算法基礎(chǔ)

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

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

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

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

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

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

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

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

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

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

注意事項(xiàng)：避免寫成自然段（2）算法框圖法

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

1.r=m%n;2.循環(huán)直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.輸出n;歐幾里德算法（4）高級程序設(shè)計語言描述法優(yōu)點(diǎn)：能由計算機(jī)執(zhí)行缺點(diǎn)：抽象性差，對語言要求高使用方法：算法需要驗(yàn)證注意事項(xiàng)：將算法寫成子函數(shù)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算法設(shè)計的一般過程充分理解要解決的問題數(shù)學(xué)模型擬制---建立符合要求數(shù)學(xué)模型，設(shè)計相關(guān)約束條件算法詳細(xì)設(shè)計---選擇算法設(shè)計策略，確定數(shù)據(jù)結(jié)構(gòu)算法描述---描述工具將算法具體過程描述下來算法思路的正確性驗(yàn)證算法分析---時間、空間復(fù)雜性算法的計算機(jī)實(shí)現(xiàn)和測試文檔資料的編制算法設(shè)計的一般過程

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

4.確定適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)

5．算法設(shè)計技術(shù)6．描述算法

7．跟蹤算法

8．分析算法的效率

9．根據(jù)算法編寫代碼

著名公式

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

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

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

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

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

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

1.大O符號(上界）定義1.1若存在兩個正的常數(shù)c和n0，對于任意n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))n0問題規(guī)模n執(zhí)行次數(shù)n0之前的情況無關(guān)緊要T(n)c×f(n)f(N)是T(N)的一個上界，即T(N)的階不高于f(N)的階根據(jù)O的定義，容易證明它有如下運(yùn)算規(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是一個正的常數(shù)；

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

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

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

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

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

intA[n]-----按次序存放1~n個數(shù)排列算法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]);}}時間復(fù)雜度：采用后向代入法計算可得到通項(xiàng)公式： T(n)=nT(n-1) =n(n-1)T(n-2)=……

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

時間復(fù)雜度：O(n!)遞歸算法的空間復(fù)雜度：算法的遞歸深度全排列算法perm共執(zhí)行了n次遞歸深度為n空間復(fù)雜度(遞歸)：O(n)回到Fibonacci數(shù)列問題functionFib1(n)ifn=1return1ifn=2return1returnFib1(n-1)+Fib1(n-2)同一個子問題被反復(fù)求解!Fibonacci數(shù)列一個較好的算法子問題: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]它有多快?運(yùn)算數(shù)與n成比例.[以前的方法:20.7n]F200現(xiàn)在可在合理時間內(nèi)計算出來,F2000和F20000也一樣.啟示

:恰當(dāng)?shù)乃惴ㄊ故虑閺氐赘挠^

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

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

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

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