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

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

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

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

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

definiteness

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

finiteness

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

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

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

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

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

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

將時間復(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ù)量.令N:問題的規(guī)模I:輸入數(shù)據(jù)A:算法本身則算法的復(fù)雜性C=F(N,I,A)設(shè)一臺抽象計算機提供的元運算有k種,分別記作O1,…,Ok

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

t2,…,tk

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

T=T(N,I)=

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

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

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

==平均情況:Tavg(N)==例題1-1其中DN:規(guī)模為N的所有合法輸入的集合

I*:DN中達到Tmax(N)的一個輸入

:DN中達到Tmin(N)的一個輸入

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

已知不重復(fù)且從小到大排列的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,設(shè)元運算執(zhí)行時間為賦值: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è)計與分析

算法1-2:二分查找(假定c是A的最后一元)例題1-1分析:問題規(guī)模為m,元運算執(zhí)行時間設(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è)計與分析>

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

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

1).漸進性態(tài)設(shè)T(n)為算法A的時間復(fù)雜性函數(shù),則它是n的單增函數(shù),如果存在一個函數(shù)使得當n,有

(T(n)-)/T(n)0稱是T(n)當n

時的漸進性態(tài)或漸進復(fù)雜性.在數(shù)學(xué)上,T(n)與有相同的最高階項.可取為略去T(n)的低階項后剩余的主項.當n充分大時我們用代替T(n)作為算法復(fù)雜性的度量,從而簡化分析.

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

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

算法概述>算法的復(fù)雜性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使得當N

N0時,有f(N)cg(N)

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

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

,也稱f(N)

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

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

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

算法概述>算法的復(fù)雜性例如估計如下二重循環(huán)算法在最壞情況下時間復(fù)雜性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)共需

16算法設(shè)計與分析>

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

表示法(算法運行時間的下限）

f(N)=(g(N)

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

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

)稱函數(shù)f(N)與g(N)同階.算法的漸進復(fù)雜性的階對于算法的效率有著決定性的意義:多項式階算法(有效算法):時間復(fù)雜性與規(guī)模N的冪同階.指數(shù)階算法:時間復(fù)雜性與規(guī)模N的一個指數(shù)函數(shù)同階.最優(yōu)算法:時間復(fù)雜性達到其下界的算法.如果正常數(shù)c和自然數(shù)N0使得當N

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

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

算法概述>算法的復(fù)雜性圖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)劣.18算法設(shè)計與分析>

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

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

1).賦值,比較,算術(shù)運算,邏輯運算,讀寫單個變量(常量)只需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)用,可建立關(guān)于T(n)的遞歸方程,求解該方程得到T(n).例題1-1算法設(shè)計與分析

算法1-2:二分查找(假定c是A的最后一元)例題1-1分析:問題規(guī)模為m,元運算執(zhí)行時間設(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è)計與分析已知不重復(fù)且從小到大排列的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; 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在最壞情況下的時間復(fù)雜性,則T(m)滿足如下遞歸方程:2

m=013m=1

11+T(m/2)m>1T(m)=解得:T(m)=11·logm+13=

(logm)算法1-3:二分查找遞歸算法算法設(shè)計與分析

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

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

>

算法概述

>算法的復(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,當n充分大時有

af(n/b)

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

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

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

算法設(shè)計與分析

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

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

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

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

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

2).確定性

definiteness

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

finiteness

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

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

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

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

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

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

將時間復(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ù)量.令N:問題的規(guī)模I:輸入數(shù)據(jù)A:算法本身則算法的復(fù)雜性C=F(N,I,A)設(shè)一臺抽象計算機提供的元運算有k種,分別記作O1,…,Ok

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

t2,…,tk

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

T=T(N,I)=

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

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

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

==平均情況:Tavg(N)==例題1-1其中DN:規(guī)模為N的所有合法輸入的集合

I*:DN中達到Tmax(N)的一個輸入

:DN中達到Tmin(N)的一個輸入

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

已知不重復(fù)且從小到大排列的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,設(shè)元運算執(zhí)行時間為賦值: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è)計與分析

算法1-2:二分查找(假定c是A的最后一元)例題1-1分析:問題規(guī)模為m,元運算執(zhí)行時間設(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è)計與分析>

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

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

1).漸進性態(tài)設(shè)T(n)為算法A的時間復(fù)雜性函數(shù),則它是n的單增函數(shù),如果存在一個函數(shù)使得當n,有

(T(n)-)/T(n)0稱是T(n)當n

時的漸進性態(tài)或漸進復(fù)雜性.在數(shù)學(xué)上,T(n)與有相同的最高階項.可取為略去T(n)的低階項后剩余的主項.當n充分大時我們用代替T(n)作為算法復(fù)雜性的度量,從而簡化分析.

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

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

算法概述>算法的復(fù)雜性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使得當N

N0時,有f(N)cg(N)

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

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

,也稱f(N)

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

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

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

算法概述>算法的復(fù)雜性例如估計如下二重循環(huán)算法在最壞情況下時間復(fù)雜性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)共需

36算法設(shè)計與分析>

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

表示法(算法運行時間的下限）

f(N)=(g(N)

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

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

)稱函數(shù)f(N)與g(N)同階.算法的漸進復(fù)雜性的階對于算法的效率有著決定性的意義:多項式階算法(有效算法):時間復(fù)雜性與規(guī)模N的冪同階.指數(shù)階算法:時間復(fù)雜性與規(guī)模N的一個指數(shù)函數(shù)同階.最優(yōu)算法:時間復(fù)雜性達到其下界的算法.如果正常數(shù)c和自然數(shù)N0使得當N

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

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

算法概述>算法的復(fù)雜性圖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)劣.38算法設(shè)計與分析>

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

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

1).賦值,比較,算術(shù)運算,邏輯運算,讀寫單個變量(常量)只需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)用,可建立關(guān)于T(n)的遞歸方程,求解該方程得到T(n).例題1-1算法設(shè)計與分析

算法1-2:二分查找(假定c是A的最后一元)例題1-1分析:問題規(guī)模為m,元運算執(zhí)行時間設(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è)計與分析已知不重復(fù)且從小到大排列的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; 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在最壞情況下的時間復(fù)雜性,則T(m)滿足如下遞歸方程:2

m=013m=1

11+T(m/2)m>1T(m)=解得:T(m)=11·logm+13=

(logm)算法1-3:二分查找遞歸算法算法設(shè)計與分析

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

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

>

算法概述

>算法的復(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,當n充分大時有

af(n/b)

cf(n),則T(n)=(f(n))設(shè)a0,a1,…an,..是任意數(shù)列,稱f(x)=a0+a1x+…+anxn+…為數(shù)列的母函數(shù)若取數(shù)列為算法的時間復(fù)雜性函數(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ù)和的漸進階.3).數(shù)學(xué)歸納法(代入法)

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

遞歸與分治第二章遞歸與分治(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è)計與分析>

遞歸與分治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;}遞歸程序的棧實現(xiàn)45算法設(shè)計與分析>

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

遞歸與分治遞歸代表一種計算規(guī)則,有時其計算出的實現(xiàn)過程很難人工模擬.用已知方法將上n-1盤,從a移到ccab將n盤子從a移到b:1.每次只移一個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è)對于任意n,方法已知(實際未知)將第n盤,從a移到b用已知方法將上n-1盤,從c移到b47算法設(shè)計與分析>

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

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

T(n)=算法的時間復(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)解得:適用問題大數(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,當h=log2n,即2h=n時,=nT(1)+2nlog2n=n+2nlog2n=O(nlog2n)當k=m=2,f(n)=2n時,驗證此公式:算法設(shè)計與分析

已知不重復(fù)且從小到大排列的m個整數(shù)的數(shù)組A[1...m],m=2K,K為正整數(shù).對于給定的整數(shù)c,要求找到一個下標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,細化分枝為1,所以k=1.f(n)=7Log21=0T(n)=n0+7log2n=1+7log2n=O(log2n)算法設(shè)計與分析

算法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è)計與分析>

遞歸與分治問題:

設(shè)X,Y是兩個n位二進制數(shù),求XY.分治算法思路:若兩個1位數(shù)相乘或相加看作1步運算,按傳統(tǒng)乘法需O(n2)次運算.將每個n(n=2K)位的二進制整數(shù)分為2段,每段的長為n/2位計算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)計算XY須4次n/2位整數(shù)的乘法,3次不超過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ù)的乘法沒有改善改進:XY＝AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD算法算法設(shè)計與分析>

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

n,B=(bij)n

n,C=A

B=(cij)n

n計算C共需n

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

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

得:T(n)=O(n3)

T(n)=O(n3)改進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)

驗證: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è)計與分析>

遞歸與分治算法算法設(shè)計與分析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問題陳述:在一個2k

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

2k

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

遞歸與分治58分治算法:

當k>0時,將2k

2k棋盤分割為4個2k-1

2k-1子棋盤

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

2k殘缺棋盤的時間,

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

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

得:T(k)=

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

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

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