算法設計與分析

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

電話：83590087Email：ypzhang@

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

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

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

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

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

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

(1)輸入：

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

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

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

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

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

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

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

數據的邏輯結構

數據的存儲結構

線性結構

非線性結構

順序存儲

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

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

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

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

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

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

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

t2,…,tk

,設算法A中用到Oi的次數為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:規模為N的所有合法輸入的集合

I*:DN中達到Tmax

(N)的一個輸入

:DN中達到Tmin

(N)的一個輸入

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

已知不重復且從小到大排列的m個整數的數組A[1...m],m=2K,K為正整數.對于給定的整數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分析:問題的規模為m,設元運算執行時間為賦值: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分析:問題規模為m,元運算執行時間設為賦值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}若進一步假定算法中所有不同元運算的單位執行時間相同,則可不考慮所包含的系數或常數因子。

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

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

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

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

復雜性的漸進性態

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

算法概述>算法的復雜性2).漸進性態的階又如算法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)

若存在正常數c和自然數N0使得當NN0時,有f(N)cg(N)

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

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

,也稱f(N)

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

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

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

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

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))運算法則內循環共需

21算法設計與分析>

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

f(N)=(g(N)

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

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

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

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

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

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

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

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

c

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

3).選擇語句case

A

of

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

am:sm

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

c

do

s

(repeat

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

算法1-2:二分查找(假定c是A的最后一元)例題1-1分析:問題規模為m,元運算執行時間設為賦值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個整數的數組A[1...m],m=2K,K為正整數.對于給定的整數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數列的前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)是函數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,..是任意數列,稱f(x)=a0+a1x+…+anxn+…為數列的母函數若取數列為算法的時間復雜性函數{T(n)},則其母函數為:

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

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

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

>

算法概述

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

若遞歸方程形如:T(n)=aT(n/b)+f(n),可根據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+),且