算法分析與計(jì)算復(fù)雜性理論第一頁(yè)，共三十七頁(yè)，2022年，8月28日2課程簡(jiǎn)介

課程名稱

算法分析與計(jì)算復(fù)雜性理論

AnalysisofAlgorithmsandTheoryofComputationalComplexity

基本目的掌握組合算法設(shè)計(jì)的基本技術(shù)掌握算法分析的基本方法掌握計(jì)算復(fù)雜性理論的基本概念學(xué)習(xí)應(yīng)用算法理論處理實(shí)際問題第二頁(yè)，共三十七頁(yè)，2022年，8月28日3課程內(nèi)容順序算法設(shè)計(jì)的基本技術(shù)

分治策略動(dòng)態(tài)規(guī)劃回溯算法貪心法概率算法順序算法分析的基本方法

評(píng)價(jià)算法的標(biāo)準(zhǔn)

算法復(fù)雜性的估計(jì)問題復(fù)雜性的下界算法分析的實(shí)例計(jì)算復(fù)雜性理論

Turing機(jī)計(jì)算復(fù)雜性的概念

NP完全性理論及其應(yīng)用

NP完全理論的拓廣第三頁(yè)，共三十七頁(yè)，2022年，8月28日預(yù)計(jì)進(jìn)度安排內(nèi)容學(xué)時(shí)內(nèi)容學(xué)時(shí)1前言19Turing機(jī)22數(shù)學(xué)基礎(chǔ)210計(jì)算復(fù)雜性理論23分治策略411NP完全性理論24動(dòng)態(tài)規(guī)劃412Cook定理15回溯與分支估界413NP完全性證明56貪心法414NP完全理論應(yīng)用27概率算法315NP完全理論的拓廣28算法分析技術(shù)616小結(jié)1第四頁(yè)，共三十七頁(yè)，2022年，8月28日5教材與參考書1.AlgorithmDesign,JonKleinberg,EvaTardos,Addison-Wesley,清華大學(xué)出版社影印版，2006.2.IntroductiontoAlgorithms（SecondEdtion）,ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,TheMITPress2001.高教出版社影印版，2002.3.

計(jì)算機(jī)和難解性:NP完全性理論導(dǎo)引,M.R.

加里,D.S.

約翰遜,張立昂等譯，科學(xué)出版社,1987.*4.

計(jì)算復(fù)雜性導(dǎo)論，堵丁柱，葛可一，王潔，高教出版社2002.*5.LimitstoParallelComputation:P-CompletenessTheory,RaymondGreenlaw,H.JamesHoover,WalterL.Ruzzo,OxfordUniversityPress,1995.第五頁(yè)，共三十七頁(yè)，2022年，8月28日學(xué)習(xí)安排成績(jī)?cè)u(píng)定：小論文：結(jié)合研究工作，50%期末筆試：50%

第六頁(yè)，共三十七頁(yè)，2022年，8月28日7引言:理論上的可計(jì)算與現(xiàn)實(shí)上的可計(jì)算

算法研究的重要性理論上的可計(jì)算

——可計(jì)算性理論現(xiàn)實(shí)上的可計(jì)算

——計(jì)算復(fù)雜性理論

第七頁(yè)，共三十七頁(yè)，2022年，8月28日8投資問題問題：

m元錢，投資給n個(gè)項(xiàng)目，效益函數(shù)fi(x)，表示第i個(gè)項(xiàng)目投入x元錢的效益，i=1,2,…,n.如何分配每個(gè)項(xiàng)目的錢數(shù)使得總效益最大？采用什么算法？效率怎樣？令xi是第i個(gè)項(xiàng)目的錢數(shù)第八頁(yè)，共三十七頁(yè)，2022年，8月28日9蠻力算法的代價(jià)Stirling公式：非負(fù)整數(shù)解<x1,x2,…,xn>的個(gè)數(shù)估計(jì)：蠻力算法——窮舉法代價(jià)太大能否利用解之間的依賴關(guān)系找到更好的算法？結(jié)論：需要算法設(shè)計(jì)技術(shù)第九頁(yè)，共三十七頁(yè)，2022年，8月28日10

T(n)=2T(n1)+1，T(1)=1，ABC思考：是否存在更好的解法？Reve難題：Hanoi塔變種，柱數(shù)增加，允許盤子相等.

其他變種：奇偶盤號(hào)分別放置解得T(n)=2n

1

1秒移1個(gè)，64個(gè)盤子要多少時(shí)間？（5000億年）Hanoi塔問題第十頁(yè)，共三十七頁(yè)，2022年，8月28日11其他問題搜索問題

輸入：排好序的數(shù)組L，x

輸出：x是否在L中？如果在輸出它的下標(biāo)排序問題輸入：n個(gè)數(shù)輸出：按遞增順序排好的n個(gè)數(shù)選擇問題輸入：n個(gè)數(shù)的集合S，正整數(shù)k（1kn)

輸出：S中第k小的數(shù)需要：現(xiàn)有的算法中哪個(gè)算法最好？是否存在更有效的算法？第十一頁(yè)，共三十七頁(yè)，2022年，8月28日12Algorithm+DataStructure=Programming好的算法提高求解問題的效率節(jié)省存儲(chǔ)空間需要解決的問題問題尋找求解算法算法設(shè)計(jì)技術(shù)算法算法的評(píng)價(jià)算法分析技術(shù)算法類問題復(fù)雜度的評(píng)價(jià)問題復(fù)雜性分析問題類能夠求解的邊界計(jì)算復(fù)雜性理論

第十二頁(yè)，共三十七頁(yè)，2022年，8月28日13算法研究的重要性算法設(shè)計(jì)與分析技術(shù)在計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域有著重要的應(yīng)用背景算法設(shè)計(jì)分析與計(jì)算復(fù)雜性理論的研究是計(jì)算機(jī)科學(xué)技術(shù)的核心研究領(lǐng)域1966-2005期間，Turing獎(jiǎng)獲獎(jiǎng)50人，其中10人以算法設(shè)計(jì)，7人以計(jì)算理論、自動(dòng)機(jī)和復(fù)雜性研究領(lǐng)域的杰出貢獻(xiàn)獲獎(jiǎng)計(jì)算復(fù)雜性理論的核心課題“P=NP?”是本世紀(jì)7個(gè)最重要的數(shù)學(xué)問題之一通過算法設(shè)計(jì)與分析課程的訓(xùn)練對(duì)提高學(xué)生的素質(zhì)和分析問題解決問題的能力有著重要的作用第十三頁(yè)，共三十七頁(yè)，2022年，8月28日14理論上的可計(jì)算：可計(jì)算性理論研究目標(biāo)確定什么問題是可計(jì)算的，即存在求解算法合理的計(jì)算模型已有的：遞歸函數(shù)、Turing機(jī)、演算、Post系統(tǒng)等條件：計(jì)算一個(gè)函數(shù)只要有限條指令每條指令可以由模型中的有限個(gè)計(jì)算步驟完成指令執(zhí)行的過程是確定的核心論題：Church-Turing論題如果一個(gè)函數(shù)在某個(gè)合理的計(jì)算模型上可計(jì)算，那么它在Turing機(jī)上也是可計(jì)算的可計(jì)算性是不依賴于計(jì)算模型的客觀性質(zhì)第十四頁(yè)，共三十七頁(yè)，2022年，8月28日15算法至少具有指數(shù)時(shí)間：理論上可計(jì)算——難解的多項(xiàng)式時(shí)間的算法：現(xiàn)實(shí)上可計(jì)算——多項(xiàng)式時(shí)間可解的對(duì)數(shù)多項(xiàng)式時(shí)間的算法：高度并行可解的理論上可計(jì)算

理論上不可計(jì)算現(xiàn)實(shí)可計(jì)算高度并行可計(jì)算理論上與現(xiàn)實(shí)上的可計(jì)算性第十五頁(yè)，共三十七頁(yè)，2022年，8月28日16計(jì)算復(fù)雜性理論內(nèi)容算法復(fù)雜度——算法所使用的時(shí)間、空間的估計(jì)問題復(fù)雜度——估計(jì)問題的難度術(shù)語(yǔ)和概念問題算法算法的時(shí)間復(fù)雜度函數(shù)的階多項(xiàng)式時(shí)間的算法與指數(shù)時(shí)間的算法問題的復(fù)雜度分析第十六頁(yè)，共三十七頁(yè)，2022年，8月28日17例1

貨郎擔(dān)問題問題：有窮個(gè)城市的集合C={c1,c2,…,cm},

正整數(shù)d(ci,cj)=d(cj,ci),1

i<j

m.

解：使得k1,k2,…,km是1,2…,m的置換且滿足

問題問題：需要回答的一般性提問，通常含有若干參數(shù)問題描述所包含的內(nèi)容：對(duì)問題參數(shù)的一般性描述，解滿足的條件問題的實(shí)例：對(duì)問題的參數(shù)的一組賦值

第十七頁(yè)，共三十七頁(yè)，2022年，8月28日1853c1c4c3c210969實(shí)例C={c1,c2,c3,c4},d(c1,c2)=10,d(c1,c3)=5,d(c1,c4)=9d(c2,c3)=6,d(c2,c4)=9,d(c3,c4)=3第十八頁(yè)，共三十七頁(yè)，2022年，8月28日19算法非形式定義有限條指令的集合指令集確定了解決某個(gè)問題的運(yùn)算或操作的序列輸入個(gè)數(shù)大于等于0

輸出個(gè)數(shù)大于0形式定義對(duì)所有的有效輸入停機(jī)的Turing機(jī)算法A解問題P

把問題P的任何實(shí)例作為算法A的輸入，A能夠在有限步停機(jī)，并輸出該實(shí)例的正確的解第十九頁(yè)，共三十七頁(yè)，2022年，8月28日20算法的描述：偽碼保持程序的主要結(jié)構(gòu)類C,Pascal賦值語(yǔ)句：分支語(yǔ)句：if…then…[else…]循環(huán)語(yǔ)句：while,for，repeat..until轉(zhuǎn)向語(yǔ)句：goto調(diào)用注釋：//…允許使用自然語(yǔ)言常忽略數(shù)據(jù)結(jié)構(gòu)、模塊、異常處理等細(xì)節(jié)常忽略變量說明第二十頁(yè)，共三十七頁(yè)，2022年，8月28日21偽碼的例子：插入排序算法INSERTION-SORT(A)1.forj

2tolength[A]2.dokeyA[j]//將A[j]插入排好序的序列A[1..j–1]3.ij–14. whilei>0andA[i]>key5.doA[i+1]A[i]6.ii–17.A[i+1]key

第二十一頁(yè)，共三十七頁(yè)，2022年，8月28日22算法的時(shí)間復(fù)雜度最壞情況下的時(shí)間復(fù)雜度

算法求解輸入規(guī)模為n的實(shí)例所需要的最長(zhǎng)時(shí)間W(n)平均情況下的時(shí)間復(fù)雜度算法求解輸入規(guī)模為n的實(shí)例所需要的平均時(shí)間A(n)復(fù)雜度表示針對(duì)問題選擇基本運(yùn)算將基本運(yùn)算次數(shù)表示為輸入規(guī)模的函數(shù)第二十二頁(yè)，共三十七頁(yè)，2022年，8月28日23實(shí)例搜索問題輸入：非降順序排列的數(shù)組L，元素?cái)?shù)為n；數(shù)x輸出：j.若x在L中，j是x首次出現(xiàn)的序標(biāo)；否則j

＝0算法順序搜索假設(shè)

x在L中的概率為p

x在L中不同位置是等概分布的，則第二十三頁(yè)，共三十七頁(yè)，2022年，8月28日24函數(shù)漸近的界設(shè)f和g是定義域?yàn)樽匀粩?shù)集N上的函數(shù)

(1)f(n)=O(g(n))

若存在正數(shù)c和n0使得對(duì)一切nn0有0f(n)cg(n)(2)f(n)=(g(n))

若存在正數(shù)c和n0使得對(duì)一切nn0有0cg(n)f(n)(3)f(n)=o(g(n))

對(duì)所有正數(shù)c<1存在n0使得對(duì)一切nn0有0f(n)<cg(n)(4)f(n)=(g(n)).

對(duì)所有正數(shù)c<1存在n0使得對(duì)一切nn0有0cg(n)<f(n)(5)f(n)=(g(n))f(n)=O(g(n))且f(n)=(g(n))(6)O(1)表示常數(shù)函數(shù)第二十四頁(yè)，共三十七頁(yè)，2022年，8月28日25函數(shù)漸近的界的基本性質(zhì)定理1.1

設(shè)f和g是定義域?yàn)樽匀粩?shù)集N上的函數(shù).(1)如果存在，并且等于某個(gè)常數(shù)c>0，那么

f(n)=(g(n)).(2)如果，那么

f(n)=o(g(n)).(3)如果,那么

f(n)=(g(n)).第二十五頁(yè)，共三十七頁(yè)，2022年，8月28日證明(只證明第一種情況)(1)根據(jù)極限定義，對(duì)于給定的正數(shù)=c/2,存在某個(gè)n0，只要nn0，就有對(duì)所有的nn0，f(n)2cg(n).從而推出f(n)=O(g(n))

對(duì)所有的nn0，f(n)(c/2)g(n)，從而推出f(n)=(g(n)),于是

f(n)=(g(n))第二十六頁(yè)，共三十七頁(yè)，2022年，8月28日27定理1.2設(shè)f,g,h是定義域?yàn)樽匀粩?shù)集合的函數(shù)，

(1)如果f=O(g)且g=O(h)，那么f=O(h).(2)如果f=(g)且g=(h)，那么f=(h).

(3)如果f=(g)和g=(h)，那么f=(h).定理1.3假設(shè)f和g是定義域?yàn)樽匀粩?shù)集合的函數(shù)，若對(duì)某個(gè)其它的函數(shù)h,我們有f=O(h)和g=O(h)，那么f+g=O(h).推論假設(shè)f和g是定義域?yàn)樽匀粩?shù)集合的函數(shù)，且滿足g=O(f)，那么f+g=(f).函數(shù)漸近的界的基本性質(zhì)第二十七頁(yè)，共三十七頁(yè)，2022年，8月28日28基本函數(shù)類階的高低

至少指數(shù)級(jí)：2n,3n,n!,…

多項(xiàng)式級(jí)：n,n2,nlogn,n1/2,…

對(duì)數(shù)多項(xiàng)式級(jí)：logn,log2n,…

第二十八頁(yè)，共三十七頁(yè)，2022年，8月28日例題29例1

設(shè)，證明f(n)=

Θ(n2).根據(jù)定理1.1有f(n)=

Θ(n2).

第二十九頁(yè)，共三十七頁(yè)，2022年，8月28日30例題例2

PrimalityTest(n)（素?cái)?shù)檢測(cè)）輸入：n,n為大于2的奇整數(shù)輸出：true或者false1．s

2．forj2tos3．ifj整除n

4．thenreturnfalse5．returntrue假設(shè)計(jì)算可以在O(1)時(shí)間完成，可以寫O(),不能寫()，因?yàn)樗璧臏y(cè)試次數(shù)小于等于之第三十頁(yè)，共三十七頁(yè)，2022年，8月28日多項(xiàng)式時(shí)間的算法31多項(xiàng)式時(shí)間的算法

時(shí)間復(fù)雜度函數(shù)為O(p(n))的算法，其中p(n)是n的多項(xiàng)式不是多項(xiàng)式時(shí)間的算法

不存在多項(xiàng)式p(n)使得該算法的時(shí)間復(fù)雜度為O(p(n))包含指數(shù)時(shí)間甚至更高階的算法第三十一頁(yè)，共三十七頁(yè)，2022年，8月28日多項(xiàng)式函數(shù)與指數(shù)函數(shù)時(shí)間復(fù)雜度函數(shù)問題規(guī)模102030405060n10－52*10－53*10－54*10－55*10－56*10－5n210－44*10－49*10－416*10－425*10－436*10－4n310－38*10－3