算法分析與設(shè)計(jì)(研究生)全冊(cè)配套課件

算法分析與設(shè)計(jì)(研究生)全冊(cè)配套課件

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

算法設(shè)計(jì)與分析>目錄第一章算法及計(jì)算幾何概述第三章凸殼及其算法第八章動(dòng)態(tài)規(guī)劃第九章貪心算法第十章回朔法第十一章分支限界法第七章遞歸與分治第六章NP完全性理論簡(jiǎn)介第二章多邊形與幾何體定位第四章Voronoi圖及其應(yīng)用第五章交與并4參考教材王曉東《算法設(shè)計(jì)與分析》，清華大學(xué)出版社，2003周培德《計(jì)算幾何－算法分析與設(shè)計(jì)》清華大學(xué)出版社，2000算法概述AlgorithmIntroduction第一章介紹算法設(shè)計(jì)的基本概念及算法分析的方法和準(zhǔn)則.算法設(shè)計(jì)與分析6一系列將問(wèn)題的輸入轉(zhuǎn)換為輸出的計(jì)算或操作步驟。

算法設(shè)計(jì)與分析>算法概述1.1算法Algorithm2).確定性

definiteness

算法的每個(gè)步驟必須有明確的意義,對(duì)每種可能的情況,算法都要給出確定的操作.1).有窮性

finiteness

算法必須在執(zhí)行有窮步后終止,且每一步均在有限時(shí)間內(nèi)完成3).能行性effectiveness

算法中的每個(gè)步驟是能夠?qū)崿F(xiàn)的,算法執(zhí)行結(jié)果要達(dá)到預(yù)期目的

3.計(jì)算機(jī)算法的一般特征4).有0個(gè)或多個(gè)輸入項(xiàng),至少有一個(gè)輸出項(xiàng).1問(wèn)題問(wèn)題是一組需要完成的任務(wù)，數(shù)學(xué)上可將問(wèn)題看作函數(shù)2算法7算法設(shè)計(jì)與分析>算法概述數(shù)值型算法:算法中的基本運(yùn)算為算術(shù)運(yùn)算.非數(shù)值型算法:算法中的基本運(yùn)算為邏輯運(yùn)算.串行算法:串行計(jì)算機(jī)上執(zhí)行的算法.并行算法:并行計(jì)算機(jī)上執(zhí)行的算法.從處理方式上6.算法分類從解法上5.算法描述語(yǔ)言

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

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

4.算法的三個(gè)要素自然語(yǔ)言,數(shù)學(xué)語(yǔ)言,流程圖,程序設(shè)計(jì)語(yǔ)言等等.8算法設(shè)計(jì)與分析>算法概述7.問(wèn)題的求解過(guò)程2)建立數(shù)學(xué)模型1)問(wèn)題的陳述3)算法設(shè)計(jì)4)算法的正確性證明5)算法的程序?qū)崿F(xiàn)6)算法分析用科學(xué)規(guī)范的語(yǔ)言,對(duì)所求解的問(wèn)題做準(zhǔn)確的描述.通過(guò)對(duì)問(wèn)題的分析,找出其中的所有操作對(duì)象及操作對(duì)象之間的關(guān)系并用數(shù)學(xué)語(yǔ)言加以描述.根據(jù)數(shù)學(xué)模型設(shè)計(jì)問(wèn)題的計(jì)算機(jī)求解算法.證明算法對(duì)一切合法輸入均能在有限次計(jì)算后產(chǎn)生正確輸出.對(duì)執(zhí)行該算法所消耗的計(jì)算機(jī)資源進(jìn)行估算.將算法正確地編寫成機(jī)器語(yǔ)言程序.9算法設(shè)計(jì)與分析>算法概述1.2算法復(fù)雜性分析1.復(fù)雜性的計(jì)量顯然,它與問(wèn)題的規(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)簡(jiǎn)化為T=T(N,I)

算法的復(fù)雜性:算法執(zhí)行所需的時(shí)間和空間的數(shù)量.令N:問(wèn)題的規(guī)模I:輸入數(shù)據(jù)A:算法本身則算法的復(fù)雜性C=F(N,I,A)設(shè)一臺(tái)抽象計(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)=

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

算法概述>算法的復(fù)雜性最好情況:Tmin(N)=T(N,I)=

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

==平均情況:Tavg(N)==例題1-1其中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ù).對(duì)于給定的整數(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分析:問(wèn)題的規(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分析:問(wèn)題規(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}13算法設(shè)計(jì)與分析>

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

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

1).漸進(jìn)性態(tài)設(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ù)雜性.在數(shù)學(xué)上,T(n)與有相同的最高階項(xiàng).可取為略去T(n)的低階項(xiàng)后剩余的主項(xiàng).當(dāng)n充分大時(shí)我們用代替T(n)作為算法復(fù)雜性的度量,從而簡(jiǎn)化分析.

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

若進(jìn)一步假定算法中所有不同元運(yùn)算的單位執(zhí)行時(shí)間相同,則可不考慮所包含的系數(shù)或常數(shù)因子。漸進(jìn)分析適用于n充分大的情況,當(dāng)問(wèn)題的規(guī)模很小時(shí),或比較的兩算法同階時(shí),則不能做這種簡(jiǎn)化.14算法設(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)N

N0時(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í)間的上限)15算法設(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為單一賦值語(yǔ)句外循環(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)共需

16算法設(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ù)雜性的階對(duì)于算法的效率有著決定性的意義:多項(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)N

N0時(shí),有f(N)cg(N)則稱函數(shù)f(N)在N充分大時(shí)有下限,且g(N)是它的一個(gè)下限,記為f(N)=(g(N))也稱f(N)的階不低于g(N)的階。(3)

表示法17算法設(shè)計(jì)與分析>

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

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

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

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

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

c

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

3).選擇語(yǔ)句case

A

of

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

am:sm

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

c

do

s

(repeat

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

算法1-2:二分查找(假定c是A的最后一元)例題1-1分析:問(wèn)題規(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; 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ù).對(duì)于給定的整數(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; elseifelement>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è)過(guò)程seg在最壞情況下的時(shí)間復(fù)雜性為T(n),則

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

>

算法概述

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

若遞歸方程形如: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+

),且

c<1,當(dāng)n充分大時(shí)有

af(n/b)

cf(n),則T(n)=(f(n))1).迭代法

將遞歸方程的的右端項(xiàng)通過(guò)迭代展開成級(jí)數(shù),然后估計(jì)級(jí)數(shù)和的漸進(jìn)階.2).數(shù)學(xué)歸納法(代入法)

先估計(jì)遞歸方程的顯式解,再用數(shù)學(xué)歸納法證明.

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

DesignandAnalysisofComputerAlgorithm第一章算法概述第二章遞歸與分治策略第三章動(dòng)態(tài)規(guī)劃第四章貪心算法第五章回朔法第六章分支限界法第七章概率算法第八章NP完全性理論簡(jiǎn)介算法設(shè)計(jì)與分析>目錄算法概述AlgorithmIntroduction第一章介紹算法設(shè)計(jì)的基本概念及算法分析的方法和準(zhǔn)則.算法設(shè)計(jì)與分析26一系列將問(wèn)題的輸入轉(zhuǎn)換為輸出的計(jì)算或操作步驟。

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

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

有些問(wèn)題沒(méi)有計(jì)算機(jī)算法.

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

2).確定性

definiteness

算法的每個(gè)步驟必須有明確的意義,對(duì)每種可能的情況,算法都要給出確定的操作.1).有窮性

finiteness

算法必須在執(zhí)行有窮步后終止,且每一步均在有限時(shí)間內(nèi)完成3).能行性effectiveness

算法中的每個(gè)步驟是能夠?qū)崿F(xiàn)的,算法執(zhí)行結(jié)果要達(dá)到預(yù)期目的

3.計(jì)算機(jī)算法的一般特征4).有0個(gè)或多個(gè)輸入項(xiàng),至少有一個(gè)輸出項(xiàng).27算法設(shè)計(jì)與分析>算法概述數(shù)值型算法:算法中的基本運(yùn)算為算術(shù)運(yùn)算.非數(shù)值型算法:算法中的基本運(yùn)算為邏輯運(yùn)算.串行算法:串行計(jì)算機(jī)上執(zhí)行的算法.并行算法:并行計(jì)算機(jī)上執(zhí)行的算法.從處理方式上6.算法分類從解法上5.算法描述語(yǔ)言

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

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

4.算法的三個(gè)要素自然語(yǔ)言,數(shù)學(xué)語(yǔ)言,流程圖,程序設(shè)計(jì)語(yǔ)言等等.28算法設(shè)計(jì)與分析>算法概述7.問(wèn)題的求解過(guò)程2)建立數(shù)學(xué)模型1)問(wèn)題的陳述3)算法設(shè)計(jì)4)算法的正確性證明5)算法的程序?qū)崿F(xiàn)6)算法分析用科學(xué)規(guī)范的語(yǔ)言,對(duì)所求解的問(wèn)題做準(zhǔn)確的描述.通過(guò)對(duì)問(wèn)題的分析,找出其中的所有操作對(duì)象及操作對(duì)象之間的關(guān)系并用數(shù)學(xué)語(yǔ)言加以描述.根據(jù)數(shù)學(xué)模型設(shè)計(jì)問(wèn)題的計(jì)算機(jī)求解算法.證明算法對(duì)一切合法輸入均能在有限次計(jì)算后產(chǎn)生正確輸出.對(duì)執(zhí)行該算法所消耗的計(jì)算機(jī)資源進(jìn)行估算.將算法正確地編寫成機(jī)器語(yǔ)言程序.29算法設(shè)計(jì)與分析>算法概述1.2算法復(fù)雜性分析1.復(fù)雜性的計(jì)量顯然,它與問(wèn)題的規(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)簡(jiǎn)化為T=T(N,I)

算法的復(fù)雜性:算法執(zhí)行所需的時(shí)間和空間的數(shù)量.令N:問(wèn)題的規(guī)模I:輸入數(shù)據(jù)A:算法本身則算法的復(fù)雜性C=F(N,I,A)設(shè)一臺(tái)抽象計(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)=

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

算法概述>算法的復(fù)雜性最好情況:Tmin(N)=T(N,I)=

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

==平均情況:Tavg(N)==例題1-1其中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ù).對(duì)于給定的整數(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分析:問(wèn)題的規(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分析:問(wèn)題規(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}33算法設(shè)計(jì)與分析>

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

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

1).漸進(jìn)性態(tài)設(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ù)雜性.在數(shù)學(xué)上,T(n)與有相同的最高階項(xiàng).可取為略去T(n)的低階項(xiàng)后剩余的主項(xiàng).當(dāng)n充分大時(shí)我們用代替T(n)作為算法復(fù)雜性的度量,從而簡(jiǎn)化分析.

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

若進(jìn)一步假定算法中所有不同元運(yùn)算的單位執(zhí)行時(shí)間相同,則可不考慮所包含的系數(shù)或常數(shù)因子。漸進(jìn)分析適用于n充分大的情況,當(dāng)問(wèn)題的規(guī)模很小時(shí),或比較的兩算法同階時(shí),則不能做這種簡(jiǎn)化.34算法設(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)N

N0時(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í)間的上限)35算法設(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為單一賦值語(yǔ)句外循環(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)共需

36算法設(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ù)雜性的階對(duì)于算法的效率有著決定性的意義:多項(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)N

N0時(shí),有f(N)cg(N)則稱函數(shù)f(N)在N充分大時(shí)有下限,且g(N)是它的一個(gè)下限,記為f(N)=(g(N))也稱f(N)的階不低于g(N)的階。(3)

表示法37算法設(shè)計(jì)與分析>

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

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

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

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

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

c

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

3).選擇語(yǔ)句case

A

of

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

am:sm

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

c

do

s

(repeat

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

算法1-2:二分查找(假定c是A的最后一元)例題1-1分析:問(wèn)題規(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; 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ù).對(duì)于給定的整數(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; elseifelement>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è)過(guò)程seg在最壞情況下的時(shí)間復(fù)雜性為T(n),則

T(n)=1+(1+F(i))2n=03n=18+F(n-1)+F(n-2)n>1F(n)=例題1-242算法設(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+

),且

c<1,當(dāng)n充分大時(shí)有

af(n/b)

cf(n),則T(n)=(f(n))設(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)通過(guò)迭代展開成級(jí)數(shù),然后估計(jì)級(jí)數(shù)和的漸進(jìn)階.3).數(shù)學(xué)歸納法(代入法)

先估計(jì)遞歸方程的顯式解,再用數(shù)學(xué)歸納法證明.43算法設(shè)計(jì)與分析>

遞歸與分治第二章遞歸與分治(DivideandConquer)2.1遞歸的概念例1.階乘函數(shù)f(n)=n!=n*(n-1)*(n-2)*…3*2*1 =n*[(n-1)!]=n*f(n-1)intfactorial(intn){ intf; if(n==0)f=1; elsef=n*factorial(n-1);//調(diào)用自身函數(shù)

returnf;}直接或間接地調(diào)用自身的算法稱為遞歸算法.44算法設(shè)計(jì)與分析>

遞歸與分治ClassFactorial{publicintn,f;Factorial(m){n=m;f=1;} };intfactorial(intn){Factorial*p;for(inti=n;i>0;i--){p=newFactorial(i);PushStack(p);}

Factorial*CurOb;Popup(&CurOb);while(Stackisnotempty){Popup(&p);p.f=p.n*CurOb.f;deleteCurOb;CurOb=p;}returnCurOb.f;}遞歸程序的棧實(shí)現(xiàn)45算法設(shè)計(jì)與分析>

遞歸與分治Fibonacci數(shù)列:F(n)=F(n-1)+F(n-2),F(0)=F(1)=1遞歸代表一種計(jì)算規(guī)則,有時(shí)有函數(shù)表示結(jié)果,有時(shí)沒(méi)有.整數(shù)劃分問(wèn)題n=n1+n2+…+nk,劃分?jǐn)?shù)p(n)計(jì)算的遞歸方法q(n,m)是所有劃分中最大加數(shù)不大于m的劃分?jǐn)?shù)有函數(shù)表示無(wú)函數(shù)表示m=n的劃分只有一個(gè)最大加數(shù)達(dá)是m的劃分個(gè)數(shù)等于將m從n中減去后n-m中最大加數(shù)是m的劃分個(gè)數(shù)46算法設(shè)計(jì)與分析>

遞歸與分治遞歸代表一種計(jì)算規(guī)則,有時(shí)其計(jì)算出的實(shí)現(xiàn)過(guò)程很難人工模擬.用已知方法將上n-1盤,從a移到ccab將n盤子從a移到b:1.每次只移一個(gè)2.大盤不能壓小盤3.架子c作為輔助架voidHanoi(intn,inta,intb,intc){if(n>0){Hanoi(n-1,a,c,b);move(a,b);Hanoi(n-1,c,b,a);}}設(shè)對(duì)于任意n,方法已知(實(shí)際未知)將第n盤,從a移到b用已知方法將上n-1盤,從c移到b47算法設(shè)計(jì)與分析>

遞歸與分治2.2分治(DivideandConquer)基本思想Divide-and-Conquer(P)if(|P|<=n0)Adhoc(P);直接求解問(wèn)題PdividePintosmallersubinstancesP1,P2,...,Pk;for(i=1;i<=k;i++)yi=Divide-and-Conquer(Pi);returnMerge(yl,...,yk);將p1,p2,…pk的解y1,y2,…yk合并成p的解問(wèn)題的規(guī)模閾值算法一般模式將規(guī)模為N的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題,使這些子問(wèn)題相互獨(dú)立可分別求解,再將k個(gè)子問(wèn)題的解合并成原問(wèn)題的解.如子問(wèn)題的規(guī)模仍很大,則反復(fù)分解直到問(wèn)題小到可直接求解為止.在分治法中,子問(wèn)題的解法通常與原問(wèn)題相同,自然導(dǎo)致遞歸過(guò)程.應(yīng)用當(dāng)中,通常將問(wèn)題分解為k個(gè)(k=2)大小相等的子問(wèn)題.例題1-148算法設(shè)計(jì)與分析>

遞歸與分治設(shè)問(wèn)題P(n)分解成k個(gè)規(guī)模為n/m的子問(wèn)題,閥值n0=1,求解P(1)的時(shí)間耗費(fèi)為O(1).將P(n)分解及合并成P(n)的解的時(shí)間為f(n),則分治法解規(guī)模為n的問(wèn)題的最壞時(shí)間復(fù)雜性函數(shù)T(n)滿足:

T(n)=算法的時(shí)間復(fù)雜性Divide-and-Conquer(P)if(|P|<=n0)Adhoc(P);dividePintosmallersubinstancesP1,P2,...,Pk;for(i=1;i<=k;i++)yi=Divide-and-Conquer(Pi);returnMerge(yl,...,yk);f(n)kT(n/m)T(1)=O(1)T(n)=kT(n/m)+f(n)解得:適用問(wèn)題大數(shù)相乘,矩陣乘法,快速富立葉變換,棋盤覆蓋,排序,選擇等.O(1)49T(1)=1T(n)=2T(n/2)+2nT(n)=2[2T(n/22)+2*n/2]+2n=22T(n/22)+2*2n=22[2T(n/23)+2n/22]+2*2n=23T(n/23)+3*2n=…=2hT(n/2h)+h*2n,當(dāng)h=log2n,即2h=n時(shí),=nT(1)+2nlog2n=n+2nlog2n=O(nlog2n)當(dāng)k=m=2,f(n)=2n時(shí),驗(yàn)證此公式:算法設(shè)計(jì)與分析

已知不重復(fù)且從小到大排列的m個(gè)整數(shù)的數(shù)組A[1...m],m=2K,K為正整數(shù).對(duì)于給定的整數(shù)c,要求找到一個(gè)下標(biāo)i,使得A[i]=c.找不到返回0.functionsearch(c) {i:=1; 1 whileA[i]<candi<mdo i:=i+1; (3+2)m ifA[i]=c thensearch:=i; elsesearch:=0; 1+1 }算法1-1:順序查找例題1-1最好情況Tmin(m)=4,最壞情況Tmax(m)=3+5m,Tmin(m)=O(1)Tmax(m)=O(m)//i:=1,A[1]<c,ifA[1]=c,search:=151intbinarySearch(inta[],intx,intleft,intright)//Arraya[]hasbeensorted{intmiddle;middle=(left+right)/2;//3if(x==a[middle])returnmiddle;//1if(x>a[middle])left=middle+1;//3elseright=middle-1;

returnbinarySearch(a,x,left,right); }二分搜索算法:規(guī)?？s小為1/2,所以m=2,細(xì)化分枝為1,所以k=1.f(n)=7Log21=0T(n)=n0+7log2n=1+7log2n=O(log2n)算法設(shè)計(jì)與分析

算法1-2:二分查找例題1-1最壞情況Tmax(n)=O(logn)functionb-search(c){L:=1;U:=n; found:=false; whilenotfoundandU>=Ldo 3(logn+1){i:=(L+U)div2; 3(logn+1) ifc=A[i] logn+1 thenfound:=true elseifc>A[i] logn+1 thenL:=i+1 elseU:=i-1 2(logn+1)}iffoundthenb-search:=1 elseb-search:=0 }n=2hh=logn53算法設(shè)計(jì)與分析>

遞歸與分治問(wèn)題:

設(shè)X,Y是兩個(gè)n位二進(jìn)制數(shù),求XY.分治算法思路:若兩個(gè)1位數(shù)相乘或相加看作1步運(yùn)算,按傳統(tǒng)乘法需O(n2)次運(yùn)算.將每個(gè)n(n=2K)位的二進(jìn)制整數(shù)分為2段,每段的長(zhǎng)為n/2位計(jì)算XY須3次n/2位整數(shù)的乘法,6次加.減和2次移位X=A2n/2+By=C2n/2+D。XY＝(A2n/2+B)(C2n/2+D)＝AC2n+(AD+CB)2n/2+BD

T(n)=T(1)=O(1)T(n)=4T(n/2)+O(n)計(jì)算XY須4次n/2位整數(shù)的乘法,3次不超過(guò)2n位的整數(shù)加法,2次移位(乘2n

和乘2n/2).XY的T(n)滿足解得T(n)=O(n2)

T(n)=T(1)=O(1)T(n)=3T(n/2)+O(n)解得T(n)=O(nlog3)2.4大整數(shù)的乘法沒(méi)有改善改進(jìn):XY＝AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD算法算法設(shè)計(jì)與分析>

遞歸與分治{S=SIGN(X)*SIGN(Y)；

X:=ABS(X)；Y:=ABS(Y)；

ifn=lthenif(X=1)and(Y=1)thenreturn(S)elsereturn(0)else{A:=X的左邊n/2位；

B:=X的右邊n/2位；

C:=Y的左邊n/2位；

D:=Y的右邊n/2位；

m1:=MULT(A，C，n/2)；

m2:=MULT(A-B,D-C，n/2)；

m3:=MULT(B，D，n/2)；

S:=S*(m1*2n+(m1+m2+m3)*2n/2+m3)；

return(S)}}{X,Y為2個(gè)小于2n的二進(jìn)制整數(shù)，返回結(jié)果為X和Y的乘積XY}functionMULT(X,Y,n)大數(shù)相乘的分治遞歸算法二進(jìn)制大整數(shù)乘法同樣可應(yīng)用于十進(jìn)制大整數(shù)的乘法存放XY的符號(hào)存放三個(gè)乘積算法552.5矩陣相乘的Strassen法常規(guī)算法:設(shè)矩陣A=(aij)n

n,B=(bij)n

n,C=A

B=(cij)n

n計(jì)算C共需n

n2個(gè)乘法,n2(n-1)個(gè)加法.分治算法:劃分A,B為四個(gè)n/2(n=2K)階方陣,則:C11=A11B11+A12B21C12=A11B11+A12B21C21=A11B11+A12B21C22=A11B11+A12B21若n=2,可直接計(jì)算C;若n>2,C需8個(gè)n/2階方陣的乘法和4個(gè)加法.

T(n)=T(2)=O(1)T(n)=8T(n/2)+O(n2)

得:T(n)=O(n3)

T(n)=O(n3)改進(jìn)C11=M5+M4-M2+M6C12=M1+M2C21=M3+M4C22=M5+M1-M3-M7M1=A11(B12-B21)M2=(A11+A12)

B22M3=(A21+A22)

B11M4=A22(B21-B11)M5=(A11+A22)(B11+B22)M6=(A12+A22)(B21+B22)M7=(A11-A21)(B11+B12)

驗(yàn)證:C22=M5+M1-M3-M7=(A11+A22)(B11+B22)+A11(B12-B21)-(A21+A22)B11-

(A11-A21)(B11+B12)=A11B11+A11B22+A22B11+A22B22+A11B12

-A11B22-A21B11-A22B11-A11B11

-A11B12+A21B11+A21B12=A21B12+A22B22算法設(shè)計(jì)與分析>

遞歸與分治算法算法設(shè)計(jì)與分析procedureSTRASSEN(n,A,B,C)；

{ifn=2thenMATRIX_MULTIPLY(A,B,C)else{將矩陣A和B分塊；

STRASSEN(n/2，A11，B12-B22，M1)；

STRASSEN(n/2，A11+A12，B22，M2)；

STRASSEN(n/2，A21+A22，B11，M3)；

STRASSEN(n/2，A22，B21-B11，M4)；

STRASSEN(n/2，A11+A22，B11+B22，M5)STRASSEN(n/2，A12-A22，B21+B22，M6)；

STRASSEN(n/2，A11+A21，B11+B12，M7)C:=矩陣相乘Strassen算法

T(n)=T(2)=O(1)T(n)=7T(n/2)+18(n/2)2

得:T(n)=O(nlog7)=O(n2.81)分析:

算法//18次小矩陣相加57問(wèn)題陳述:在一個(gè)2k

2k個(gè)方格組成的棋盤中,恰有一方格殘缺殘缺方格的位置有22k種。故對(duì)任何k≥0,殘缺棋盤有22k種.要求用L型骨牌覆蓋殘缺棋盤上的所有方格且任何2個(gè)L型骨牌不得重疊覆蓋。2k

2k

的棋盤覆蓋中，用到的骨牌數(shù)為(4k-1)/32.6棋盤覆蓋算法設(shè)計(jì)與分析>

遞歸與分治58分治算法:

當(dāng)k>0時(shí),將2k

2k棋盤分割為4個(gè)2k-1

2k-1子棋盤

殘缺方格必位于4個(gè)子棋盤之一其余3個(gè)子棋盤中無(wú)殘缺方格為此將剩余3棋盤轉(zhuǎn)化為殘缺棋盤.用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤的結(jié)合處.這3個(gè)子棋盤上被L型骨牌覆蓋的方格就成為該棋盤上的殘缺方格,原問(wèn)題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤覆蓋問(wèn)題。遞歸地使用這種分割，直至棋盤簡(jiǎn)化為11棋盤.算法分析:設(shè)T(k)為覆蓋2k

2k殘缺棋盤的時(shí)間,

當(dāng)k=0時(shí)覆蓋它需要常數(shù)時(shí)間O(1)當(dāng)k>0時(shí),測(cè)試哪個(gè)子棋盤殘缺以及形成3個(gè)殘缺子棋盤需要O(1),覆蓋4個(gè)殘缺子棋盤需四次遞歸調(diào)用,共需時(shí)間4T(k-1),

T(k)=O(1)4T(k-1)+O(1)

得:T(k)=

(4k)與所需骨牌數(shù)同階算法設(shè)計(jì)與分析>

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

voidChessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return；//tr,tc:Cornerrow&columnno.