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

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

DesignandAnalysisofComputerAlgorithm張永平y(tǒng)pzhang@公用：cumt_zyp@163.com密碼：7654321第一章算法概述第二章遞歸與分治策略第三章動(dòng)態(tài)規(guī)劃第四章貪心算法第五章回朔法第六章分支限界法*第七章概率算法算法設(shè)計(jì)與分析>目錄參考書計(jì)算機(jī)算法設(shè)計(jì)與分析（第4版），王曉東著，電子工業(yè)出版社，2012年計(jì)算機(jī)算法基礎(chǔ)（第二版），余祥宣等著，華中理工大學(xué)出版社，2000年計(jì)算機(jī)算法導(dǎo)引——設(shè)計(jì)與分析，盧開澄著，清華大學(xué)出版社，1996年計(jì)算機(jī)算法設(shè)計(jì)與分析，盧開澄，中國鐵道出版社，1998年IntroductiontoAlgorithms（第二版影印版），ThomasH.Cormen著，高等教育出版社算法設(shè)計(jì)與分析課程考核安排實(shí)驗(yàn)、作業(yè)論文考勤、課堂考試（30%）閉卷考試（70%）附加題包含兩個(gè)算法的動(dòng)畫（+）至多3個(gè)人一個(gè)小組，算法盡量不要相同題目可以為實(shí)現(xiàn)書中的程序答疑時(shí)間：周四下午七八節(jié)（12周-20周）地點(diǎn)：計(jì)A324-2或計(jì)A315-1

電話：83590087Email：ypzhang@

cumt_zyp@163.com密碼：7654321（公用）算法設(shè)計(jì)與分析算法概述AlgorithmIntroduction第1章介紹算法設(shè)計(jì)的基本概念及算法分析的方法和準(zhǔn)則.算法設(shè)計(jì)與分析學(xué)習(xí)要點(diǎn):算法設(shè)計(jì)與分析理解算法的概念。理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系。掌握算法的計(jì)算復(fù)雜性概念。掌握算法漸近復(fù)雜性的數(shù)學(xué)表述。掌握用C++語言描述算法的方法。算法是什么？算法設(shè)計(jì)與分析>算法概述1.1算法Algorithm算法，一個(gè)既陌生又熟悉的名詞。從小學(xué)就開始接觸算法。例如，做四則運(yùn)算要先乘除后加減，從里往外脫括弧等等都是算法，只要按照一定的程序一步一步做，一定不會(huì)錯(cuò)。因此，算法其實(shí)是耳熟能詳?shù)臄?shù)學(xué)對象。一般地，算法是指在解決問題時(shí)按照某種機(jī)械程序步驟一定可以得到結(jié)果的處理過程。這種過程必須是確定的、有效的、有限的。7算法設(shè)計(jì)與分析>算法概述“如果你在森林里迷路了，保持冷靜，調(diào)動(dòng)常識，走一步看一步。”

——這里是建議而非算法。童子軍的條例：如果你在森林里迷路了，一直往下走，直到溪流旁，然后順流而下，最后你會(huì)到達(dá)一個(gè)城鎮(zhèn)?！@是一個(gè)算法。89一系列將問題的輸入轉(zhuǎn)換為輸出的計(jì)算或操作步驟。

2.計(jì)算機(jī)算法與人工算法

算法設(shè)計(jì)與分析>算法概述1.算法定義

有些問題沒有計(jì)算機(jī)算法.

有些問題計(jì)算機(jī)算法與人工算法不同.

(1)輸入：

有外部提供的量作為算法的輸入。(2)輸出：

算法產(chǎn)生至少一個(gè)量作為輸出。(3)確定性：definiteness

組成算法的每條指令是清晰，無歧義的。(4)有限性：finiteness

算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。3.計(jì)算機(jī)算法的一般特征10算法設(shè)計(jì)與分析>算法概述數(shù)值型算法:算法中的基本運(yùn)算為算術(shù)運(yùn)算.非數(shù)值型算法:算法中的基本運(yùn)算為邏輯運(yùn)算.串行算法:串行計(jì)算機(jī)上執(zhí)行的算法.并行算法:并行計(jì)算機(jī)上執(zhí)行的算法.從處理方式上6.算法分類從解法上5.算法描述語言

1).數(shù)據(jù):運(yùn)算序列中作為運(yùn)算對象和結(jié)果的數(shù)據(jù).2).運(yùn)算:運(yùn)算序列中的各種運(yùn)算:賦值,算術(shù)和邏輯運(yùn)算

3).控制和轉(zhuǎn)移:運(yùn)算序列中的控制和轉(zhuǎn)移.

4.算法的三個(gè)要素自然語言,數(shù)學(xué)語言,流程圖,程序設(shè)計(jì)語言等等.11算法設(shè)計(jì)與分析>算法概述理解問題算法分析設(shè)計(jì)程序證明正確性設(shè)計(jì)算法1)問題的陳述用科學(xué)規(guī)范的語言,對所求解的問題做準(zhǔn)確的描述.2)建立數(shù)學(xué)模型通過對問題的分析,找出其中的所有操作對象及操作對象之間的關(guān)系并用數(shù)學(xué)語言加以描述.3)設(shè)計(jì)算法4)算法的正確性證明5)算法的程序?qū)崿F(xiàn)6)算法分析根據(jù)數(shù)學(xué)模型設(shè)計(jì)問題的計(jì)算機(jī)求解算法.證明算法對一切合法輸入均能在有限次計(jì)算后產(chǎn)生正確輸出.對執(zhí)行該算法所消耗的計(jì)算機(jī)資源進(jìn)行估算.將算法正確地編寫成機(jī)器語言程序.7.問題的求解過程12算法設(shè)計(jì)與分析>算法概述8.算法與程序、數(shù)據(jù)結(jié)構(gòu)的關(guān)系過程：算法+數(shù)據(jù)結(jié)構(gòu)程序?qū)ο螅簩ο?消息程序側(cè)重點(diǎn)不同數(shù)據(jù)的結(jié)構(gòu)，直接影響算法的選擇和效率。算法——程序的靈魂13

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲結(jié)構(gòu)

線性結(jié)構(gòu)

非線性結(jié)構(gòu)

順序存儲

鏈?zhǔn)酱鎯€性表?xiàng)ｊ?duì)列樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：

散列存儲索引存儲串及數(shù)組數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等算法設(shè)計(jì)與分析>算法概述8.算法與程序、數(shù)據(jù)結(jié)構(gòu)的關(guān)系14算法設(shè)計(jì)與分析>算法概述1.2算法復(fù)雜性分析1.復(fù)雜性的計(jì)量顯然,它與問題的規(guī)模,算法的輸入數(shù)據(jù)及算法本身有關(guān).

將時(shí)間復(fù)雜性和空間復(fù)雜性分別考慮,并用T和S表示.則

T=T(N,I,A)S=S(N,I,A)

將A隱含在函數(shù)名中,則T=T(N,I,A)簡化為T=T(N,I)

算法的復(fù)雜性:算法執(zhí)行所需的時(shí)間和空間的數(shù)量.令N:問題的規(guī)模I:輸入數(shù)據(jù)A:算法本身則算法的復(fù)雜性C=F(N,I,A)設(shè)一臺抽象計(jì)算機(jī)提供的元運(yùn)算有k種,分別記作O1,…,Ok

設(shè)這些元運(yùn)算每執(zhí)行一次所需時(shí)間分別為t1,

t2,…,tk

,設(shè)算法A中用到Oi的次數(shù)為ei,i=1,…,k,則ei=ei(N,I)

T=T(N,I)=

最好情況:Tmin(N)=T(N,I)=

==最壞情況:Tmax(N)=T(N,I)=

==平均情況:Tavg(N)==15算法設(shè)計(jì)與分析>

算法概述>算法的復(fù)雜性其中DN:規(guī)模為N的所有合法輸入的集合

I*:DN中達(dá)到Tmax

(N)的一個(gè)輸入

:DN中達(dá)到Tmin

(N)的一個(gè)輸入

P(I):出現(xiàn)輸入為I的概率算法設(shè)計(jì)與分析

已知不重復(fù)且從小到大排列的m個(gè)整數(shù)的數(shù)組A[1...m],m=2K,K為正整數(shù).對于給定的整數(shù)c,要求找到一個(gè)下標(biāo)i,使得A[i]=c.找不到返回0.functionsearch(c) {i:=1; a whileA[i]<candi<mdo 2mt i:=i+1; (m-1)(s+a) ifA[i]=c t thensearch:=i; elsesearch:=0; a }算法1-1:順序查找例題1-1分析:問題的規(guī)模為m,設(shè)元運(yùn)算執(zhí)行時(shí)間為賦值:a,判斷:t,加法:s,并設(shè)c在A中.最好情況Tmin

(m)=2a+3t最壞情況Tmax(m)=(m+1)a+(2m+1)t+(m-1)s平均情況Tavg(m)=0.5(m+3)a+(m+2)t+0.5(m-1)s算法設(shè)計(jì)與分析

算法1-2:二分查找(假定c是A的最后一元)例題1-1分析:問題規(guī)模為m,元運(yùn)算執(zhí)行時(shí)間設(shè)為賦值a,判斷t,加法s,除法d,減法b.最壞情況Tmax(m)=6a+4t+2s+d+(2a+2s+3t+d)

logmfunctionb-search(c){L:=1;U:=m; 2afound:=false; awhilenotfoundandU>=Ldo t(logm+2){i:=(L+U)div2; (a+s+d)(logm+1) ifc=A[i] t(logm+1) thenfound:=true a elseifc>A[i] t(logm+1) thenL:=i+1 (s+a)(logm+1)elseU:=i-1 }iffoundthenb-search:=i elseb-search:=0 a}若進(jìn)一步假定算法中所有不同元運(yùn)算的單位執(zhí)行時(shí)間相同,則可不考慮所包含的系數(shù)或常數(shù)因子。

例如T(n)=3n2+4nlogn+7,則可以是3n2.

在數(shù)學(xué)上,T(n)與有相同的最高階項(xiàng).可取為略去T(n)的低階項(xiàng)后剩余的主項(xiàng).當(dāng)n充分大時(shí)我們用代替T(n)作為算法復(fù)雜性的度量,從而簡化分析.設(shè)T(n)為算法A的時(shí)間復(fù)雜性函數(shù),則它是n的單增函數(shù),如果存在一個(gè)函數(shù)使得當(dāng)n,有

(T(n)-)/T(n)0稱是T(n)當(dāng)n時(shí)的漸進(jìn)性態(tài)或漸進(jìn)復(fù)雜性.18算法設(shè)計(jì)與分析>

算法概述>算法的復(fù)雜性2

復(fù)雜性的漸進(jìn)性態(tài)

1).漸進(jìn)性態(tài)漸進(jìn)分析適用于n充分大的情況,當(dāng)問題的規(guī)模很小時(shí),或比較的兩算法同階時(shí),則不能做這種簡化.19算法設(shè)計(jì)與分析>

算法概述>算法的復(fù)雜性2).漸進(jìn)性態(tài)的階又如算法1-1中Tmin

(m)=2a+3t,Tmax(m)=(m+1)a+(2m+1)t+(m-1)s,Tmin(m)=O(1)Tmax(m)=O(m)例如3n=O(n),n+1024=O(n),n2=O(n3)?n3=O(n2)?2n2+11n-10=O(n2)

若存在正常數(shù)c和自然數(shù)N0使得當(dāng)NN0時(shí),有f(N)cg(N)

則稱函數(shù)f(N)在N充分大時(shí)有上界,且g(N)是它的一個(gè)上界,

記為f(N)=O(g(N))

,也稱f(N)

的階不高于g(N)的階.

設(shè)f(N)和g(N)是定義在正整數(shù)集上的正函數(shù),(1)大O表示法

(算法運(yùn)行時(shí)間的上限)20算法設(shè)計(jì)與分析>

算法概述>算法的復(fù)雜性例如估計(jì)如下二重循環(huán)算法在最壞情況下時(shí)間復(fù)雜性T(n)的階.分析:內(nèi)循環(huán)體只需O(1)時(shí)間,故fori:=1tondoforj:=1toido{s1,s2,s3,s4};//s1,s2,s3,s4為單一賦值語句外循環(huán)共需

1.O(f)+O(g)=O(max(f,g))2.O(f)+O(g)=O(f+g)3.O(f)·O(g)=O(f·g)4.如果g(n)=O(f(n)),則O(f)+O(g)=O(f)5.f=O(f)6.O(cf(n))=O(f(n))運(yùn)算法則內(nèi)循環(huán)共需

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

算法概述>算法的復(fù)雜性(2)大表示法(算法運(yùn)行時(shí)間的下限）

f(N)=(g(N)

)當(dāng)且僅當(dāng)f(N)=O(g(N)

)且f(N)=(g(N)

)稱函數(shù)f(N)與g(N)同階.算法的漸進(jìn)復(fù)雜性的階對于算法的效率有著決定性的意義:多項(xiàng)式階算法(有效算法):時(shí)間復(fù)雜性與規(guī)模N的冪同階.指數(shù)階算法:時(shí)間復(fù)雜性與規(guī)模N的一個(gè)指數(shù)函數(shù)同階.最優(yōu)算法:時(shí)間復(fù)雜性達(dá)到其下界的算法.如果正常數(shù)c和自然數(shù)N0使得當(dāng)NN0時(shí),有f(N)cg(N)則稱函數(shù)f(N)在N充分大時(shí)有下限,且g(N)是它的一個(gè)下限,記為f(N)=(g(N))也稱f(N)的階不低于g(N)的階。(3)表示法22算法設(shè)計(jì)與分析>

算法概述>算法的復(fù)雜性圖1

時(shí)間函數(shù)的增長率常見的多項(xiàng)式階有:O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)O(2n)<O(n!)<O(nn)常見的指數(shù)階有:對規(guī)模較小的問題,決定算法工作效率的可能是算法的簡單性而不是算法執(zhí)行的時(shí)間.當(dāng)比較兩個(gè)算法的效率時(shí),若兩個(gè)算法是同階的,必須進(jìn)一步考察階的常數(shù)因子才能辨別優(yōu)劣.23算法設(shè)計(jì)與分析>

算法概述>算法的復(fù)雜性3.漸進(jìn)分析

時(shí)間復(fù)雜性漸進(jìn)階分析的規(guī)則:(最壞情況)

1).賦值,比較,算術(shù)運(yùn)算,邏輯運(yùn)算,讀寫單個(gè)變量(常量)只需1單位時(shí)間2).執(zhí)行條件語句if

c

thenS1elseS2的時(shí)間為TC+max(TS1,TS2).

3).選擇語句case

A

of

a1:s1；a2:s2；...；

am:sm

需要的時(shí)間為max（TS1,TS2,...,TSm）.4).訪問數(shù)組的單個(gè)分量或紀(jì)錄的單個(gè)域需要一個(gè)單位時(shí)間.5).執(zhí)行for循環(huán)語句的時(shí)間=執(zhí)行循環(huán)體時(shí)間*循環(huán)次數(shù).6).while

c

do

s

(repeat

suntilc)語句時(shí)間=(Tc+Ts)*循環(huán)次數(shù).7).用goto從循環(huán)體內(nèi)跳到循環(huán)體末或循環(huán)后面的語句時(shí),不需額外時(shí)間8).過程或函數(shù)調(diào)用語句對非遞歸調(diào)用,根據(jù)調(diào)用層次由里向外用規(guī)則1-7進(jìn)行分析；對遞歸調(diào)用,可建立關(guān)于T(n)的遞歸方程,求解該方程得到T(n).例題1-1算法設(shè)計(jì)與分析

算法1-2:二分查找(假定c是A的最后一元)例題1-1分析:問題規(guī)模為m,元運(yùn)算執(zhí)行時(shí)間設(shè)為賦值a,判斷t,加法s,除法d,減法b.最壞情況Tmax(m)=6a+4t+2s+d+(2a+2s+3t+d)logm=13+8logmfunctionb-search(c){L:=1;U:=m; 2found:=false; 1whilenotfoundandU>=Ldo 3{i:=(L+U)div2; 3

ifc=A[i] 1 thenfound:=true 1 elseifc>A[i] 1 thenL:=i+1 1elseU:=i-1 }iffoundthenb-search:=i elseb-search:=0 1}Logm+1算法設(shè)計(jì)與分析已知不重復(fù)且從小到大排列的m個(gè)整數(shù)的數(shù)組A[1...m],m=2K,K為正整數(shù).對于給定的整數(shù)c,要求找到一個(gè)下標(biāo)i,使得A[i]=c.找不到返回0.例題1-1functionb-search(c,L,U){ifU<Lthen 1b-search:=0 1

else{index:=(L+U)div2; 3element:=A[index]; 2

ifelement=cthen 1

b-search:=index; 1elseifelement>cthen 1

b-search:=b-search(c,L,index-1);3+T(m/2)

elseb-search:=b-search(c,index+1,U);3+T(m/2)};}設(shè)T(m)是b-search在最壞情況下的時(shí)間復(fù)雜性,則T(m)滿足如下遞歸方程:2

m=013m=1

11+T(m/2)m>1T(m)=解得:T(m)=11·logm+13=(logm)算法1-3:二分查找遞歸算法算法設(shè)計(jì)與分析

求Fibonacci數(shù)列的前N項(xiàng)a0,a1,…aN

其中,a0=0,a1=1,ai=ai-1+ai-2算法1-4Procedureseq(n)functionA(n){ifn=0then 1

A:=01elseifn=1then 1A:=1 1

elseA:=A(n-1)+A(n-2) 6+F(n-1)+F(n-2)};{ifn<0then1errorelsefori:=0tondo

writeln(A(i)) (1+F(i))};設(shè)F(n)是函數(shù)A在最壞情況下的時(shí)間復(fù)雜性,則F(n)滿足如下遞歸方程:設(shè)過程seg在最壞情況下的時(shí)間復(fù)雜性為T(n),則

T(n)=1+(1+F(i))2n=03n=18+F(n-1)+F(n-2)n>1F(n)=例題1-227算法設(shè)計(jì)與分析

>

算法概述

>算法的復(fù)雜性設(shè)a0,a1,…an,..是任意數(shù)列,稱f(x)=a0+a1x+…+anxn+…為數(shù)列的母函數(shù)若取數(shù)列為算法的時(shí)間復(fù)雜性函數(shù){T(n)},則其母函數(shù)為:

f(x)=T(0)+T(1)x+…+

T(n)xn…若能由T(n)的遞歸方程求出T(n)的母函數(shù),其展開式第n項(xiàng)系數(shù)即為T(n).4遞歸方程解的漸進(jìn)階1)母函數(shù)法2)迭代法

將遞歸方程的的右端項(xiàng)通過迭代展開成級數(shù),然后估計(jì)級數(shù)和的漸進(jìn)階.28算法設(shè)計(jì)與分析

>

算法概述

>算法的復(fù)雜性4)套用公式法

若遞歸方程形如:T(n)=aT(n/b)+f(n),可根據(jù)f(n)的不同情況套用公式

1)若>0,使得f(n)=O(nlogba-),則T(n)=(n

logba)2)若f(n)=(nlogba),則T(n)=(nlogba·logn)3)若>0,使得f(n)=(nlogba+),且