第一章

算法概述第二章 遞歸與分治策略第三章 動(dòng)態(tài)規(guī)劃1第四章 貪心算法第五章 回朔法第六章 分支限界法第七章 隨機(jī)化算法算法設(shè)計(jì)與分析>目錄1.1

算法與程序2算法復(fù)雜度分析NP完全性理論算法設(shè)計(jì)與分析>第一章目錄“算法是任何定義好的計(jì)算程式，它取某些值或值的集合作為輸入，并產(chǎn)生某些值或值的集合作為輸出。”1.1

算法與程序1

算法定義及其特性算法設(shè)計(jì)與分析>算法概述算法: 是將問(wèn)題的輸入轉(zhuǎn)化為輸出的一系列計(jì)算或操作步驟.3算法設(shè)計(jì)與分析>算法概述算法描述舉例例：求兩個(gè)不全為0的非負(fù)整數(shù)m,n的最大公約數(shù)gcd(m,n)的歐幾里德算法描述:如果n=0,返回m的值作為結(jié)果，過(guò)程結(jié)束；否則，進(jìn)入第二步；用n去除m，將余數(shù)賦給r;將n的值賦給m，將r的值賦給n,返回第一步。4計(jì)算機(jī)算法與人工算法例如 求定積分:

s=人工處理步驟為找出f(x)的源函數(shù)F(x)利用牛-萊公式:s=F(b)-F(a)算法設(shè)計(jì)與分析>算法概述計(jì)算機(jī)算法：計(jì)算定積分采用數(shù)值積分的方法,得到一個(gè)近似解.有些問(wèn)題沒(méi)有計(jì)算機(jī)算法.有些問(wèn)題計(jì)算機(jī)算法與人工算法不同.5算法設(shè)計(jì)與分析>算法概述算法的定義因看待的角度不同而不同6

哲學(xué)家：算法是解決一個(gè)問(wèn)題的抽象行為序列。

碼農(nóng)：算法是一個(gè)計(jì)算過(guò)程，它接受一些輸入，并產(chǎn)生某些輸出。

高大上：算法是解決一個(gè)精確定義的計(jì)算問(wèn)題的工具。核心：算法是解決問(wèn)題的辦法和法則，算法必須能夠讓人一步一步照著執(zhí)行。算法的特征算法設(shè)計(jì)與分析>算法概述1.有窮性一個(gè)算法須在執(zhí)行有限個(gè)運(yùn)算步后終止,每一步必須在有限時(shí)間內(nèi)完成.實(shí)際應(yīng)用中,算法的有窮性應(yīng)該包括執(zhí)行時(shí)間的合理性.程序是算法的程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn).可不滿足性質(zhì)1.一個(gè)算法面向一個(gè)問(wèn)題，而不是僅僅求解一個(gè)問(wèn)題的實(shí)例操作系統(tǒng)程序：是一個(gè)在無(wú)限循環(huán)中執(zhí)行的程序，而不是一個(gè)算法。7算法設(shè)計(jì)與分析>算法概述例如 計(jì)算分段函數(shù)

f(x)

=1

x>1000

x<108算法描述：輸入變量x,

若x大于100的數(shù)，輸出1;

若x小于10的數(shù)，輸出0.

輸入10<=x<=100,則算法在異常情況下,執(zhí)行結(jié)果是不確定的.2.確定性算法的每一步驟必須有確定的含義,對(duì)每一種可能出現(xiàn)的情況,算法都應(yīng)給出確定的操作,不能有多義性.3.能行性算法中的每個(gè)步驟是能實(shí)現(xiàn)的,

如

x/0; 負(fù)數(shù)開(kāi)方…算法的執(zhí)行結(jié)果達(dá)到預(yù)期目的,正確,有效.輸入有0個(gè)或多個(gè)輸入項(xiàng).輸出算法產(chǎn)生至少有一個(gè)輸出項(xiàng)算法設(shè)計(jì)與分析>算法概述9問(wèn)題的陳述理解問(wèn)題，并用科學(xué)規(guī)范的語(yǔ)言把所求解問(wèn)題進(jìn)行準(zhǔn)確的描述,包括所有已知條件和輸出要求.建立數(shù)學(xué)模型通過(guò)對(duì)問(wèn)題分析,找出其中所有操作對(duì)象以及對(duì)象之間的關(guān)系,并用數(shù)學(xué)語(yǔ)言加以描述. 對(duì)非數(shù)值型解法來(lái)說(shuō),數(shù)學(xué)模型通常是鏈表,樹(shù),圖,集合等數(shù)據(jù)結(jié)構(gòu).2.算法設(shè)計(jì)過(guò)程(程序設(shè)計(jì)過(guò)程)算法設(shè)計(jì)與分析>算法概述10算法設(shè)計(jì)根據(jù)數(shù)據(jù)模型, 給出求解問(wèn)題的一系列步驟,且這些步驟可通過(guò)計(jì)算機(jī)的各種操作來(lái)實(shí)現(xiàn).算法的正確性證明算法的正確性:對(duì)一切合法的輸入,算法均能在有限次的計(jì)算后產(chǎn)生正確的輸出.算法的程序?qū)崿F(xiàn)將一個(gè)算法描述正確地編寫成機(jī)器語(yǔ)言程序.算法設(shè)計(jì)與分析>算法概述116.算法分析對(duì)執(zhí)行該算法所消耗的計(jì)算機(jī)資源進(jìn)行估算,對(duì)數(shù)值型算法還需分析算法的穩(wěn)定性和誤差等問(wèn)題.計(jì)算機(jī)資源中最重要的是時(shí)間和空間資源,執(zhí)行一個(gè)算法程序需要的時(shí)間和占用的內(nèi)存空間分別稱為算法的時(shí)間復(fù)雜度和空間復(fù)雜性.算法設(shè)計(jì)與分析>算法概述12描述算法的方式一般有三種:自然語(yǔ)言,流程圖,偽代碼語(yǔ)言。偽代碼描述介于自然語(yǔ)言與程序設(shè)計(jì)語(yǔ)言之間。3.算法的描述算法設(shè)計(jì)與分析>算法概述134.

算法結(jié)構(gòu)算法設(shè)計(jì)與分析>算法概述任何算法都可由順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)這三塊“積木”通過(guò)組合和嵌套表達(dá)出來(lái)，遵循這種方法的程序設(shè)計(jì)，即為結(jié)構(gòu)化程序設(shè)計(jì)。145.

算法分類從解法上數(shù)值型算法:算法中的基本運(yùn)算為算術(shù)運(yùn)算.非數(shù)值型算法:算法中的基本運(yùn)算為邏輯運(yùn)算.從處理方式上串行算法:串行計(jì)算機(jī)上執(zhí)行的算法.并行算法:并行計(jì)算機(jī)上執(zhí)行的算法.本課程主要介紹非數(shù)值型的串行算法.算法設(shè)計(jì)與分析>算法概述15算法的復(fù)雜性:指執(zhí)行算法所消耗或占用的資源的數(shù)量一個(gè)算法所需資源越多,我們就說(shuō)它的復(fù)雜性越高,反之則低.空間復(fù)雜性算法的復(fù)雜性時(shí)間復(fù)雜性1.2

算法的復(fù)雜性分析算法設(shè)計(jì)與分析>算法概述16考慮空間復(fù)雜性的理由

在多用戶系統(tǒng)中運(yùn)行時(shí)，需指明分給該程序的內(nèi)存大小；

需預(yù)先知道計(jì)算機(jī)系統(tǒng)是否有足夠的內(nèi)存來(lái)運(yùn)行該程序；

一個(gè)問(wèn)題可能有若干個(gè)不同的內(nèi)存解決方案，從中擇取；

用空間復(fù)雜性估計(jì)一個(gè)程序可能解決的問(wèn)題的最大規(guī)模。算法設(shè)計(jì)與分析>算法概述17算法設(shè)計(jì)與分析>算法概述考慮時(shí)間復(fù)雜性的理由18

某些計(jì)算機(jī)用戶需要提供程序運(yùn)行時(shí)間的上限（用戶可接受的）；

所開(kāi)發(fā)的程序需要提供一個(gè)滿意的實(shí)時(shí)反應(yīng)。算法設(shè)計(jì)與分析>算法概述算法分析:(漸進(jìn)算法分析):對(duì)執(zhí)行算法所消耗或占用的資源進(jìn)行估算,給出算法耗費(fèi)的限界函數(shù).需解決兩個(gè)問(wèn)題:

如何度量復(fù)雜性?

如何分析復(fù)雜性?19例如 在數(shù)組中找分量c,兩個(gè)矩陣相乘,表中排序,遍歷一棵樹(shù),n:數(shù)組中分量的個(gè)數(shù)

n:矩陣的維數(shù)n:數(shù)組中分量的個(gè)數(shù)

n:樹(shù)中節(jié)點(diǎn)數(shù)1.復(fù)雜性的計(jì)量算法的復(fù)雜性: 算法運(yùn)行所需的時(shí)間和空間的數(shù)量.它與算法求解問(wèn)題的規(guī)模n,算法的輸入數(shù)I

及算法本身有關(guān).問(wèn)題的規(guī)模n:指問(wèn)題的輸入數(shù)據(jù)或初始數(shù)據(jù)的量.在不同的問(wèn)題中,n有不同的表現(xiàn)形式：算法設(shè)計(jì)與分析>算法概述20<算法不同>算法效率與計(jì)算機(jī)的性能有關(guān)，但此因素對(duì)所有算法的影響相同。5*5的矩陣相乘與10*10矩陣的矩陣相乘所需時(shí)間<問(wèn)題規(guī)模不算法設(shè)計(jì)與分析>算法概述空間均不相同；同>找c在數(shù)組A中的位置,c=A(1),與c=A(100),所需時(shí)間顯然也不同入數(shù)不同>順序查找還是折半查找速度也是不一樣的.<輸21令

n:

問(wèn)題規(guī)模

I:

輸入數(shù)據(jù)雜性,則C=f

(

n,

I,

A

)A:

算法本身

C:

算法的復(fù)將時(shí)間復(fù)雜性和空間復(fù)雜性分別考慮,并用T和S表示.則有:T=T(n,

I,

A) S=S

(n,

I,

A)將算法A

隱含在函數(shù)名中,不同函數(shù)名代表不同算法,則簡(jiǎn)化為T=T(

n,

I

) S=S(

n,

I

)算法設(shè)計(jì)與分析>算法概述22僅以時(shí)間復(fù)雜性為例將復(fù)雜性函數(shù)具體化.設(shè)一臺(tái)抽象計(jì)算機(jī)提供的元運(yùn)算有k種,記作

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

t1,…,tk;設(shè)在算法A中用到Oi的次數(shù)為

ei

,i=1,…,k,則ei=

ei

(n,

I)T=T(n,I)=當(dāng)問(wèn)題的規(guī)模n和算法確定后,T是輸入變?cè)猧的函數(shù).算法設(shè)計(jì)與分析>算法概述23說(shuō)明：我們不可能對(duì)規(guī)模為n的每一種合法輸入I都計(jì)算ei次，因?yàn)檩斎肟赡苁菬o(wú)窮集合,我們只能對(duì)規(guī)模為n的問(wèn)題的某類具有代表性的合法輸入統(tǒng)計(jì)相應(yīng)的ei.算法設(shè)計(jì)與分析>算法概述24最好情況:Tmin(n)=T(n,I)===平均情況:Tavg(n)

=

=P(I):

出現(xiàn)輸入為I的概25率其中

Dn

:規(guī)模為n的所有合法輸入的集合最壞情況:Tmax(n)=T(n,I)

===Dn中達(dá)到Tmin

(n)的一個(gè)輸入.Dn中達(dá)到Tmax(n)的一個(gè)輸入.算法設(shè)計(jì)與分析>算法概述算法設(shè)計(jì)與分析>算法概述當(dāng)一個(gè)問(wèn)題的輸入規(guī)模很大時(shí),算法的結(jié)構(gòu)又很復(fù)雜時(shí),采用前面介紹的精確分析就顯得過(guò)于繁瑣,為降低算法分析的代價(jià),同時(shí)又保證估算的精確度,引入一個(gè)簡(jiǎn)化的計(jì)算模型來(lái)評(píng)估算法的開(kāi)銷.稱為漸進(jìn)分析.漸進(jìn)分析是對(duì)問(wèn)題的規(guī)模充分大的算法開(kāi)銷的估算。T(n)的漸進(jìn)復(fù)雜性(漸進(jìn)表達(dá)式)

:(T(n)-

)/T(n)→0，n

→∞時(shí)漸進(jìn)階:

O,

Ω

,

θ262.復(fù)雜性的漸進(jìn)性態(tài)如果存在一個(gè)函數(shù)(T(n)

-使得當(dāng)n→∞,有)/

T(n)→0稱 是T(n)當(dāng)

n→

∞

時(shí)的漸進(jìn)性態(tài)

或 漸進(jìn)復(fù)雜性1.漸進(jìn)性態(tài)設(shè)T(n)為算法A的時(shí)間復(fù)雜性函數(shù)(輸入值固定.如Tmax,Tmin,Tavg),則它是n

的單增函數(shù)。算法設(shè)計(jì)與分析>算法概述27當(dāng)n充分大時(shí)用 代替T(n)作為算法復(fù)雜性的度量,以簡(jiǎn)化分析比較兩個(gè)算法時(shí)，如果他們的階不同，就可分出效率高低。故此時(shí)只需關(guān)心 最高限的階即可。可忽略最高項(xiàng)系數(shù)或低階項(xiàng)。在數(shù)學(xué)上,T(n)與 有相同的最高階項(xiàng).可取略去T(n)的低階項(xiàng)后剩余的主項(xiàng).例如

T(n)=3n2+4nlogn+7,

則 可以是3n2算法設(shè)計(jì)與分析>算法概述為282.漸進(jìn)性態(tài)的階例如3n=O(n),

n+1024=O(n),

2n2+11n-10=O(n2)n2=O(n3)

?n3=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í)間的上限

)算法設(shè)計(jì)與分析>算法概述√29三點(diǎn)注意:用來(lái)作比較的函數(shù)g(n)應(yīng)該盡量接近f(n).例如3n+2=O(n2)松散的界限；3n+2=O(n)較好的界限不要產(chǎn)生錯(cuò)誤界限。例如n2+100n+6，當(dāng)n<3時(shí)，n2+100n+6<106n，由此就認(rèn)為n2+100n+6＝O(n).f(n)=O(g(n))不能寫成g(n)=O(f(n))因?yàn)閮烧卟⒉坏葍r(jià)。實(shí)際上，這里的等號(hào)并不是通常相等的含義。算法設(shè)計(jì)與分析>算法概述30O(f

)+O(g)=O(

max(f,

g

))O(f

)+O(g)=O(f+g)O(f

)·O(g)=O(f·g)如果g(n)=O(f

(n)),則O(f

)+O(g)=O(f

)f=O(

f

)O(

cf

(n))=O(

f(n))算法設(shè)計(jì)與分析>算法概述運(yùn)算規(guī)則31證明:O(f

)+O(g)=O(max(f,g))算法設(shè)計(jì)與分析>算法概述設(shè)F(N)=O(f).根據(jù)O的定義,存在正常數(shù)C1和自然數(shù)N1,使得對(duì)所有N≥N1,有F(N)≤C1f(N).類似G(N)=O(g).根據(jù)O的定義,存在正常數(shù)C2和自然數(shù)N2,使得對(duì)所有N≥N2,有G(N)≤C2g(N).令C3=max{C1,C2},N3=max{N1,N2},h(N)=max{f,g},則對(duì)所有N≥N3,有F(N)≤C1f(N)

≤C1h(N)≤C3h(N).類似G(N)≤C2g(N)≤C2h(N)≤C3h(N).O(f

)+O(g)=

F(N)

+G(N)≤C3h(N)+C3h(N)=2C3h(N)=

O(h)=O(

max(

f,

g

)

)32例 估計(jì)如下二重循環(huán)的Tmax(n)的階.分析:內(nèi)循環(huán)體只需O(1)時(shí)間,故for

i:=

1ton

dofor

j:=1toi

do{s1,s2,s3,s

4};

s1,s2,s3,s4為單一賦值語(yǔ)句內(nèi)循環(huán)共需外循環(huán)共需算法設(shè)計(jì)與分析>算法概述2.

O(f)+O(g)=O(f+g)33(2)

大Ω表示法

(算法運(yùn)行時(shí)間的下限）若?正常數(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)的階算法設(shè)計(jì)與分析>算法概述例

T(n)=c1n2+c2n

,

則T(n)=Ω

(n2),34f

(n)

=θ(g(n)

)等價(jià)于

f(n)=O(g

(n)

)

且

f(n)=Ω(g

(n)

)稱函數(shù)f(n)與g(n)同階.(3)θ表示法例T(n)=c1n2+c2n,則T(n)=θ

(n2)算法設(shè)計(jì)與分析>算法概述35多項(xiàng)式階算法(有效算法):若算法的最壞情形時(shí)間復(fù)雜度T(n)=O(nk);指數(shù)階算法:若算法的最壞情形時(shí)間復(fù)雜度T(n)=Ω(an),a>1.

這類算法可認(rèn)為計(jì)算上不可行的算法.算法設(shè)計(jì)與分析>算法概述算法復(fù)雜性分類:36最優(yōu)算法:

時(shí)間復(fù)雜性達(dá)到其下界的算法.常見(jiàn)的多項(xiàng)式階有:O(1)

< O(logn)

<常見(jiàn)的指數(shù)階有:O(n)

<

O(nlogn)< O(n2)

<

O(n3)O(2n)

< O(n!)

<

O(nn)一般當(dāng)n很大時(shí),在計(jì)算機(jī)上運(yùn)行比O(logn)復(fù)雜性更高的算法已經(jīng)很困難了.對(duì)規(guī)模較小的問(wèn)題,決定算法工作效率的可能是算法的簡(jiǎn)單性而不是算法執(zhí)行的時(shí)間.當(dāng)比較兩個(gè)算法的效率時(shí),若兩個(gè)算法是同階的,必須進(jìn)一步考察階的常數(shù)因子才能辨別優(yōu)劣.算法設(shè)計(jì)與分析>算法概述兩點(diǎn)說(shuō)明:37時(shí)間復(fù)雜度并不是表示一個(gè)程序解決問(wèn)題需要花多少時(shí)間，而是當(dāng)問(wèn)題規(guī)模擴(kuò)大后，程序需要的時(shí)間長(zhǎng)度增長(zhǎng)得有多快。38算法設(shè)計(jì)與分析>算法概述1.3

NP完全性理論確定性算法：設(shè)A是求解問(wèn)題的一個(gè)算法,如果在算法的整個(gè)執(zhí)行過(guò)程中,每一步只有一個(gè)確定的選擇,并且對(duì)于同一輸入實(shí)例運(yùn)行算法,所得的結(jié)果嚴(yán)格一致.P類問(wèn)題:對(duì)于某個(gè)判定問(wèn)題II，對(duì)于規(guī)模為n的輸入，能夠在O(nk)得到y(tǒng)es或no的求解。時(shí)間內(nèi)運(yùn)行一個(gè)確定性算法答案，其中k為某一確定常數(shù)僅回答yes或no的問(wèn)題算法設(shè)計(jì)與分析>算法概述非確定性算法：設(shè)A是求解問(wèn)題的一個(gè)算法,如果算法以如下猜測(cè)并驗(yàn)證的方式工作,算法A是非確定算法.(1)猜測(cè)階段:對(duì)問(wèn)題的輸入實(shí)例產(chǎn)程一個(gè)任意字符串y,在算法的每一次執(zhí)行y的值可能不同,猜測(cè)以一種非確定性的形式工作;(2)驗(yàn)證階段:用一個(gè)確定性算法驗(yàn)證:a)檢查在猜測(cè)階段產(chǎn)生的串y是否是合適的形式，如果不是，算法停止得到no；b)如果y是合適的形式，再驗(yàn)證它是否是問(wèn)題的解，如果是算法停止得到y(tǒng)es，否則算法停止得到no。算法設(shè)計(jì)與分析>算法概述NP類問(wèn)題:對(duì)于某個(gè)判定問(wèn)題II，對(duì)于規(guī)模為n的輸入，能夠在O(nk)時(shí)間內(nèi)運(yùn)行一個(gè)非確定性算法求解得到y(tǒng)es或no,其中k為某一確定常數(shù)，該判定問(wèn)題II是一個(gè)NP類輸入轉(zhuǎn)換IO'輸出轉(zhuǎn)換OI'算法A問(wèn)題。NP完全問(wèn)題：令I(lǐng)I是個(gè)判定問(wèn)題，如果問(wèn)題II屬于NP類問(wèn)題，并且對(duì)NP類問(wèn)題中的每個(gè)問(wèn)題II’，都有(規(guī)約),則稱判定問(wèn)題II是個(gè)NP完全問(wèn)題。問(wèn)題II'問(wèn)題II算法設(shè)計(jì)與分析>算法概述NP完全問(wèn)題P類問(wèn)題:能在多項(xiàng)式時(shí)間內(nèi)解決的問(wèn)題。NP類問(wèn)題:在多項(xiàng)式