第一講算法基礎(chǔ)

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

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

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

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

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

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

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

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

算法是滿足上述性質(zhì)的指令序列。程序：1.1.1 算法的特征歐幾里德算法mnr例：歐幾里德算法——輾轉(zhuǎn)相除法求兩個(gè)自然數(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個(gè)標(biāo)準(zhǔn)正確性：在合理的數(shù)據(jù)輸入下，能在有限的時(shí)間內(nèi)得出正確的結(jié)果?？勺x性：應(yīng)易于人的理解，易于調(diào)試。健壯性：具備檢查錯(cuò)誤和對(duì)錯(cuò)誤進(jìn)行適當(dāng)處理的能力。效率：算法執(zhí)行時(shí)所需計(jì)算機(jī)資源的多少，包括運(yùn)行時(shí)間和存儲(chǔ)空間。1.1.3算法的描述形式（1）自然語(yǔ)言優(yōu)點(diǎn)：容易理解缺點(diǎn)：冗長(zhǎng)、不夠嚴(yán)謹(jǐn)、二義性使用方法：粗線條描述算法思想

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

優(yōu)點(diǎn)：流程圖、盒圖，流程直觀、簡(jiǎn)潔、明了，便于理解和交流缺點(diǎn)：缺少嚴(yán)密性、靈活性使用方法：描述簡(jiǎn)單算法注意事項(xiàng)：注意抽象層次1.1.3算法的描述形式N開(kāi)始輸入m和nr=m%nr=0m=n；n=r輸出n結(jié)束Y歐幾里德算法（3）偽代碼語(yǔ)言描述法偽代碼（Pseudocode）：介于自然語(yǔ)言和程序設(shè)計(jì)語(yǔ)言之間的方法，它采用某一程序設(shè)計(jì)語(yǔ)言的基本語(yǔ)法，操作指令可以結(jié)合自然語(yǔ)言來(lái)設(shè)計(jì)。（算法語(yǔ)言）優(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）高級(jí)程序設(shè)計(jì)語(yǔ)言描述法優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行缺點(diǎn)：抽象性差，對(duì)語(yǔ)言要求高使用方法：算法需要驗(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è)計(jì)的一般過(guò)程充分理解要解決的問(wèn)題數(shù)學(xué)模型擬制---建立符合要求數(shù)學(xué)模型，設(shè)計(jì)相關(guān)約束條件算法詳細(xì)設(shè)計(jì)---選擇算法設(shè)計(jì)策略，確定數(shù)據(jù)結(jié)構(gòu)算法描述---描述工具將算法具體過(guò)程描述下來(lái)算法思路的正確性驗(yàn)證算法分析---時(shí)間、空間復(fù)雜性算法的計(jì)算機(jī)實(shí)現(xiàn)和測(cè)試文檔資料的編制算法設(shè)計(jì)的一般過(guò)程

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

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

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

7．跟蹤算法

8．分析算法的效率

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

著名公式

Algorithm+DataStructure=Programming好的算法提高求解問(wèn)題的效率節(jié)省存儲(chǔ)空間需要解決的問(wèn)題問(wèn)題一個(gè)求解算法：算法設(shè)計(jì)技術(shù)算法算法的評(píng)價(jià)：

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

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

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

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

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

1.大O符號(hào)(上界）定義1.1若存在兩個(gè)正的常數(shù)c和n0，對(duì)于任意n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))n0問(wèn)題規(guī)模n執(zhí)行次數(shù)n0之前的情況無(wú)關(guān)緊要T(n)c×f(n)f(N)是T(N)的一個(gè)上界，即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是一個(gè)正的常數(shù)；

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

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

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

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

{if(k==1){

輸出一個(gè)排列}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]);}}時(shí)間復(fù)雜度：采用后向代入法計(jì)算可得到通項(xiàng)公式： T(n)=nT(n-1) =n(n-1)T(n-2)=……

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

時(shí)間復(fù)雜度：O(n!)遞歸算法的空間復(fù)雜度：算法的遞歸深度全排列算法perm共執(zhí)行了n次遞歸深度為n空間復(fù)雜度(遞歸)：O(n)回到Fibonacci數(shù)列問(wèn)題functionFib1(n)ifn=1return1ifn=2return1returnFib1(n-1)+Fib1(n-2)同一個(gè)子問(wèn)題被反復(fù)求解!Fibonacci數(shù)列一個(gè)較好的算法子問(wèn)題: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)在可在合理時(shí)間內(nèi)計(jì)算出來(lái),F2000和F20000也一樣.啟示

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

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

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

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

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