第一章 算法分析基本概念

算法設(shè)計技巧與分析

信工學(xué)院軟件與理論教研室

王培崇

2014年9月

紀(jì)律要求等情況說明：1、請勿隨意缺課；2、交作業(yè)（會適當(dāng)）；3、交試驗報告(務(wù)必運行程序讓我看結(jié)果，跟我說明程序的設(shè)計思想)4、實驗紀(jì)律（點名出勤，缺課1/3則沒有實驗分?jǐn)?shù)）5、最終分?jǐn)?shù)=試卷（70%）+實驗（30%）作業(yè)依據(jù)質(zhì)量融入實驗分?jǐn)?shù)中；6、考試形式：按照往常年的情況就是7或8道分析設(shè)計題（10-15分/題）。

涉及編程、設(shè)計思想、求解步驟分析等。一般情況下是沒有選擇、填空、判斷、簡答等的題目。算法的直覺含義:一個由有限的指令集組成的過程.

Knuth教授的定義:一個算法就是一個有窮規(guī)則的集合,其中的規(guī)則確定了一個解決某一特定類型問題的運算序列.算法導(dǎo)論中的定義：定義良好的計算過程，它取一個或一組作為輸入，并產(chǎn)生出一個或一組作為輸出。

1.1引言

在計算機(jī)科學(xué)領(lǐng)域，算法設(shè)計與分析是十分重要的。D.E.Knuth說：“計算機(jī)科學(xué)就是算法的研究”。

算法的規(guī)則須滿足特點:

(1)有窮性—執(zhí)行有限條指令后一定要終止。(2)確定性(無二義)—算法的每一步操作都必須有確切定義，不得有任何歧義性。(3)可(能)行性—算法的每一步操作都必須是可行的，即每步操作均能在有限時間內(nèi)完成。(4)輸入—一個算法有n（n>=0)個初始數(shù)據(jù)的輸入。(5)輸出—一個算法有一個或多個與輸入有某種關(guān)系的有效信息的輸出。IT產(chǎn)業(yè)中算法的應(yīng)用1、百度的深度學(xué)習(xí)研究院：招聘優(yōu)秀的機(jī)器學(xué)習(xí)、深度學(xué)習(xí)、大數(shù)據(jù)處理、BI等算法人才；百度搜索引擎算法的研究；

2、Google為什么能夠屹立業(yè)界：先進(jìn)的搜索引擎處理算法、非開源的云計算架構(gòu)；（注：hadoop是開源的）2、IT公司的競爭其實是科技含量的競爭，實質(zhì)就是在算法、架構(gòu)能否優(yōu)先的競爭。3、優(yōu)秀軟件公司的組織結(jié)構(gòu)：

a、CTO（首席架構(gòu)師）

b、需求分析師：負(fù)責(zé)跟甲方溝通；

c、系統(tǒng)設(shè)計師+核心算法設(shè)計小組人員。

d、項目經(jīng)理

e、編碼人員（這個階層人數(shù)最多）

f、測試小組；

g、質(zhì)量管理人員。

微軟高薪挖角：挖掉了borland

delphi的首席架構(gòu)師等人，去做VS系列以及設(shè)計C#等。（PS:編譯器中的優(yōu)化算法等等各個公司的編譯器均不相同。)搜索引擎中的各個算法處理方案也不盡相同。

DNA中基因?qū)π蛄信抨犚矔婕皬?fù)雜的算法。網(wǎng)絡(luò)數(shù)據(jù)傳輸中的路由選擇算法。（QQ、微信中的信息傳輸）

自動化軟件測試中的路徑測試用例自動生成技術(shù)。該問題也是一個復(fù)雜性相當(dāng)強的問題，會產(chǎn)生組合爆炸。圍棋軟件、象棋軟件等等（我們身邊的：查詢你自己的通話記錄，有優(yōu)秀算法的存在嗎？數(shù)據(jù)庫：優(yōu)化、索引）科學(xué)研究中的算法1、圖靈獎的獲得者絕大部分是做算法的研究的；姚期智：受聘于清華大學(xué)計算機(jī)系，唯一的一個圖靈獎華裔獲得者。2、尋求計算方面的突破?？捎嬎阈岳碚撆c計算復(fù)雜性理論等等。

最簡單的實例：圍棋中的人工智能其實就是一個計算復(fù)雜性太大的問題，各種組合會產(chǎn)生組合爆炸的問題，在目前圖靈機(jī)模型下沒有辦法進(jìn)行突破。

排序算法的突破：尋求更快速、更穩(wěn)定的排序算法。（基于比較的排序算法和非比較排序算法O(nlogn)、O(n)）

（1）國王獎勵有功的大臣：棋盤放麥子的問題。說明一個問題：計算復(fù)雜性問題，沒有知識是多么可怕啊。（2）網(wǎng)絡(luò)安全：其實也是一個計算復(fù)雜性問題。沒有絕對安全的網(wǎng)絡(luò)，從理論上可以證明構(gòu)建絕對安全的網(wǎng)絡(luò)是一個完全NP問題，無法達(dá)到，只能尋求某種情況下的最優(yōu)。（如果你不知道這些，會在上面浪費非常多的人力、無力，而沒有任何效果，不能無限制滿足甲方的不合理要求）3、美國計算機(jī)協(xié)會組織的ACM大賽。是目前為止，最受肯定的國際級別的比賽，主要專注的就是算法設(shè)計和編程。參賽者組成一個團(tuán)隊，以5個小時之內(nèi)完成的算法和編程完成情況排名。（這個賽事備受各個大公司獵頭的關(guān)注，親們可以組隊參加試試）4、跟大家畢業(yè)相關(guān)的算法介紹計算科學(xué)的算法實在是太多了，介紹幾個如下：（1）排序算法：要考慮需要進(jìn)行排序的數(shù)據(jù)的順序程度、數(shù)據(jù)取值的可能限制、數(shù)據(jù)所處于介質(zhì)如內(nèi)存、磁盤、磁帶等的情況。（2）倒排索引：搜索引擎中的算法；頁面關(guān)聯(lián)度分析算法等等；（3）海量數(shù)據(jù)中的查找算法；（4）圖形、圖像中的各種算法：高斯去噪；圖像分割、圖像內(nèi)容提取、圖像修復(fù)等等。（5）智能優(yōu)化算法（最多）。遺傳算法、蟻群算法、粒子群算法等等。用于解決那些無法找到確定性算法解決的問題，即NP問題。（這是我們畢業(yè)生做的最多的）（6）大數(shù)據(jù)中的數(shù)據(jù)挖掘、關(guān)聯(lián)度分析等等算法。（7）軟件保護(hù)中的加解密、水印算法等等。●20世紀(jì)30年代,人們的注意力是放在問題的可解與不可解的分類上,即是否存在有效過程來求解問題,為此產(chǎn)生了計算模型的概念.例如:遞歸函數(shù)、演算、POST機(jī)、

Turing機(jī).●

令人驚奇的是“幾乎所有”的問題都是不可解的。(請參考書上的說明，不做要求)●把問題的可判定性和可解性的研究領(lǐng)域稱為可計算性理論或計算理論。

1.2歷史背景●數(shù)字計算機(jī)出現(xiàn)后,對于可解問題研究的要求越來越多,由于有限的可用資源與開發(fā)復(fù)雜算法的要求,導(dǎo)致了在計算理論中出現(xiàn)了一個稱為計算復(fù)雜性的新領(lǐng)域?！裨诖祟I(lǐng)域，人們研究可解類問題的效率。

注意：自本節(jié)起，在搜索與排序的問題以及類似問題中，均假定元素取自線序集合(如整數(shù)集)。

●考慮這樣的問題：判定給定元素x是否在數(shù)組A[1…n]中。此問題可表述為：尋找索引j，1jn，如果x在A中，則有x=A[j]，否則j=0。1.3二分搜索

●解決該問題能夠想到的最簡單的方法：順序掃描法（線性搜索）：算法思想如下：掃描A中所有項，將每一項與x比較，如果在比較j次后(1jn)搜索成功，即x=A[j]，則返回j的值，否則返回0，表示沒有找到。算法1.1

LinearSearch偽碼描述：Input:數(shù)組A[1…n]、欲搜索元素x。Output:若x=A[j]且1jn,輸出j,否則輸出0。

1.j12.while(jn)and(xA[j])//處理循環(huán)

3.jj+14.endwhile5.ifx=A[j]thenreturnj

else

return0.

上述搜索算法在一般情況下是沒有問題的，但是在某些特殊情況下，如果仍然采用這種方法，是很愚蠢的處理方式。如果數(shù)據(jù)有序，我們就要考慮應(yīng)用數(shù)據(jù)之間的關(guān)系，來迅速定位待查找數(shù)據(jù)所處位置。●一般地，令A(yù)[low…h(huán)igh]為升序數(shù)組，A[mid]為其中間元素。1、如果x=A[mid]，則j=mid,結(jié)束;2、如果x>A[mid]，則x必定在A[mid+1...high]中,此時丟棄A[low…mid],只需在A[mid+1…h(huán)igh]中搜索x;3、如果x<A[mid]，則x必定在A[low…mid-1]中,此時丟棄A[mid…h(huán)igh],只需在A[low…mid-1]中搜索x。算法1.2BinarySearch算法偽碼：Input:n個元素的升序數(shù)組A[1…n]和元素x.Output:若x=A[j],1jn,輸出j,否則輸出0.1.low1;highn;j02.while(lowhigh)and(j=0)3.mid(low+high)/24.ifx=A[mid]thenjmid

//找到數(shù)據(jù)

5.else

ifxA[mid]thenhighmid-16.

elselowmid+17.endwhile8.returnj

顯然，由數(shù)據(jù)的搜索過程分析，可以把二分搜索算法的執(zhí)行描述為二元樹的搜索過程，又稱為：決策樹。

如下圖：其中黃色的節(jié)點是與待搜索元素ｘ進(jìn)行比較的數(shù)字。

10、23、15、22

1.3.1二分搜索算法分析1023152212514879322735顯然可以輕松得出結(jié)論：

數(shù)據(jù)X正好在數(shù)組的中間，算法1.2的比較次數(shù)是1，應(yīng)該是最少的。

（注意：不是0）下面重點分析普通情況的算法復(fù)雜性，即什么情況下搜索次數(shù)最多。推理如下：

(3)第k次迭代循環(huán)時剩余元素數(shù)目是n/2k-1，現(xiàn)在的停止條件是搜索數(shù)組為1或找到該元素x。也就是說最大的循環(huán)次數(shù)就是上述公式的滿足條件的k值。1=<n/2k-1<2則有k-1<=logn<kk=logn+1（1）第一次迭代A[mid+1..n]中剩余數(shù)據(jù)數(shù)目n/2或者是(n-1)/2，即n/2的下界：n/2；（包含了n是奇數(shù)或是偶數(shù)）(2)第二次迭代之后剩余的數(shù)據(jù)數(shù)目是n/2

/2=n/4；另外一種證明方法，決策樹明顯是一個二叉樹：一棵二叉樹的高度是logn比較次數(shù)就是logn+1。

定理1.1對于一個大小為n的排序數(shù)組，算法BINARYSEARCH執(zhí)行比較的最大次數(shù)為logn+1。得到如下結(jié)論：●假設(shè)有數(shù)組A[1…m],p,q,r為其三個索引，并且滿足：1pq<rm,兩子數(shù)組A[p…q]和A[q+1…r]各自按升序排列?，F(xiàn)重新安排A中元素的位置，使子數(shù)組A[p…r]也按升序排列。1.4合并兩個已排序的表●算法工作思路：設(shè)置一個空數(shù)組，用于暫時存放數(shù)據(jù)：B[p…r]。

指針s、t初始時分別指向A[p]和A[q+1]，每次比較元素A[s]和A[t],將小的元素添加進(jìn)數(shù)組B，即：1、如果A[s]A[t]，則A[s]添加進(jìn)B,并且s加1；2、如果A[s]A[t]，則A[t]添加進(jìn)B,并且t加1。3、當(dāng)至少有一個數(shù)組為空時(即s=q+1或t=r+1時),只要將非空數(shù)組的剩余元素添加進(jìn)B即可。4、最后,將數(shù)組B[p…r]復(fù)制回A[p…r]。算法1.3Merge偽代碼Input:A[1…m]和其三個索引p,q,r,1pqrm兩子數(shù)組A[p…q]和A[q+1…r]各自安升序排列.Output:合并A[p…q]和A[q+1…r]為數(shù)組A[p…r].1.Comment:B[p…r]是輔助數(shù)組.2.sp;tq+1;kp3.whilesqandtr

4.ifA[s]A[t]then5.B[k]A[s]6.ss+17.else8.B[k]A[t]

9.tt+110.endif11.kk+112.endwhile13.ifs=q+1then

//檢查哪個數(shù)組還沒有處理完

B[k…r]A[t…r]14.

elseB[k…r]A[s…q]

15.endif16.A[p…r]B[p…r]

//復(fù)制回去

下面分析排序數(shù)組A[p…r]中元素所需要的比較次數(shù)?！?/p>

必須強調(diào)的是：從現(xiàn)在起所說的算法執(zhí)行所需要的比較次數(shù)是指元素比較，即輸入數(shù)據(jù)中所含對象的比較。（非while循環(huán)）●設(shè)兩子數(shù)組A[p…q]和A[q+1…r]的大小分別為n1和n2,n1n2,并且n1+n2=n

。1、如果A[p…q]中的所有元素都比A[q+1…r]中的元素小，則需要比較n1次；(循環(huán)選擇A[p..q]中n1個元素依次與A[q+1..r]中的第一個元素進(jìn)行比較，故是n1次。)否則，全部元素之間都需要比較一遍，比較次數(shù)最多為n1+n2-1=n-1。

（最后一個元素肯定不用比較了，故-1）觀察結(jié)論1.1算法MERGE將兩個大小分別為n1和n2的非空數(shù)組合并成一個大小為n1+n2=n的排序數(shù)組，當(dāng)n1n2時,元素比較次數(shù)在n1到n-1之間。特別地，如果兩子數(shù)組大小為n/2和n/2，需要比較的次數(shù)在n/2到n-1之間?！裨鯓哟_定元素的賦值次數(shù)呢？觀察結(jié)論1.2

使用算法MERGE將兩個數(shù)組合并成一個大小為n的有序數(shù)組，元素賦值的次數(shù)恰好是2n。（向數(shù)組B中賦值n次，將B向A中賦值n次）問題描述：

令A(yù)[1…n]為一個有n個元素的數(shù)組，一種對A中元素進(jìn)行簡單、直接排序的算法如下。算法思想：1、首先找到最小的元素，將其放入A[1]中；2、然后在剩下的n-1個元素中找到最小的元素，將其放入A[2]中；3、重復(fù)此過程直到找到第二大元素,并將其放入A[n-1]中。1.5選擇排序算法1.4SelectionSortInput:n個元素的數(shù)組A[1…n]。

Output:按非降序排列的數(shù)組A[1…n]。

1.fori1ton-12.ki

//標(biāo)記當(dāng)前需要處理數(shù)據(jù)的位置

3.forji+1ton{查找第i小的元素}4.ifA[j]A[k]thenkj//保證k一直指向最小數(shù)

5.endfor6.ifkithen交換A[i]和A[k]

//賦值3次

7.endfor●算法(1.4SelectionSort)執(zhí)行的元素比較次數(shù)為：比較次數(shù)：i=1時，比較次數(shù)是:n-1;i=2時，比較次數(shù)是：n-2;依次類推：i=n時，比較次數(shù)應(yīng)該是n-n+1=1.

故總比較次數(shù)是：

(n-1)+(n-2)+…+2+1=n(n-1)/2

根據(jù)程序可以得到：程序由于采用的是標(biāo)記交換位置下標(biāo)的做法，故交換次數(shù)是0...n-1。

每次交換需要3次元素賦值，故元素賦值次數(shù)界于0與3(n-1)之間。//(A[k]<->A[i])觀察結(jié)論1.3

執(zhí)行算法SelectionSort所需的元素比較次數(shù)為n(n-1)/2，元素賦值次數(shù)界于0與3(n-1)之間。1.6插入排序●插入排序的基本思想：（將待排數(shù)據(jù)插入到已經(jīng)有序的數(shù)組中的適當(dāng)位置）1、從下標(biāo)為1的子數(shù)組A[1]開始,其自然已排好序；2、將A[2]插入到A[1]的前面或者后面,如果A[2]<A[1]，插入到A[1]前面，否則插入到后面；3、繼續(xù)這一過程，在第i次執(zhí)行中,要將A[i]插入到已排好序的A[1…i-1]中適當(dāng)位置；4、重復(fù)以上過程，直到所有元素都插入到數(shù)組中。算法1.5INSERTIONSORT

Input:n個元素的數(shù)組A[1…n]。Output:按非降序排列的數(shù)組A[1…n]。

1.fori2ton

//從第2個元素開始進(jìn)行

2.xA[i]

//取出該數(shù)據(jù),賦值操作

3.ji-1

//跟前面的數(shù)據(jù)開始比較

4.While(j>0)and(A[j]>x)//注意條件，比較的依據(jù)，A[j]>x就是比較。

5.A[j+1]A[j]

//將數(shù)據(jù)后移給x騰地，賦值

6.jj-1

//依次遞減，直至最小處

7.endwhile8.A[j+1]x

//將X放在合適的位置上，賦值操作

9.endfor●算法INSERTIONSORT分析1、輸入序列已按非降序排列時，元素比較次數(shù)是：n-1，（每一個元素A[i](2in)只和A[i-1]比較）；（A[j]>x進(jìn)行比較）2、輸入序列按照降序排列且所有元素均不相同時,元素的比較次數(shù)最大,最大次數(shù)為。

1+2+…+(i-1)+…+(n-1)=n(n-1)/2。（解釋：i=2時，前面有1個元素，故是1；i=3時，前面有2個元素，故是2；i=j時，前面是j-1個元素，故是j-1；i=n時，前面是n-1個元素，故比較n-1次）觀察結(jié)論1.1

執(zhí)行算法InsertionSort的元素比較次數(shù)在n-1到n(n-1)/2之間。

元素賦值次數(shù)等于元素比較次數(shù)加上n-1（賦值次數(shù)的處理是錯誤的）。（分析錯誤：內(nèi)循環(huán)比較1次就賦值1次，數(shù)據(jù)后移時候的賦值；外循環(huán)2到n的循環(huán)共n-2+1=n-1次賦值）

應(yīng)該分開討論賦值操作次數(shù)的問題，討論如下：

1、當(dāng)數(shù)組已經(jīng)排好順序時，內(nèi)循環(huán)只比較，不進(jìn)行任何數(shù)據(jù)的賦值，內(nèi)循環(huán)賦值次數(shù)為0。外循環(huán)賦值次數(shù)2*(n-1)。2、當(dāng)數(shù)組逆序時，每比較一次，內(nèi)循環(huán)賦值一次，故內(nèi)循環(huán)的賦值次數(shù)是：

1+2+…+n-1=n(n-1)/2總的比較次數(shù)是：n(n-1)/2+2*(n-1)3、雜亂無章時，內(nèi)循環(huán)比較次數(shù)與賦值次數(shù)沒有任何關(guān)系，無法確定內(nèi)循環(huán)的賦值次數(shù)。假設(shè)為m，則0≤m≤n(n-1)/2，為m+2*(n-1).修改的插入排序算法1.fori2ton

//從第2個元素開始進(jìn)行

2.xA[i]

//取出該數(shù)據(jù),賦值操作

3.ji-1

//跟前面的數(shù)據(jù)開始比較

4.While(j>0)and(A[j]>x)//注意條件，比較的依據(jù)，A[j]>x就是比較。

5.A[j+1]A[j]

//將數(shù)據(jù)后移給x騰地，賦值

6.jj-1

//依次遞減，直至最小處

7.endwhile8.if((j+1)<>i)9.A[j+1]x

//將X放在合適的位置上，賦值操作

10.endfor//減少外層循環(huán)的賦值次數(shù)，尤其對于已經(jīng)排好序的情況1.7自底向上合并排序上述算法的比較次數(shù)均是n2級別。數(shù)據(jù)結(jié)構(gòu)中“樹”的的計算復(fù)雜性要明顯較線性表低，所以我們考慮下面通過樹的方式來構(gòu)造排序。減少數(shù)據(jù)之間的比較次數(shù)。例如：排序如下數(shù)據(jù)序列：945217461234567892459146749251746945217461.7自底向上合并排序令A(yù)為待排序的n個元素的數(shù)組。算法基本思想：1、將數(shù)組分解為n個數(shù)組，每一個數(shù)組只有一個元素，兩兩組合進(jìn)行排序；生成目標(biāo)：大小為2的n/2個排序序列數(shù)組；

特例：n不是2的整數(shù)倍，則剩余一個元素,不做任何處理直接進(jìn)入下一輪迭代。2、對由第一步生成的排序完成的數(shù)組，進(jìn)行兩兩合并排序；目標(biāo)：生成n/4個長度為4的排序序列；特例：a、剩余一組2元素排序數(shù)組或1個元素，則直接進(jìn)入下一輪迭代；b、剩余三個元素（即一組2元素數(shù)組和一個一元素數(shù)組），則將它們進(jìn)行排序合并生成一個3元素數(shù)組。3、繼續(xù)這一過程…，在第j次迭代中,生成n/2j個大小為2j的排序序列.直至完成全部排序為止。剩余元素：如有k個剩余元素,1k2j-1，則將它們放在下一次合并中，如有k個剩余元素,2j-1<k<2j,則將它們合并,形成一個大小為k的排序序列。（注意：兩兩合并操作，所以第i次合并操作得到的數(shù)組長度應(yīng)該是：2i-1,

如果剩余的元素數(shù)目正好小于或等于這個數(shù)，肯定是單獨一組數(shù)據(jù)；

如果大于這個數(shù)據(jù)，肯定是存在兩組單獨的數(shù)據(jù)，所以肯定要進(jìn)行合并操作。）算法1.6BOTTOMUPSORTInput:n個元素的數(shù)組A[1…n]。Output:按非降序排列的數(shù)組A[1…n]。1.t12.whiletn//注意循環(huán)次數(shù)，樹的高度logn次3.st;t2s;i0;//因為每次合并都是2個數(shù)組所以t被乘以2，t//s是被合并數(shù)組的長度4.whilei+tn5.MERGE(A,i+1,i+s,i+t)//合并兩個已排序表，紅色標(biāo)識合并數(shù)組的邊界

6.ii+t；//t是原始數(shù)的2倍，兩兩合并，故通過此公式向后推動i值，確定前一個合并數(shù)組的后邊界值

7.endwhile8.ifi+s<nthenMERGE(A,i+1,i+s,n)//用于處理多余的剩余元素合并，如果n是2的整數(shù)冪，則不被執(zhí)行

9.endwhile●算法中的變量說明1、s存儲被合并序列的大小,開始將s置初值1，每次執(zhí)行外面的While循環(huán)時被乘以2。2、i+1,i+s,i+t

用來定義兩個要排序的序列的邊界。3、當(dāng)n不是t的倍數(shù)時,執(zhí)行第8步;在這種情況下,如果剩余元素數(shù)目(即n-i)大于s，就要在大小為s的序列和剩余元素之間在進(jìn)行一次排序。

假設(shè)n為2的倍數(shù)，則不再需要執(zhí)行第八步，即不會有多余的數(shù)據(jù)序列遺留。（1）算法迭代次數(shù)是樹的高度number=logn;(2)第i次迭代過程中，應(yīng)該具有n/2i-1個數(shù)據(jù)序列，每個數(shù)據(jù)序列長度是2i-1。（因為是按照每層都是2對數(shù)據(jù)序列合并）

（3）根據(jù)觀察結(jié)論1.1可知，每次迭代過程中，每兩對數(shù)據(jù)序列的比較次數(shù)應(yīng)該是n1到n1+n2-1====》2i-1到2i-1。故第i次全部的元素的比較次數(shù)應(yīng)該是(n/2j)*2i-1到(n/2j)*2i-1。設(shè)k=logn，則最小比較次數(shù)是最大比較次數(shù)是：nlogn-n+1●例1.3

自底向上合并排序舉例（參見課本）●算法執(zhí)行的元素比較次數(shù)分析●元素賦值的次數(shù):由觀察結(jié)論1.2可知：在每一次合并操作時,外部while循環(huán)每執(zhí)行一次要進(jìn)行2n次元素賦值，一共進(jìn)行2nlogn次賦值。（logn是樹的高度，迭代次數(shù)）（為什么是2n次：合并操作中：兩個n的數(shù)組，先賦值到B，然后拷貝回A，故賦值次數(shù)是2n）。觀察結(jié)論1.5

用算法BOTTOMUPSORT對n個元素的數(shù)組進(jìn)行排序，當(dāng)n為2的冪時，元素比較次數(shù)在(nlogn)/2到nlogn-n+1之間。執(zhí)行該算法的元素賦值次數(shù)為2nlogn。1.8時間復(fù)雜性●

算法運行時間與空間的確定問題是算法分析的一個基本組成部分，稱為計算復(fù)雜性問題。研究的主要目的是：

當(dāng)給出合法輸入時，為了得到輸出，確定該算法運行所需的時間與空間。

例子：觀察：自底向上排序算法最大比較次數(shù)：nlogn-n+1，選擇排序比較次數(shù)是n(n-1)/2。假設(shè)每一次的元素比較時間是10e-6秒，我們設(shè)置一個128的數(shù)組進(jìn)行排序，則兩個算法分別是8e-4秒和0.008秒。換做另外一個數(shù)組1048576,則經(jīng)過計算前者是20秒，后者則是6.4天。（所以我們在設(shè)計算法時更應(yīng)該關(guān)注時間）

顯而易見，說一個算法A對于輸入x要用y秒運行是沒有意義的。所以我們更應(yīng)該關(guān)注的是給一個算法的最通常的衡量標(biāo)準(zhǔn)。1.在什么機(jī)器上和怎樣執(zhí)行的。2.用的是什么樣的編程語言。3.編譯器和程序員的能力如何?；谏鲜鲈蛭覀儾⒉恍枰贸鏊惴ǖ拇_切時間1.8.1階的增長影響程序的運行時間的要素：1.與其它算法比較運行時間，估計的時間是相對的而不是絕對;2.其次，一個算法要獨立于機(jī)器，才能夠衡量性能；3.再者，它還應(yīng)該是技術(shù)獨立的，也就是說，無論科技如何進(jìn)步，我們對算法運行時間的測度始終成立；4.第四，最關(guān)心的是在大數(shù)據(jù)量輸入時，算法的運行情況?！裎覀兩踔烈膊⒉恍枰贸鏊惴ǖ慕茣r間，●事實上，要精確計算所有的運算次數(shù)，如果不是不可能的話，也是非常麻煩的。由于只對大數(shù)據(jù)量輸入運行時間感興趣，所以可利用討論運行時間的增長率或增長的階的方法來度量算法的效率。見圖1.5

顯然n3增長率更快，而logn的增長率要低很多。n3>n2>nlogn>n>lognf(n)=30n3+10;f(n)=100n3+50n+1顯然隨著n的增大，兩個函數(shù)趨于相同.(漸進(jìn))所以：常數(shù)在函數(shù)中影響就較小?！?/p>

表1.1是時間復(fù)雜性分別為logn,n,nlogn,n2,n3,2n的算法的近似運行時間。

●一旦去除了表示算法運行時間的函數(shù)中低階項和常數(shù)，我們就稱是在度量算法的漸近運行時間(Asymptoticrunningtime)。在算法分析中,用“時間復(fù)雜性”來表示漸進(jìn)時間。定義1.1

對任一計算步驟,如果它的代價總是以一個時間常量為上界,而不論輸入數(shù)據(jù)或執(zhí)行的算法,我們稱該計算步驟為“元運算”。●常見的元運算舉例：1.算術(shù)運算，包括加、減、乘和除；2.比較和邏輯運算；3.賦值運算，包括遍歷表或樹的指針賦值?！裣旅娼o出表示算法復(fù)雜性的幾個符號。元運算

由于考慮的是漸進(jìn)曲線，所以對于元運算的可以任意選擇一個整數(shù)作為其系數(shù)。1.8.2符號●

INSERTIONSORT執(zhí)行的比較次數(shù)（元運算）次數(shù)是(n2-n)/2,是n2階的，故選擇k為某個適當(dāng)選擇的正常數(shù)。則其運算次數(shù)比較最多是kn2即：算法的運行時間是(n2)。●可作如下解釋:只要當(dāng)排序元素的個數(shù)等于或超過某個閾值n0時，那么對于某個常量k>0，運行時間至多為kn2。（強調(diào)：數(shù)據(jù)量較大）

注意：數(shù)據(jù)量很大時，也不能說運行時間總是恰好為kn2。這樣,符號提供了一個運行時間的上界,它一般不是算法的實際運行時間。給出符號的數(shù)學(xué)定義：定義1.2

令f(n)和g(n)是自然數(shù)集到非負(fù)實數(shù)集的兩個函數(shù)，如果存在一個自然數(shù)n0和一個常數(shù)c>0,使得nn0時f(n)cg(n),則稱f(n)為(g(n))。因此，如果limnf(n)/g(n)存在，那么

limnf(n)/g(n)=》f(n)=O(g(n))?！穸x1.2說明f(n)不比g(n)的某個常數(shù)倍增長得更快;符號給出了算法運行時間的一個上界?！?/p>

eg.f(n)=5n3+7n2-2n+13,可以寫成:

f(n)=5n3+(n2).這樣表示對于低階項不感興趣。1.8.3符號●(讀作“大omega”)符號在運行時間的一個常數(shù)因子內(nèi)提供一個下界。●例如算法INSERTIONSORT的運行時間是(n)。自底向上算法運算時間是(nlogn)●可解釋為：無論何時，當(dāng)被排序的元素個數(shù)等于或超過某一個閾值n0時，那么對某個常數(shù)c>0，運行時間至少是n的c倍。自底向上的運行時間至少是nlogn的c倍?！穹栆脖粡V泛用于表示問題的下界，換句話說,它通常用來表示解決某一問題的算法的下界（最小運行時間）。符號的定義：定義1.3令f(n)和g(n)是自然數(shù)集到非負(fù)實數(shù)集的兩個函數(shù),如果存在一個自然數(shù)n0和一個常數(shù)c>0,使得nn0,f(n)cg(n)則稱f(n)為(g(n))。因此，如果limnf(n)/g(n)存在，那么limnf(n)/g(n)0蘊含著f(n)=(g(n))。(也就是說：f(n)至少不比g(n)的某個倍數(shù)增長慢，起碼是一樣快的)●從定義1.2與1.3可以看出：

f(n)為(g(n))當(dāng)且僅當(dāng)g(n)為(f(n))。(即：f(n)是g(n)的上界，則g(n)就是f(n)的下界)

就像足球一樣，中韓足球的成績。沖出亞洲的過程中，我們現(xiàn)在找不到一個增長速率能夠超越韓國足球的增長速率。（為什么不說巴西、阿根廷、荷蘭、西班牙呢，因為那不是緊挨著的上界，注意區(qū)分）“你問我中國足球何時得第一，別嚇著上帝。”--《青花瓷-國足》更深的理解：

如果一個算法的最小運算復(fù)雜度是(g(n))，則認(rèn)為基于該算法的核心思路（比較、選擇）無法設(shè)計出漸進(jìn)復(fù)雜性小于g(n)的程序。1.8.4符號●

選擇排序算法比較次數(shù)是n(n-1)/2（沒有最少和最多），所以該算法執(zhí)行元運算次數(shù)總是和n2成正比，由于每一個元運算需要一個常量時間，我們說算法SELECTIONSORT的運行時間(n2)(讀做“thetan平方”)。

●

可做如下解釋：

●這一符號是表示算法的精確階的，它蘊含算法的運行時間有確切界限。

存在常數(shù)c1和c2，在n≥n0的任何大小的輸入情況下：

c1n2<=runtime<=c2n2。表明，對于任意正整數(shù)n,算法SELECTIONSORT的運行時間為(n2)。符號的定義定義1.4：令f(n)和g(n)是自然數(shù)集到非負(fù)實數(shù)集的兩個函數(shù)，如果存在一個自然數(shù)n0和兩個正常數(shù)c1和c2,使得nn0時,c1g(n)f(n)c2g(n),則稱f(n)為(g(n))的。因此如果limnf(n)/g(n)存在，那么limnf(n)/g(n)=c(其中c必須是一個大于0的常數(shù))蘊含著f(n)=(g(n))?！衽c前兩個不同，

符號給出了算法運行時間增長率的一個精確描述；可以認(rèn)為，類似于,類似于，而類似于?！穸x1.4的一個重要推論是:f(n)=(g(n))當(dāng)且僅當(dāng)f(n)=(g(n))并且f(n)=(g(n))。例如：雖然100nn，但100n=(n)(上界)；雖然n100n，但n=(100n)（下界）；雖然n100n，但是n=(100n)

（確切值）。eg1.f(n)=10n2+20n；n>=1時，f(n)<=30n2故算法的上界是O(n2);n>=1時，f(n)>=n2,故算法的下界是(n2)；n>=1時，n2<=f(n)<=30n2,故精確時間是（n2）。eg2.f(n)=ank+a'nk-1+......+a1n+a0

則考慮最高的項目階的漸進(jìn)變化，則應(yīng)該有f(n)=(nk)；（最大運算時間）f(n)=(nk)(最小運算時間)f(n)=(nk)（精確運算時間）

eg3.f(n)=logn2求極限limf(n)/n=0，故f(n)=(n)，但不是（n）和（n）。eg4.f(n)=logn2

logn2=2logn,也就是說

前者和后者的變化速度是一樣快的，所以有l(wèi)ogn2=（logn）。對于固定常數(shù)k有l(wèi)ognk=（logn）.eg5.常數(shù)函數(shù)的特殊之處

(1)、（1）、（1）。1.9空間復(fù)雜性●算法使用的空間定義：算法工作所需要的空間。它不包括用來存儲輸入的空間（輸入緩沖區(qū)）。●算法的占用內(nèi)存空間與其運算是相互協(xié)調(diào)的，寫入每一個內(nèi)存單元都至少需要一定的時間。所以算法的空間復(fù)雜性不可能超過時間復(fù)雜性這樣，有S(n)=(T(n))。（即：（T是該算法的上界））eg1.線性搜索、二分查找、選擇排序、插入排序

(1);//只需要增加一個暫存單元eg2.合并兩個數(shù)組算法中只增加了一個數(shù)組B（大小為n），則為(n)；eg3.自底向上的排序算法主要考慮的是中間進(jìn)行合并時的數(shù)組大小，鑒于初始排序的數(shù)組大小是n，則B的最大長度應(yīng)該是n。故是(n).eg4.組合n長度的字符，形成字符串，并輸出。

因為不需要保存，設(shè)置一個最長的n數(shù)組即可，明顯是(n)。

如果還要保存用于后期的處理，則成了n*n!=（(n+1)!）?！窀拍睿?/p>

如果任何一個求解問題的算法必定是(f(n))，那么我們把在(f(n))時間內(nèi)求解問題的任何算法都稱為問題的最優(yōu)算法。1.10最優(yōu)算法例如：在12.3.2節(jié)將證明:對于大小為n的數(shù)組而言,任何用元素比較的方法進(jìn)行數(shù)據(jù)排序的算法，其運行時間在最壞情況下必定是(nlogn)的。

不能期望任一個算法在最壞情況下的漸進(jìn)運行時間少于nlogn。因此把在O(nlogn)時間內(nèi)用元素比較法排序的任何算法稱為基于比較的排序問題的最優(yōu)算法?！耥槺阒赋?，在最優(yōu)算法的定義中沒有考慮空間復(fù)雜性，其原因有兩點：1.首先是因為時間比空間寶貴的多，只要算法使用的空間在一個合理的范圍內(nèi)即不予考慮。2.其次，大多數(shù)已有的最優(yōu)算法，在相互比較它們的空間復(fù)雜性時，往往是同處于(n)階內(nèi)的。1.11如何估計算法運行時間●背景：

1、對于元運算，全部進(jìn)行相加可以得到精確解；（現(xiàn)實是不可取的）2、不存在一個固定的過程或計算方法得到算法的時間和空間；3、計算時間需要直覺和機(jī)智。

通過如下的一些技術(shù)可以實現(xiàn)估算運行時間：

(1)計算迭代次數(shù)；(2)計算元運算的頻度；(3)使用遞推技術(shù)●在相關(guān)的較多算法中（搜索、排序、矩陣處理）包含較多的是循環(huán)或類似結(jié)構(gòu)，而運算時間與其密切相關(guān)。eg1.count1//假設(shè)n=2k1.count=0;//count用于計算迭代次數(shù)；2.whilen>=1//執(zhí)行k+1次，k=logn；forj=1ton//執(zhí)行n次，n/2，n/4，.......1次；count=count+1//endforn=n/2；

endwhilereturncount1.11.1計算迭代次數(shù)eg2.輸入正整數(shù)n(記住結(jié)論，這個例子和1.15和2.16有關(guān))count=0;//計算元運算的迭代次數(shù)fori=1tonm=

forj=1tom//循環(huán)執(zhí)行依次為：n,n/2,n/3,.......n/n（均為下界）5.count=count+1//endforendforreturncount第5步故得出結(jié)論該步驟執(zhí)行了（nlogn）次，整個算法運行時間是（nlogn）。eg3.如下程序//輸入n=22k

count=0;fori=1tonj=2;whilej<=n//j=2，4,16,........,22k循環(huán)得到執(zhí)行。j=j*j;count=count+1;endwhileendforreturncount//對于for循環(huán)講，每一個while循環(huán)執(zhí)行k+1次，即loglogn+1。則while的總執(zhí)行次數(shù)是n(k+1)=n(loglogn+1)次。

運算時間是

(n(loglogn+1)）。2、計算基本運算的頻度：

對于某些算法精確估算運行次數(shù)幾乎是不可能的。單源最短路徑、尋找最小生成樹prim算法、深度優(yōu)先搜索、計算凸包等（后續(xù)待講）?？梢蕴暨x一個元運算，其運行頻率在所有的運算中是最大的，即包含了其它的元運算。

定義1.6如果算法中一個元運算具有最高的頻度，所有其他元運算的頻度均在它的頻度的常數(shù)倍內(nèi)，則稱這個元運算為基本運算。例如：兩個有序數(shù)組（長度都是n）的合并運算。元素的賦值運算包含兩部分，也是該算法中最有頻度的運算（包含了比較運算）。2n次賦值運算。故時間復(fù)雜度是(n)。

3.在遍歷一個鏈表時，可以選擇設(shè)置或更新指針的運算為基本運算；2.在矩陣乘法算法中,可選數(shù)量乘法為基本運算；4.在圖的遍歷中，可以選訪問節(jié)點的“動作”和對被訪問節(jié)點的計數(shù)為基本運算。●然而，在選擇基本運算時，有一點要注意。請看下面的例子：

●在問題中的幾種常見基本運算：1.在搜索和排序算法中,若元素比較是元運算,則可選為基本運算；例1.自底向上排序法的分析：（1）基本運算來自merge算法，選擇元素比較作為元運算的基本運算。（2）算法的比較總次數(shù)是(nlogn)/2和nlogn-n+1（n是2的倍數(shù)）。（3）此時比較次數(shù)的上界和下屆均為nlogn次，則其精確運算次數(shù)也是nlogn。（4）當(dāng)n不是2的倍數(shù)時，由于每一次只是增加了一個merge運算，而其也是nlogn級別的，故上述第三步的結(jié)論仍然成立。（５）依據(jù)上述可以得出結(jié)論運算時間與數(shù)據(jù)比較次數(shù)成正比，故運算時間是(nlogn)。例2、見如下程序修改的插入排序

fori=2tonx=a[i];

k=modbinarysearch(a[1..i-1]),x)

//修改的二分搜索，確定待插入位置forj=i-1downtok//找到待插入位置后，后移數(shù)據(jù)；a[j+1]=a[j]endfora[k]=x;endfor

分析：確定運算最多的元是：k=.......，被調(diào)用n-1次，根據(jù)二分搜索的比較次數(shù)計算最大是[log(i-1)]+1（定理1.1），故其總次數(shù)是n-1次的和=(nlogn)(很有誘惑力的結(jié)論)

但是實際上該算法應(yīng)該是O(n2)。該算法和插入排序算法的賦值次數(shù)完全一樣。

錯誤在于：將基于元素比較作為基本運算，而實際應(yīng)該是元素的移動。

另外注意：在一些算法中，所有的元運算都不是基本運算。它可能是這樣的情況：兩種或者更多的運算結(jié)合在一起的頻度與算法的運行時間成正比，在此情況下，用執(zhí)行這些運算的總次數(shù)的函數(shù)來表示運行時間。eg3.實現(xiàn)數(shù)組中前k個整數(shù)相乘，后面的相加prod=1;sum=0;forj=1tokprod=prod*a[j];endforforj=k+1tonsum=sum+1；endfor

分析：沒有基本的元運算；runtime正比于（time(加)+time(乘)）；即：存在n個元運算（加+乘）；故界是（n）；通過循環(huán)次數(shù)確定時間，循環(huán)總次數(shù)是k+(n-k)=n次?！褚粋€計算運行時間的函數(shù)常常以遞推關(guān)系的形式給出，即函數(shù)的定義之中包含了函數(shù)本身。例如在算法BINARYSEARCH中，令C(n)為大小為n的實例中執(zhí)行的次數(shù)，則有遞推關(guān)系：

當(dāng)n=1時,C(n)=1;

當(dāng)n2時,C(n)C(n/2)+1.于是，C(n)C(n/2)+1=C(n/2/2)+1+1=C(n/4)+1+1=…=logn+1因此，C(n)logn+1，故C(n)=(logn),即算法BINARYSEARCH的時間復(fù)雜性為(logn)。1.11.3使用遞推關(guān)系1.12最壞情況和最好情況的分析

1、考慮兩個nn的整數(shù)矩陣A和B的相加問題。

運行時間與輸入值無關(guān)只與維度有關(guān)2、SELECTIONSORT算法（選擇排序）

算法的運行時間與輸入的值無關(guān)。3、插入排序INSERTIONSORT，自底向上排序等等。運行時間在很大程度上與輸入值有關(guān)。這表明算法不僅是輸入n的函數(shù)，也是輸入元素初始順序的函數(shù)，算法運行時間不僅依賴于輸入數(shù)據(jù)的個數(shù)，還依賴于它的形式，

我們一般情況下很難找到一個與輸入大小和形式都相關(guān)的描述算法時間復(fù)雜性的函數(shù)，后一因素往往只能被忽略。見課本圖1.6所示，對于插入排序，不同的排列次序，其時間復(fù)雜度是不同的。如果已經(jīng)按升序排好：是n;隨機(jī)安排：n2/4；降序排列：n2/2例如:

插入排序：對于一個數(shù)據(jù)輸入序列n，最壞復(fù)雜度的上界與下界均是n2階的，所以使用（n2）表示。表達(dá)算法在最壞情況下的確切性能。1、最壞情況下是（f(n)），蘊含了最壞情況下(f(n)).2、最壞情況下是O(f(n))，則無法推知下界是否是(f(n))。

1.12.1最壞情況分析

3、最壞情況下說以確切的(f(n))，要比使用上界O(f(n))強，更易理解；例子：線性搜索linesearch一般情況下是O(n)(上界)和（1）