算法設(shè)計(jì)與分析

AlgorithmDesignandAnalysis課程要求掌握常用的算法設(shè)計(jì)策略、算法復(fù)雜度分析方法授課方式：講授考核方式：閉卷筆試教材《算法設(shè)計(jì)技巧與分析》，M.H.Alsuwaiyel著,電子工業(yè)出版社相關(guān)參考文獻(xiàn)AlgorithmDesignTechniquesandAnalysis,M.H.Alsuwaiyel.(影印本).電子工業(yè)出版社.2003算法導(dǎo)論(第2版)，ThomasH.Cormen等著，潘金貴等譯，機(jī)械工業(yè)出版社，2006.計(jì)算機(jī)算法設(shè)計(jì)與分析(第3版),王曉東,電子工業(yè)出版社,2007.算法設(shè)計(jì)與分析，王紅梅編著，清華大學(xué)出版社，2006.1算法引論歷史背景算法復(fù)雜度與漸近分析方法如何估計(jì)算法的復(fù)雜度算法復(fù)雜度分析的意義歷史背景階段1：二十世紀(jì)30年代，能否使用一個(gè)有效的過(guò)程來(lái)求解一個(gè)問(wèn)題(相當(dāng)于現(xiàn)在算法的概念)一直是人們所關(guān)注的。當(dāng)時(shí)的焦點(diǎn)是將問(wèn)題進(jìn)行分類(lèi)：可解或是不可解。關(guān)注問(wèn)題是否可以求解的領(lǐng)域稱(chēng)為可計(jì)算理論(computabilitytheoryortheoryofcomputation)。出現(xiàn)了一系列的計(jì)算模型，例如：calculusofChurch、PostmachinesofPost、TuringmachinesofTuring、RAMmodelofcomputation。階段2：隨著數(shù)字計(jì)算機(jī)的出現(xiàn)，人們?cè)絹?lái)越關(guān)注于那些可求解的問(wèn)題。一開(kāi)始，人們滿(mǎn)足于能夠在一定的時(shí)間內(nèi)解決一個(gè)特定的問(wèn)題，而不去關(guān)注所需要的資源。慢慢地，人們需要考慮在有限資源的條件下高效地解決問(wèn)題。這就導(dǎo)致了計(jì)算復(fù)雜度(computationalcomplexity)這一新學(xué)科的誕生。在這個(gè)領(lǐng)域，主要是研究解決可求解問(wèn)題時(shí)所需要的資源，主要是時(shí)間和空間復(fù)雜性。有時(shí)候，其他的資源也需要考慮，例如，通信代價(jià)、需要使用的處理器的個(gè)數(shù)(使用并行計(jì)算模型)等等。引例：搜索問(wèn)題給定已經(jīng)排好序(不妨假設(shè)為非降序)的n個(gè)元素A[1…n],現(xiàn)在要判定一個(gè)給定的元素x是否在此數(shù)組中出現(xiàn)。方法1：順序搜索方法2：二分搜索二分搜索算法輸入：非降序排列的數(shù)組A[1…n]和元素x輸出：如果x=A[j],1

j

n,則輸出j,否則輸出0.1.low←1;high←n;j←02.while(low

high)and(j=0)3.mid←

(low+high)/2

4.ifx=A[mid]thenj←mid5.elseifx<A[mid]thenhigh←mid-16.elselow←mid+17.endwhile8.returnj分析最好情形：比較1次最壞情形：比較

logn

+1次每次循環(huán)都要拋棄一些元素，例如第二次循環(huán)時(shí)，剩余元素為A[1…mid-1]或A[mid+1…n]，不妨設(shè)為A[mid+1…n]，則剩余的元素個(gè)數(shù)是

n/2

第j次while循環(huán)時(shí)，剩余元素的個(gè)數(shù)是

n/2j-1

或者找到x，或者程序在子序列長(zhǎng)度達(dá)到1時(shí)終止搜索,此時(shí)

n/2j-1

=1

1

n/2j-1<2

2j-1

n<2j

logn<j

logn+1

j=

logn

+1算法及其性質(zhì)算法是對(duì)問(wèn)題求解過(guò)程的準(zhǔn)確描述，由有限條指令組成，這些指令能在有限時(shí)間內(nèi)執(zhí)行完畢并產(chǎn)生確定性的輸出。算法需滿(mǎn)足的4個(gè)性質(zhì)：輸入：零個(gè)或多個(gè)外部量作為輸入。輸出：至少產(chǎn)生一個(gè)量作為輸出,它(們)與輸入量之間存在某種特定的聯(lián)系。確定性：組成算法的每條指令都是清晰、無(wú)歧義的。有限性：每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時(shí)間也有限。程序與算法的區(qū)別：程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。程序可以不滿(mǎn)足算法的有限性性質(zhì)。算法的復(fù)雜度復(fù)雜度：算法運(yùn)行時(shí)需要耗費(fèi)計(jì)算機(jī)資源的量，可以分為時(shí)間復(fù)雜度和空間復(fù)雜度。算法復(fù)雜度依賴(lài)于三個(gè)方面：待求解問(wèn)題的規(guī)模、算法的輸入和算法本身。用n,I,A分別表示問(wèn)題的規(guī)模、算法的輸入和算法本身，用表示C復(fù)雜度，則有：C=F(n,I,A)。如果將時(shí)間復(fù)雜度和空間復(fù)雜度分開(kāi)，則有T=T(n,I,A)和S=S(n,I,A)。通常，我們讓A隱藏在復(fù)雜度函數(shù)名中，所以有T=T(n,I)和S=S(n,I)。由于時(shí)間復(fù)雜度和空間復(fù)雜度概念類(lèi)似，計(jì)量方法類(lèi)似，且空間復(fù)雜度分析相對(duì)簡(jiǎn)單，因此本課程主要討論算法的時(shí)間復(fù)雜度。T=T(n,I)的具體化假設(shè)計(jì)算機(jī)提供k種元運(yùn)算，分別記為O1,O2,…,Ok。所謂元運(yùn)算指的是這樣一類(lèi)運(yùn)算：不管使用什么樣的算法和輸入數(shù)據(jù)，該運(yùn)算的上階是一個(gè)常數(shù)時(shí)間(關(guān)于階，參見(jiàn)后文描述)。例如，算術(shù)運(yùn)算、比較、邏輯、賦值等。元運(yùn)算Oi每執(zhí)行一次需要的時(shí)間為ti。對(duì)于給定的算法A，已經(jīng)知道用到的元運(yùn)算Oi

的執(zhí)行次數(shù)為ei,i=1,...,k。很顯然ei是n和I的函數(shù)，即ei=ei(n,I)。至此，就有：分析T(n,I)給出的是在問(wèn)題規(guī)模為n，輸入為I時(shí)的時(shí)間復(fù)雜度。但是我們不可能，也沒(méi)必要對(duì)每種可能的輸入都去求其時(shí)間復(fù)雜度。通?？梢钥紤]3種情形下的時(shí)間復(fù)雜度：最壞情形、最好情形以及平均情形。實(shí)踐表明：可操作性最強(qiáng)、最有實(shí)際價(jià)值的是算法最壞情形下的時(shí)間復(fù)雜度。使用算法的絕對(duì)運(yùn)行時(shí)間來(lái)度量其時(shí)間復(fù)雜度？

－NO一個(gè)編程實(shí)現(xiàn)了的算法的具體運(yùn)行時(shí)間，不僅僅和算法本身相關(guān)，還和很多其他因素密切相關(guān)：機(jī)器性能、編程語(yǔ)言、編譯器、編程技巧等等。在分析一個(gè)算法的運(yùn)行時(shí)間時(shí)，通常將該算法和其他算法在同一問(wèn)題、甚至是不同的問(wèn)題上進(jìn)行比較，因而運(yùn)行時(shí)間只能是相對(duì)的，而不是絕對(duì)的。希望算法的描述不僅獨(dú)立于機(jī)器，并且可以以任何語(yǔ)言來(lái)加以描述，包括自然語(yǔ)言。希望使用度量算法運(yùn)行時(shí)間的準(zhǔn)則不依賴(lài)于技術(shù)的進(jìn)步。不僅僅關(guān)注小規(guī)模輸入下的，而且還關(guān)注在大規(guī)模輸入下的情形。漸近分析(AsymptoticAnalysis)對(duì)于T(n)，當(dāng)n單調(diào)遞增并趨于∞時(shí)，T(n)也是單調(diào)增加并趨于∞。為此,如果存在一個(gè)T*(n)，使得當(dāng)n→∞時(shí)有(T(n)?T*(n))/T(n)→0,就稱(chēng)T*(n)是T(n)當(dāng)n→∞的漸近性態(tài)，或稱(chēng)T*(n)是給定算法在n→∞時(shí)的漸近復(fù)雜度。顯然,T*(n)不是唯一的。我們可以盡可能的選擇簡(jiǎn)單的T*(n)，然后使用T*(n)來(lái)替代T(n)作為n→∞的復(fù)雜度度量。漸近復(fù)雜度分析只要關(guān)心T*(n)的階就可以了(在n充分大時(shí))，不必關(guān)心其中的常數(shù)因子。4種階：O,Ω,Θ,和o假設(shè)：f(n)和g(n)是定義在正數(shù)集上的正函數(shù)。(此假設(shè)的實(shí)際意義?)定義1(O)：如果存在正的常數(shù)C和自然數(shù)n0，使得當(dāng)n≥n0時(shí)，有f(n)≤C·g(n)，則稱(chēng)函數(shù)f(n)在n充分大時(shí)有上有界，且g(n)是它的一個(gè)上界，記做f(n)=O(g(n))，并稱(chēng)f(n)的階不高于g(n)的階。例子例：f(n)＝n2，g(n)＝n3。因?yàn)椋捍嬖趎0＝1，C=1，當(dāng)n≥n0時(shí)，有n2≤Cn3,所以：n2=O(n3)例：f(n)＝n2，g(n)＝n2。因?yàn)椋捍嬖趎0＝1，C=1,n≥n0時(shí)，有n2≤Cn2,所以：n2=O(n2)例：f(n)＝n2+nlog(n)

，g(n)＝n2。同樣有n2+nlog(n)=O(n2)例：f(n)＝an2+nlog(n)

，g(n)＝n2。同樣有an2+nlog(n)=O(n2)例：f(n)＝an2+nlog(n)+c

，g(n)＝n2。同樣有an2+nlog(n)+c=O(n2)小結(jié)在進(jìn)行階的運(yùn)算時(shí)，常系數(shù)、低的階以及常數(shù)項(xiàng)可以忽略。根據(jù)O的定義，得到的是在問(wèn)題規(guī)模充分大時(shí)，算法復(fù)雜度的一個(gè)上界。上界的階越低則評(píng)估越有價(jià)值。運(yùn)算規(guī)則O(f)+O(g)=O(max(f,g));O(f)·O(g)=O(f·g);O(C·f(n))=O(f(n));f=O(f);Ω定義2(Ω)：如果存在正的常數(shù)C和自然數(shù)n0

，使得當(dāng)n≥n0時(shí)，有f(n)≥C·g(n)，則稱(chēng)函數(shù)f(n)在n充分大時(shí)有下有界，且g(n)是它的一個(gè)下界，記做f(n)=Ω(g(n))，并稱(chēng)f(n)的階不低于g(n)的階。下界的階越高，則評(píng)估精度越高，也就越有價(jià)值。Θ和o定義3(Θ)：f(n)=Θ(g(n))，當(dāng)且僅當(dāng)f(n)=O(g(n))，且f(n)=Ω(g(n))，稱(chēng)f(n)和g(n)是同階。定義4(o)：對(duì)于任意給定的ε>0，存在正整數(shù)n0

，使得當(dāng)n≥n0

時(shí)，有f(n)/g(n)≤ε，則稱(chēng)函數(shù)f(n)在n充分大時(shí)的階比g(n)低，記為f(n)=o(g(n))。小結(jié)進(jìn)行算法的時(shí)間復(fù)雜度分析，就是求其T(n)，并用O、Ω或是Θ以盡可能簡(jiǎn)單的形式進(jìn)行表示。理想情況下，希望能夠使用Θ表示算法的時(shí)間復(fù)雜性。退而求其次，可以使用O或是Ω。使用O時(shí)，希望估計(jì)的上界的階越小越好。使用Ω時(shí)，希望估計(jì)的下界的階越大越好。算法耗費(fèi)時(shí)間隨問(wèn)題規(guī)模的變化Algorithm12345Timefunction(ms)33n46n

lgn13n23.4n32nInputsize(n)Solutiontime100.00033sec.0.0015sec.0.0013sec.0.0034sec.0.001sec.1000.0033sec.0.03sec.0.13sec.3.4sec.4

1016yr.1,0000.033sec.0.45sec.13sec.0.94hr.10,0000.33sec.6.1sec.22min.39days100,0003.3sec.1.3min.1.5days108yr.TimeallowedMaximumsolvableinputsize(approx.)1second30,0002,00028067201minute1,800,00082,0002,20026026階運(yùn)算的幾個(gè)實(shí)例=(1)=解：因?yàn)樗?2)解:a.因?yàn)橛?b.又因?yàn)閯t有命題成立(3)解:因?yàn)?不準(zhǔn)確)a.b.所以換底公式所以亦即12n12n+1(4)√√x估計(jì)算法的時(shí)間復(fù)雜度計(jì)算迭代次數(shù)使用遞歸方程頻度分析計(jì)算迭代次數(shù)通常，程序的運(yùn)行時(shí)間和程序的迭代次數(shù)成比例。因此計(jì)算程序的迭代次數(shù)就可以作為算法運(yùn)行時(shí)間的指示器。這在很多算法中都可以得到應(yīng)用，如查找、排序等等。計(jì)算迭代次數(shù)輸入：n(n=2k

，k為某一正整數(shù))輸出：count1.count←02.whilen≥13.forj←1ton4.count←count+1//執(zhí)行一次耗費(fèi)時(shí)間設(shè)為a5.endfor6.n←n/2//執(zhí)行一次耗費(fèi)時(shí)間設(shè)為d7.endwhile8.returncount

分析：while迭代的次數(shù)是k+1次(因?yàn)閚≥1可以寫(xiě)成n≥20,運(yùn)行過(guò)程n=2k→20)，k=logn。在每次while循環(huán)里面for依次執(zhí)行n，n/2,n/4,…,1次，所以，算法的時(shí)間復(fù)雜度為：思考？為什么在上面計(jì)算算法的時(shí)間復(fù)雜度時(shí)不考慮step6,而只是考慮step4呢？如果同時(shí)考慮step4和step6，我們有：小結(jié)：使用計(jì)算迭代次數(shù)的技術(shù)來(lái)分析算法的時(shí)間復(fù)雜度時(shí)，只需要考慮最深層次的迭代。例：輸入：正整數(shù)n輸出：step5的執(zhí)行次數(shù)1.count←02.fori←1ton3.m←

n/i

4.forj←1tom5.count←count+16.endfor7.endfor8.returncount分析：Step5的執(zhí)行次數(shù)依次為：

n,

n/2

,

n/3

,…,

n/n

因?yàn)樗?使用遞歸方程輸入：非降序排列的數(shù)組A[1…n]和元素x輸出：如果x=A[j],1

j

n,則輸出j,否則輸出0.1.low←1;high←n;j←02.while(low

high)and(j=0)3.mid←

(low+high)/2

4.ifx=A[mid]thenj←mid5.elseifx<A[mid]thenhigh←mid-16.elselow←mid+17.endwhile8.returnj3頻度分析對(duì)于有些算法，要像前面那樣準(zhǔn)確地分析算法的運(yùn)行時(shí)間非常麻煩，有時(shí)甚至是不可能的。這時(shí)候，可以使用頻度分析，我們將在后續(xù)章節(jié)中進(jìn)行講解。(單源最短路徑、Prim算法等等)算法復(fù)雜度分析的意義已知待求解問(wèn)題的多種