計(jì)算機(jī)算法設(shè)計(jì)與分析第二章導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)

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

DesignandAnalysisofComputerAlgorithms大學(xué)軟件學(xué)院

12第二章：導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)32.1算法（概念）2.2分析算法2.3用SPARKS語(yǔ)言寫算法(略)2.4基本數(shù)據(jù)結(jié)構(gòu)(略)第二章導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)4計(jì)算的數(shù)學(xué)本質(zhì)圖靈機(jī)是計(jì)算機(jī)的數(shù)學(xué)原型算法的計(jì)算能力和圖靈機(jī)在數(shù)學(xué)上是等價(jià)的5一、什么是算法算法屬于難于定義的概念算法的非形式描述：算法就是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問(wèn)題的一系列運(yùn)算。數(shù)值計(jì)算方法求解數(shù)值問(wèn)題，插值計(jì)算、數(shù)值積分等非數(shù)值計(jì)算方法求解非數(shù)值問(wèn)題，主要進(jìn)行判斷比較算法2.1算法6二、算法的五個(gè)重要特性算法(Algorithm)確定性每一種運(yùn)算必須要有確切的定義，無(wú)二義性能行性運(yùn)算都是基本運(yùn)算，原理上能在有限時(shí)間內(nèi)完成輸入有0個(gè)或多個(gè)輸入輸出一個(gè)或多個(gè)輸出有窮性

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

)8三、算法學(xué)習(xí)的五個(gè)內(nèi)容如何設(shè)計(jì)算法運(yùn)用一些基本設(shè)計(jì)策略規(guī)劃算法如何表示算法用恰當(dāng)?shù)姆绞奖硎舅惴ㄈ绾未_認(rèn)算法算法正確性的證明(算法確認(rèn)algorithmvalidation)如何分析算法通過(guò)時(shí)間和空間復(fù)雜度的分析，確定算法的優(yōu)劣如何測(cè)試程序測(cè)試程序是否會(huì)產(chǎn)生錯(cuò)誤的結(jié)果2.1算法9一、如何分析算法

分析算法的目的 設(shè)計(jì)更高效的算法算法分析的前提 要求獨(dú)立于具體的軟硬件環(huán)境單純分析算法 一臺(tái)通用計(jì)算機(jī)(理想情況下)

順序處理、每次一條指令、存儲(chǔ)容量足夠大、 存取時(shí)間恒定2.2分析算法10一、如何分析算法算法分析的準(zhǔn)備：首先確定使用哪些運(yùn)算以及執(zhí)行這些運(yùn)算所用的時(shí)間。(運(yùn)算包括基本運(yùn)算和由一些更基本的任意長(zhǎng)序列的運(yùn)算所組成的復(fù)雜運(yùn)算)其次是要確定出能反映算法在各種情況下工作的數(shù)據(jù)集。（即要求我們編造出能產(chǎn)生最好、最壞和有代表性情況的數(shù)據(jù)配置，通過(guò)使用這些數(shù)據(jù)來(lái)運(yùn)行算法，以更了解算法的性能）2.2分析算法11二、全面分析算法的兩個(gè)階段事前分析(aprioranalysis)求出該算法的一個(gè)時(shí)間限界函數(shù)事前分析只限于每條語(yǔ)句的頻率計(jì)數(shù)(frequencycount)語(yǔ)句的執(zhí)行次數(shù)，與所用的機(jī)器無(wú)關(guān)，且獨(dú)立于程序設(shè)計(jì)語(yǔ)言，可由算法直接確定事后測(cè)試(aposteriortesting)

收集此算法的實(shí)際執(zhí)行時(shí)間和占用空間的統(tǒng)計(jì)資料2.2分析算法12例：計(jì)算語(yǔ)句xx+y在下面三個(gè)程序段中的頻率計(jì)數(shù)beginxx+yendFC:1beginfori1tondo

xx+yendFC:nbeginfori1tondoforj1tondo

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

確定一個(gè)算法的數(shù)量級(jí)十分重要，因?yàn)樗诒举|(zhì)上反映了算法所需的計(jì)算時(shí)間。準(zhǔn)確分析出一個(gè)算法的計(jì)算時(shí)間有時(shí)是很困難的，因此我們對(duì)算法的計(jì)算時(shí)間進(jìn)行漸進(jìn)表示。2.2分析算法13算法復(fù)雜性分析形式化表述算法復(fù)雜性即算法所需要的計(jì)算機(jī)資源算法的時(shí)間復(fù)雜性T(n)；算法的空間復(fù)雜性S(n)。其中n是問(wèn)題的規(guī)模（輸入大?。?。14算法的時(shí)間復(fù)雜性（1）最壞情況下的時(shí)間復(fù)雜性

Tmax(n)=max{T(I)|size(I)=n}（2）最好情況下的時(shí)間復(fù)雜性

Tmin(n)=min{T(I)|size(I)=n}（3）平均情況下的時(shí)間復(fù)雜性

Tavg(n)=

其中I是問(wèn)題的規(guī)模為n的實(shí)例，p(I)是實(shí)例I出現(xiàn)的概率。15三、計(jì)算時(shí)間的漸進(jìn)表示2.2分析算法T(n),當(dāng)n;(T(n)-t(n))/T(n)0

，當(dāng)n;t(n)是T(n)的漸近性態(tài)，為算法的漸近復(fù)雜性。在數(shù)學(xué)上，t(n)是T(n)的漸近表達(dá)式，是T(n)略去低階項(xiàng)留下的主項(xiàng)。它比T(n)簡(jiǎn)單。16三、計(jì)算時(shí)間的漸進(jìn)表示定義2.1：如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≥n0，有|f(n)|≤c|g(n)|

則記作：f(n)=O(g(n))Note：f(n)表示算法的計(jì)算時(shí)間，n是輸入或輸出量

g(n)是在事前分析中確定的某個(gè)形式的簡(jiǎn)單函數(shù)

f(n)與機(jī)器和語(yǔ)言有關(guān)，而g(n)是獨(dú)立于機(jī)器和語(yǔ)言的

一個(gè)算法具有O(g(n))的計(jì)算時(shí)間是指如果這個(gè)算法用n值不變的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是小于|g(n)|的一個(gè)常數(shù)倍。

g(n)是計(jì)算時(shí)間f(n)的一個(gè)上界函數(shù)，f(n)的數(shù)量級(jí)就是g(n)2.2分析算法17|f(n)|≤c|g(n)|f(n)=O(g(n))f(n)18O函數(shù)舉例反例證明n3O(n2)如不然，則存在C和N使得當(dāng)nN時(shí)，有n3Cn2

即nC顯然當(dāng)n

max{N,C}+1時(shí)不成立。所以，

n3

O(n2)19定理2.1：若A(n)=amnm+…+a1n+a0是一個(gè)m次多項(xiàng)式，則A(n)=O(nm)證明：取n0=1，當(dāng)n≥n0時(shí)由A(n)的定義和不等式關(guān)系|A+B|≤|A|+|B|有

|A(n)|=|amnm+…+a1n+a0|≤|am|nm+…+|a1|

n+|a0| =(|am|+|am-1|/n…+|a0|/nm)

nm

≤(|am|+|am-1|…+|a0|)

nm取c=|am|+|am-1|…+|a0|，有|A(n)|≤cnm即：A(n)=O(nm)，定理得證。2.2分析算法20定理2.1表明，變量n的最高階數(shù)為m的任一多項(xiàng)式，與nm同階。因此一個(gè)計(jì)算時(shí)間為m階多項(xiàng)式的算法，其時(shí)間都可以用O(nm)來(lái)表示。

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

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

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

其中m=max{mi|1≤i≤k}2.2分析算法21數(shù)量級(jí)對(duì)算法有效性影響的實(shí)例

多項(xiàng)式時(shí)間算法(polynomialtimealgorithm):

用多項(xiàng)式來(lái)對(duì)其計(jì)算時(shí)間限界的算法

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)

指數(shù)時(shí)間算法(exponentialtimealgorithm):

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

O(2n)<O(n!)<O(nn)2.2分析算法從計(jì)算時(shí)間上可把算法分為兩類：22定義2.2：如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≥n0，有|f(n)|≥c|g(n)|

則記作：f(n)=Ω(g(n))定義2.3：如果存在兩個(gè)正常數(shù)c1,c2和n0，對(duì)于所有的n≥n0，有c1|g(n)|≤|f(n)|≤c2|g(n)|

則記作：f(n)=Θ(g(n))在某些情況下，可能會(huì)出現(xiàn)g(n)既是f(n)的上界又是它的下界，為此引入數(shù)學(xué)符號(hào)Θ來(lái)表示這種情況稱g(n)是計(jì)算時(shí)間f(n)的一個(gè)下界函數(shù)2.2分析算法23|f(n)|≥c|g(n)|f(n)=Ω(g(n))f(n)24c1|g(n)|≤|f(n)|≤c2|g(n)|f(n)=Θ(g(n))f(n)25非緊上界函數(shù)o

o(g(n))={f(n)|對(duì)于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對(duì)所有nn0有：0f(n)<cg(n)}等價(jià)于

f(n)/g(n)0

，asn。非緊下界函數(shù)

(g(n))={f(n)|對(duì)于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對(duì)所有nn0有：0cg(n)

<

f(n)}等價(jià)于

f(n)/g(n)

，asn。f(n)

(g(n))

g(n)

o(f(n))Notes:補(bǔ)充定義26漸近表示函數(shù)在等式和不等式中的意義f(n)=(g(n))的確切意義是：f(n)

(g(n))。一般情況下，等式和不等式中的漸近記號(hào)(g(n))表示(g(n))中的某個(gè)函數(shù)。例如：2n2+3n+1=2n2+(n)表示

2n2+3n+1=2n2+f(n)，其中f(n)是(n)中某個(gè)函數(shù)。等式和不等式中漸近記號(hào)O,o,和的意義是類似的。27漸近分析中函數(shù)比較a=f(n)；b=Cg(n)f(n)=O(g(n))ab;f(n)=(g(n))ab;f(n)=(g(n))a=b;f(n)=o(g(n))a<b;f(n)=(g(n))a>b.28漸近表示函數(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))；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))；29（2）反身性：f(n)=(f(n))；f(n)=O(f(n))；f(n)=(f(n)).（3）對(duì)稱性：f(n)=(g(n))

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

g(n)=(f(n))；f(n)=o(g(n))

g(n)=

(f(n))；30（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))；g(n)=O(f(n))O(f(n))+O(g(n))=

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

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

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

c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。則對(duì)所有的nn3，有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)}).32規(guī)則O(f(n))+O(g(n))=

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

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

c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=f(n)+g(n)。則對(duì)所有的nn3，有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)).33規(guī)則O(f(n))*O(g(n))=

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

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

c2g(n)。令c3=c1*c2，n3=max{n1,n2}，h(n)=f(n)*g(n)。則對(duì)所有的nn3，有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)).34算法分析中常見的復(fù)雜性函數(shù)35小規(guī)模數(shù)據(jù)36中等規(guī)模數(shù)據(jù)37不同時(shí)間復(fù)雜性函數(shù)的對(duì)比38四、常用的整數(shù)求和公式通式：2.2分析算法39時(shí)空性能分布圖 算法時(shí)間的準(zhǔn)確測(cè)量 時(shí)鐘不準(zhǔn)確造成的噪聲 解決方法 增大規(guī)模 重復(fù)執(zhí)行 分布圖的做法402.3

用SPARKS語(yǔ)言寫算法SPARKS語(yǔ)言的基本數(shù)據(jù)類型：整型(integer),實(shí)型(real),布爾型(boolean),字符型(char)SPARKS語(yǔ)言的變量命名規(guī)則：以字母開頭，不允許使用特殊字符，不允許與保留字重復(fù)賦值語(yǔ)句：變量表達(dá)式邏輯運(yùn)算符：and,or,not關(guān)系運(yùn)算符：<，≤，=，≠，>，≥布爾值:True，F(xiàn)alse數(shù)組：任意整數(shù)下界和上界的多維數(shù)組例:integerx,y;charch;例:integerA(1:10);realB(1:3,1:4);41SPARKS語(yǔ)言的條件語(yǔ)句if條件thens1endifif條件thens1elses2 endif ?

if(條件){s1}else{s2} ?if(條件){s1}case

:

條件1:s1 …

:

條件n:sn

:else:sn+1endcaseSPARKS語(yǔ)言的case語(yǔ)句case

條件1:s1 …

條件n:snelse:sn+1endcase?2.3

用SPARKS語(yǔ)言寫算法42SPARKS語(yǔ)言的循環(huán)語(yǔ)句while條件doSrepeatloopSuntil條件repeatfor變量初值to終值by變量增值doSrepeatwhile(條件){S}do{S}while(條件)for(變量=初值;循環(huán)條件;變量增值){S}2.3

用SPARKS語(yǔ)言寫算法43SPARKS語(yǔ)言的函數(shù)(過(guò)程)procedureNAME(<參數(shù)列表>)

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

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

用