計算機算法設計與分析

算法設計與分析

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

電話：83590087Email：ypzhang@

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

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

2.計算機算法與人工算法

算法設計與分析>算法概述1.算法定義

有些問題沒有計算機算法.

有些問題計算機算法與人工算法不同.

(1)輸入：

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

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

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

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

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

3).控制和轉移:運算序列中的控制和轉移.

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

數(shù)據(jù)的邏輯結構

數(shù)據(jù)的存儲結構

線性結構

非線性結構

順序存儲

鏈式存儲線性表棧隊列樹形結構圖形結構數(shù)據(jù)結構的三個方面：

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

將時間復雜性和空間復雜性分別考慮,并用T和S表示.則

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

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

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

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

t2,…,tk

,設算法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算法設計與分析>

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

I*:DN中達到Tmax

(N)的一個輸入

:DN中達到Tmin

(N)的一個輸入

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

已知不重復且從小到大排列的m個整數(shù)的數(shù)組A[1...m],m=2K,K為正整數(shù).對于給定的整數(shù)c,要求找到一個下標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,設元運算執(zhí)行時間為賦值:a,判斷:t,加法:s,并設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算法設計與分析

算法1-2:二分查找(假定c是A的最后一元)例題1-1分析:問題規(guī)模為m,元運算執(zhí)行時間設為賦值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}若進一步假定算法中所有不同元運算的單位執(zhí)行時間相同,則可不考慮所包含的系數(shù)或常數(shù)因子。

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

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

(T(n)-)/T(n)0稱是T(n)當n時的漸進性態(tài)或漸進復雜性.18算法設計與分析>

算法概述>算法的復雜性2

復雜性的漸進性態(tài)

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

算法概述>算法的復雜性2).漸進性態(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使得當NN0時,有f(N)cg(N)

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

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

,也稱f(N)

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

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

(算法運行時間的上限)20算法設計與分析>

算法概述>算法的復雜性例如估計如下二重循環(huán)算法在最壞情況下時間復雜性T(n)的階.分析:內(nèi)循環(huán)體只需O(1)時間,故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))運算法則內(nèi)循環(huán)共需

21算法設計與分析>

算法概述>算法的復雜性(2)大表示法(算法運行時間的下限）

f(N)=(g(N)

)當且僅當f(N)=O(g(N)

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

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

算法概述>算法的復雜性圖1

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

算法概述>算法的復雜性3.漸進分析

時間復雜性漸進階分析的規(guī)則:(最壞情況)

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

c

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

3).選擇語句case

A

of

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

am:sm

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

c

do

s

(repeat

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

算法1-2:二分查找(假定c是A的最后一元)例題1-1分析:問題規(guī)模為m,元運算執(zhí)行時間設為賦值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算法設計與分析已知不重復且從小到大排列的m個整數(shù)的數(shù)組A[1...m],m=2K,K為正整數(shù).對于給定的整數(shù)c,要求找到一個下標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)};}設T(m)是b-search在最壞情況下的時間復雜性,則T(m)滿足如下遞歸方程:2

m=013m=1

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

求Fibonacci數(shù)列的前N項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))};設F(n)是函數(shù)A在最壞情況下的時間復雜性,則F(n)滿足如下遞歸方程:設過程seg在最壞情況下的時間復雜性為T(n),則

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

>

算法概述

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

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

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

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

>

算法概述

>算法的復雜性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+),且