算法分析課件第01章-PPT幻燈片

基本內(nèi)容導(dǎo)引（第一、二章）基本的算法設(shè)計(jì)策略分治法（第四章）貪心方法（第五章）動態(tài)規(guī)劃（第六章）回溯法（第八章）分支－限界法（第九章）基本算法分析方法NP-難度和NP-完全問題（第十章）學(xué)習(xí)目標(biāo)掌握基本的算法設(shè)計(jì)方法掌握分析算法的基本方法（時間、空間復(fù)雜度分析）靈活運(yùn)用基本的算法設(shè)計(jì)方法，用于解決實(shí)際問題第二章導(dǎo)引2.1算法2.2分析算法及數(shù)學(xué)基礎(chǔ)2.3用SPARKS語言寫算法2.4基本數(shù)據(jù)結(jié)構(gòu)二、算法的五個重要特性算法(Algorithm)確定性

每一種運(yùn)算必須要有確切的定義，無二 義性能行性

運(yùn)算都是基本運(yùn)算，原則上能在有限時間內(nèi)完成輸入

有0個或多個輸入輸出

一個或多個輸出有窮性

在執(zhí)行了有窮步運(yùn)算后終止Notes：僅僅有窮還不夠，還要在現(xiàn)代計(jì)算機(jī)上有效才行程序(Program)(計(jì)算過程)程序是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。程序可以不滿足算法的性質(zhì)(5)有窮性。例如操作系統(tǒng)，是一個在無限循環(huán)中執(zhí)行的程序，因而不是一個算法。操作系統(tǒng)的各種任務(wù)可看成是單獨(dú)的問題，每一個問題由操作系統(tǒng)中的一個子程序通過特定的算法來實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止。程序=算法+數(shù)據(jù)結(jié)構(gòu)(ByWirth

)用計(jì)算機(jī)求解問題的步驟設(shè)計(jì)、確認(rèn)、分析、編碼、檢查、調(diào)試、計(jì)時證明正確性分析算法理解問題精確解或近似解算法設(shè)計(jì)策略選擇數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)算法設(shè)計(jì)程序三、算法學(xué)習(xí)的五個內(nèi)容如何設(shè)計(jì)算法運(yùn)用一些基本設(shè)計(jì)策略規(guī)劃算法如何表示算法用恰當(dāng)?shù)姆绞奖硎舅惴ㄈ绾未_認(rèn)算法算法正確性的證明(算法確認(rèn)algorithmvalidation)如何分析算法通過時間和空間復(fù)雜度的分析，確定算法的優(yōu)劣如何測試程序測試程序是否會產(chǎn)生錯誤的結(jié)果設(shè)計(jì)高效算法SPARKS語言窮舉、數(shù)學(xué)歸納法、反證法、構(gòu)造性證明、測試目的是比較和改進(jìn)算法調(diào)試和時空分布圖第二章導(dǎo)引2.1算法2.2分析算法及數(shù)學(xué)基礎(chǔ)2.3用SPARKS語言寫算法2.4基本數(shù)據(jù)結(jié)構(gòu)一、如何分析算法分析算法的目的

設(shè)計(jì)更高效的算法算法分析的前提

要求獨(dú)立于具體的軟硬件環(huán)境單純分析算法 一臺通用計(jì)算機(jī)(理想情況下)

順序處理、每次一條指令、存儲容量足夠大、 存取時間恒定算法分析是對一個算法需要多少計(jì)算時間和存儲空間作定量的分析。2.2分析算法2.2分析算法一、如何分析算法算法分析的準(zhǔn)備：首先確定使用哪些運(yùn)算以及執(zhí)行這些運(yùn)算所用的時間。(運(yùn)算包括基本運(yùn)算和由一些更基本的任意長序列的運(yùn)算所組成的復(fù)雜運(yùn)算)其次是要確定出能反映算法在各種情況下工作的數(shù)據(jù)集。(即要求我們編造出能產(chǎn)生最好、最壞和有代表性情況的數(shù)據(jù)配置，通過使用這些數(shù)據(jù)來運(yùn)行算法，以更了解算法的性能)

二、全面分析算法的兩個階段事前分析(aprioranalysis)求出該算法的一個時間限界函數(shù)(一些關(guān)于參數(shù)的函數(shù))事前分析只限于每條語句的頻率計(jì)數(shù)(frequencycount).語句的執(zhí)行次數(shù)，與所用的機(jī)器無關(guān)，且獨(dú)立于程序設(shè)計(jì)語言，可由算法直接確定事后測試(aposteriortesting)

收集此算法的實(shí)際執(zhí)行時間和占用空間的統(tǒng)計(jì)資料2.2分析算法例：計(jì)算語句x

x+y在下面三個程序段中的頻率計(jì)數(shù)beginx

x+yendFC:1beginfori

1tondo

x

x+yendFC:nbeginfori

1tondoforj

1tondo

x

x+yendFC:n2語句的數(shù)量級是指執(zhí)行它的頻率計(jì)數(shù)之和算法的數(shù)量級是指算法的所有語句的頻率計(jì)數(shù)之和

確定一個算法的數(shù)量級十分重要，因?yàn)樗诒举|(zhì)上反映了算法所需的計(jì)算時間。準(zhǔn)確分析出一個算法的計(jì)算時間有時是很困難的，因此我們對算法的計(jì)算時間進(jìn)行漸進(jìn)表示。2.2分析算法算法復(fù)雜性分析形式化表述算法復(fù)雜性即算法所需要的計(jì)算機(jī)資源算法的時間復(fù)雜性T(n)；算法的空間復(fù)雜性S(n)。其中n是問題的規(guī)模（輸入大小）。算法的時間復(fù)雜性（1）最壞情況下的時間復(fù)雜性Tmax(n)=max{T(I)|size(I)=n}（2）最好情況下的時間復(fù)雜性Tmin(n)=min{T(I)|size(I)=n}（3）平均情況下的時間復(fù)雜性Tavg(n)=其中I是問題規(guī)模為n的實(shí)例，p(I)是實(shí)例I出現(xiàn)的概率。2.2分析算法n：問題的規(guī)模f(n)：算法的計(jì)算時間g(n)：形式簡單的函數(shù)(f(n)-g(n))/f(n)0，asn;在數(shù)學(xué)上，g(n)是f(n)的漸近表達(dá)式，是f(n)略去低階項(xiàng)留下的主項(xiàng)。它比f(n)簡單。三、計(jì)算時間的漸近表示定義1.1如果存在兩個正常數(shù)c和n0，對于所有的n

n0，有|f(n)|

c|g(n)|，則記做f(n)

O(g(n)).

f(n)表示算法的計(jì)算時間，n是輸入或輸出量，g(n)是在事前分析中確定的某個形式的簡單函數(shù)，f(n)與機(jī)器和語言有關(guān)，而g(n)是獨(dú)立于機(jī)器和語言的。一個算法具有O(g(n))的計(jì)算時間是指如果這個算法用n

值不變的同一類數(shù)據(jù)在某臺機(jī)器上運(yùn)行時，所用的時間

總是小于|g(n)|的一個常數(shù)倍。

g(n)是計(jì)算時間f(n)的一個上界函數(shù)，f(n)的數(shù)量級就

是g(n)。例子

f(n)

O(g(n))f(n)＝3n,

g(n)=4nf(n)＝n+1024,

g(n)=1025nf(n)＝2n2+11n-10,

g(n)=3n2f(n)＝n2,

g(n)=n3反例：f(n)＝n3,

g(n)=n2定理1.1若A(n)=amnm+……+a1n+a0是一個m次多項(xiàng)式，則A(n)=O(nm)定理1.1表明，變量n的最高階數(shù)為m的任一多項(xiàng)式，與nm同階。因此一個計(jì)算時間為m階多項(xiàng)式的算法，其時間都可以用O(nm)來表示。

若一個算法有數(shù)量級為c1nm1，c2nm2，…cknmk的

k個語句，則算法的數(shù)量級及計(jì)算時間就是

c1nm1+c2nm2+…+cknmk=O(nm)

其中m=max{mi|1

i

k}從計(jì)算時間上對算法分類多項(xiàng)式時間算法(polynomialtimealgorithm):

用多項(xiàng)式來對其計(jì)算時間限界的算法

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指數(shù)時間算法(exponentialtimealgorithm):

計(jì)算時間用指數(shù)函數(shù)限界的算法

O(2n)<O(n!)<O(nn)數(shù)量級對算法有效性影響的實(shí)例不同時間復(fù)雜性函數(shù)的對比小規(guī)模數(shù)據(jù)中等規(guī)模數(shù)據(jù)定義1.2

如果存在兩個正常數(shù)c和n0，對于所有的n

n0，有|f(n)|

c

|g(n)|，則記做f(n)

(g(n)).

這種情況稱g(n)是計(jì)算時間f(n)的一個下界函數(shù)。在某些情況下，可能會出現(xiàn)g(n)既是f(n)的上界，又是它的下界，為此引入數(shù)學(xué)符號Θ來表示。定義1.3

如果存在兩個正常數(shù)c1,c2和n0，對于所有的n

n0，有c1|g(n)|

|f(n)|

c2|g(n)|，則記作：f(n)=Θ(g(n)).漸近分析中函數(shù)比較a=f(n)；b=c

g(n)f(n)=O(g(n))

ab;f(n)=

(g(n))

ab;f(n)=

(g(n))

a=b;漸近表示函數(shù)的若干性質(zhì)（1）傳遞性f(n)=

(g(n))，g(n)=

(h(n))

f(n)=

(h(n))；f(n)=O(g(n))，g(n)=O

(h(n))

f(n)=O

(h(n))；f(n)=

(g(n))，g(n)=

(h(n))

f(n)=

(h(n))；（2）反身性f(n)=

(f(n))；f(n)=O(f(n))；f(n)=

(f(n)).（3）對稱性f(n)=

(g(n))

g(n)=

(f(n)).（4）互對稱性f(n)=O(g(n))

g(n)=

(f(n))；（5）算術(shù)運(yùn)算O(f(n))+O(g(n))=

O(max{f(n),g(n)})；O(f(n))+O(g(n))=

O(f(n)+g(n))；O(f(n))*O(g(n))=

O(f(n)*g(n))；O(cf(n))=

O(f(n))；f(n)=O(g(n))

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

O(g(n))。也有類似性質(zhì)，證明方法類似。規(guī)則O(f(n))+O(g(n))=

O(max{f(n),g(n)})的證明：對于任意f1(n)=O(f(n))，存在正常數(shù)c1和自然數(shù)n1，使得對所有n

n1，有f1(n)

c1f(n)。類似地，對于任意g1(n)=O(g(n))，存在正常數(shù)c2和自然數(shù)n2，使得對所有n

n2，有g(shù)1(n)

c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。則對所有的n

n3，有f1(n)+g1(n)

c1f(n)+c2g(n)

c3f(n)+c3g(n)=c3(f(n)+g(n))

2c3max{f(n),g(n)}=2c3h(n)=O(max{f(n),g(n)}).規(guī)則O(f(n))+O(g(n))=

O(f(n)+g(n))的證明：對于任意f1(n)=O(f(n))，存在正常數(shù)c1和自然數(shù)n1，使得對所有n

n1，有f1(n)

c1f(n)。類似地，對于任意g1(n)=O(g(n))，存在正常數(shù)c2和自然數(shù)n2，使得對所有n

n2，有g(shù)1(n)

c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=f(n)+g(n)。則對所有的n

n3，有O(f(n))+O(g(n))=f1(n)+g1(n)

c1f(n)+c2g(n)

c3f(n)+c3g(n)=c3(f(n)+g(n))=c3h(n)=O(f(n)+g(n)).規(guī)則O(f(n))*O(g(n))=

O(f(n)*g(n))的證明：對于任意f1(n)=O(f(n))，存在正常數(shù)c1>1和自然數(shù)n1，使得對所有n

n1，有f1(n)

c1f(n)。類似地，對于任意g1(n)=O(g(n))，存在正常數(shù)c2>1和自然數(shù)n2，使得對所有n

n2，有g(shù)1(n)

c2g(n)。令c3=c1*c2，n3=max{n1,n2}，h(n)=f(n)*g(n)。則對所有的n

n3，有O(f(n))*O(g(n))=f1(n)*g1(n)

c1f(n)*c2g(n)=

c3f(n)*g(n)=c3h(n)=O(f(n)*g(n)).數(shù)學(xué)基礎(chǔ)（1）求和公式通式算法漸近復(fù)雜性分析中常用函數(shù)（2）單調(diào)函數(shù)單調(diào)遞增：m

n

f(m)

f(n);單調(diào)遞減：m

n

f(m)

f(n);嚴(yán)格單調(diào)遞增：m

<n

f(m)<f(n);嚴(yán)格單調(diào)遞減：m

<n

f(m)>f(n).（3）取整函數(shù)

x：不大于x的最大整數(shù)；2.5

=22

=2

x：不小于x的最小整數(shù)。2.5=32=2取整函數(shù)的若干性質(zhì)

x-1<x

x

x<x+1；

n/2

+n/2=n;

對于n

0，a,b>0，有：

n/a/b=n/ab;

n/a/b=n/ab;

a/b(a+(b-1))/b;

a/b(a-(b-1))/b;

f(x)=x,g(x)=x為單調(diào)遞增函數(shù)。（4）多項(xiàng)式函數(shù)

p(n)=a0+a1n+a2n2+…+adnd；ad>0;

p(n)=

(nd);

p(n)=O(nk)

p(n)多項(xiàng)式有界；p(n)=O(1)

p(n)

c;（5）指數(shù)函數(shù)一些性質(zhì)

對于正整數(shù)m,n和實(shí)數(shù)a>0:a0=1;

a1=a;

a-1=1/a;(am)n=amn;

(am)n=(an)m;

aman=

am+n;

a>1

an為單調(diào)遞增函數(shù);

a>1

nb=o(an)ex

1+x;|x|11+x

ex

1+x+x2;

ex

=1+x+(x2),asx0;（5）對數(shù)函數(shù)logn=log2n;

lgn=log10n;

lnn=logen;

logkn=(logn)k;loglogn=log(logn);fora

0,b

0,c

0|x|1forx>-1,foranya>0,

, logbn=o(na)（6）階乘函數(shù)Stirling’sapproximation

時空分布圖要求時鐘及其精確度操作系統(tǒng)的工作方式處理噪聲

增加輸入規(guī)模增加執(zhí)行次數(shù)時空分布圖的做法用途比較同一問題的不同算法對算法改進(jìn)前后進(jìn)行比較主要內(nèi)容2.1算法2.2分析算法及數(shù)學(xué)基礎(chǔ)2.3用SPARKS語言寫算法2.4基本數(shù)據(jù)結(jié)構(gòu)2.3用SPARKS語言寫算法

SPARKS語言的基本數(shù)據(jù)類型：整型(integer),實(shí)型(real),布爾型(boolean),字符型(char)

SPARKS語言的變量命名規(guī)則：以字母開頭，不允許使用特殊字符，不允許與保留字重復(fù)

賦值語句：變量

表達(dá)式

邏輯運(yùn)算符：and,or,not

關(guān)系運(yùn)算符：

，

，

，

，

，

布爾值:true，false

數(shù)組：任意整數(shù)下界和上界的多維數(shù)組

integerA(l1:u1,…,ln:un);例:integerx,y;charch;例:integerA(1:10);realB(3:6,1:4);

SPARKS語言的條件語句if

條件

thens1endifif條件

thens1elses2endif

case

:

條件1:s1

…:

條件n:sn

:

else

:sn+1endcase

SPARKS語言的case語句2.3用SPARKS語言寫算法

SPARKS語言的循環(huán)語句while

條件

do

SrepeatloopSuntil

條件

repeatfor

變量

初值

to

終值

by

變量增值

do

Srepeat2.3用SPARKS語言寫算法

exit

轉(zhuǎn)到含有exit的最內(nèi)層循環(huán)語句后面的第一條語句

goto

標(biāo)號

cycle

結(jié)束本次循環(huán)

returnstop2.3用SPARKS語言寫算法

SPARKS語言的函數(shù)(過程)procedureNAME(<參數(shù)列表>)

<說明部分>Sreturn(<表達(dá)式>)endNAME函數(shù)名,通常用大寫字母說明參數(shù)的數(shù)據(jù)類型和函數(shù)中使用的變量parameters形式參數(shù)global全局變量local局部變量函數(shù)的語句部分

SPARKS語言的輸入、輸出：

read（參數(shù)表）；print