算法設(shè)計與分析課件

第一章

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

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

算法與程序1

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

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

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

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

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

f(x)

=1

x>1000

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

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

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

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

如

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

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

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

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

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

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

一個問題可能有若干個不同的內(nèi)存解決方案，從中擇?。?/p>

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

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

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

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

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

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

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

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

n:

問題規(guī)模

I:

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

(

n,

I,

A

)A:

算法本身

C:

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

I,

A) S=S

(n,

I,

A)將算法A

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

n,

I

) S=S(

n,

I

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

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

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

ei

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

ei

(n,

I)T=T(n,I)=當(dāng)問題的規(guī)模n和算法確定后,T是輸入變元i的函數(shù).算法設(shè)計與分析>算法概述23說明：我們不可能對規(guī)模為n的每一種合法輸入I都計算ei次，因為輸入可能是無窮集合,我們只能對規(guī)模為n的問題的某類具有代表性的合法輸入統(tǒng)計相應(yīng)的ei.算法設(shè)計與分析>算法概述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)的一個輸入.Dn中達(dá)到Tmax(n)的一個輸入.算法設(shè)計與分析>算法概述算法設(shè)計與分析>算法概述當(dāng)一個問題的輸入規(guī)模很大時,算法的結(jié)構(gòu)又很復(fù)雜時,采用前面介紹的精確分析就顯得過于繁瑣,為降低算法分析的代價,同時又保證估算的精確度,引入一個簡化的計算模型來評估算法的開銷.稱為漸進(jìn)分析.漸進(jìn)分析是對問題的規(guī)模充分大的算法開銷的估算。T(n)的漸進(jìn)復(fù)雜性(漸進(jìn)表達(dá)式)

:(T(n)-

)/T(n)→0，n

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

O,

Ω

,

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

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

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

n→

∞

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

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

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

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

則 可以是3n2算法設(shè)計與分析>算法概述為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時,有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表示法

(算法運行時間的上限

)算法設(shè)計與分析>算法概述√29三點注意:用來作比較的函數(shù)g(n)應(yīng)該盡量接近f(n).例如3n+2=O(n2)松散的界限；3n+2=O(n)較好的界限不要產(chǎn)生錯誤界限。例如n2+100n+6，當(dāng)n<3時，n2+100n+6<106n，由此就認(rèn)為n2+100n+6＝O(n).f(n)=O(g(n))不能寫成g(n)=O(f(n))因為兩者并不等價。實際上，這里的等號并不是通常相等的含義。算法設(shè)計與分析>算法概述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è)計與分析>算法概述運算規(guī)則31證明:O(f

)+O(g)=O(max(f,g))算法設(shè)計與分析>算法概述設(shè)F(N)=O(f).根據(jù)O的定義,存在正常數(shù)C1和自然數(shù)N1,使得對所有N≥N1,有F(N)≤C1f(N).類似G(N)=O(g).根據(jù)O的定義,存在正常數(shù)C2和自然數(shù)N2,使得對所有N≥N2,有G(N)≤C2g(N).令C3=max{C1,C2},N3=max{N1,N2},h(N)=max{f,g},則對所有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例 估計如下二重循環(huán)的Tmax(n)的階.分析:內(nèi)循環(huán)體只需O(1)時間,故for

i:=

1ton

dofor

j:=1toi

do{s1,s2,s3,s

4};

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

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

大Ω表示法

(算法運行時間的下限）若?正常數(shù)c和自然數(shù)N0使得當(dāng)

n

≥

N0

時,有f(n)≥cg(n)則稱函數(shù)f(n)在n充分大時有下限,

且

g(n)是它的一個下限,記為f(n)=Ω

(g(n)

)

也稱f(n)的階不低于g(n)的階算法設(shè)計與分析>算法概述例

T(n)=c1n2+c2n

,

則T(n)=Ω

(n2),34f

(n)

=θ(g(n)

)等價于

f(n)=O(g

(n)

)

且

f(n)=Ω(g

(n)

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

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

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

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

< O(logn)

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

<

O(nlogn)< O(n2)

<

O(n3)O(2n)

< O(n!)

<

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

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