算法設計技巧與分析

信工學院軟件與理論教研室

王培崇

2014年9月

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

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

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

1.1引言

在計算機科學領域，算法設計與分析是十分重要的。D.E.Knuth說：“計算機科學就是算法的研究”。

算法的規則須滿足特點:

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

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

a、CTO（首席架構師）

b、需求分析師：負責跟甲方溝通；

c、系統設計師+核心算法設計小組人員。

d、項目經理

e、編碼人員（這個階層人數最多）

f、測試小組；

g、質量管理人員。

微軟高薪挖角：挖掉了borland

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

DNA中基因對序列排隊也會涉及復雜的算法。網絡數據傳輸中的路由選擇算法。（QQ、微信中的信息傳輸）

自動化軟件測試中的路徑測試用例自動生成技術。該問題也是一個復雜性相當強的問題，會產生組合爆炸。圍棋軟件、象棋軟件等等（我們身邊的：查詢你自己的通話記錄，有優秀算法的存在嗎？數據庫：優化、索引）科學研究中的算法1、圖靈獎的獲得者絕大部分是做算法的研究的；姚期智：受聘于清華大學計算機系，唯一的一個圖靈獎華裔獲得者。2、尋求計算方面的突破。可計算性理論與計算復雜性理論等等。

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

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

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

Turing機.●

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

1.2歷史背景●數字計算機出現后,對于可解問題研究的要求越來越多,由于有限的可用資源與開發復雜算法的要求,導致了在計算理論中出現了一個稱為計算復雜性的新領域。●在此領域，人們研究可解類問題的效率。

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

●考慮這樣的問題：判定給定元素x是否在數組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:數組A[1…n]、欲搜索元素x。Output:若x=A[j]且1jn,輸出j,否則輸出0。

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

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

else

return0.

上述搜索算法在一般情況下是沒有問題的，但是在某些特殊情況下，如果仍然采用這種方法，是很愚蠢的處理方式。如果數據有序，我們就要考慮應用數據之間的關系，來迅速定位待查找數據所處位置。●一般地，令A[low…high]為升序數組，A[mid]為其中間元素。1、如果x=A[mid]，則j=mid,結束;2、如果x>A[mid]，則x必定在A[mid+1...high]中,此時丟棄A[low…mid],只需在A[mid+1…high]中搜索x;3、如果x<A[mid]，則x必定在A[low…mid-1]中,此時丟棄A[mid…high],只需在A[low…mid-1]中搜索x。算法1.2BinarySearch算法偽碼：Input:n個元素的升序數組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

//找到數據

5.else

ifxA[mid]thenhighmid-16.

elselowmid+17.endwhile8.returnj

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

如下圖：其中黃色的節點是與待搜索元素ｘ進行比較的數字。

10、23、15、22

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

數據X正好在數組的中間，算法1.2的比較次數是1，應該是最少的。

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

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

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

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

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

//檢查哪個數組還沒有處理完

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

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

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

//復制回去

下面分析排序數組A[p…r]中元素所需要的比較次數。●

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

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

（最后一個元素肯定不用比較了，故-1）觀察結論1.1算法MERGE將兩個大小分別為n1和n2的非空數組合并成一個大小為n1+n2=n的排序數組，當n1n2時,元素比較次數在n1到n-1之間。特別地，如果兩子數組大小為n/2和n/2，需要比較的次數在n/2到n-1之間。●怎樣確定元素的賦值次數呢？觀察結論1.2

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

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

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

1.fori1ton-12.ki

//標記當前需要處理數據的位置

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

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

//賦值3次

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

故總比較次數是：

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

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

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

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

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

1.fori2ton

//從第2個元素開始進行

2.xA[i]

//取出該數據,賦值操作

3.ji-1

//跟前面的數據開始比較

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

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

//將數據后移給x騰地，賦值

6.jj-1

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

7.endwhile8.A[j+1]x

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

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

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次）觀察結論1.1

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

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

應該分開討論賦值操作次數的問題，討論如下：

1、當數組已經排好順序時，內循環只比較，不進行任何數據的賦值，內循環賦值次數為0。外循環賦值次數2*(n-1)。2、當數組逆序時，每比較一次，內循環賦值一次，故內循環的賦值次數是：

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

//從第2個元素開始進行

2.xA[i]

//取出該數據,賦值操作

3.ji-1

//跟前面的數據開始比較

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

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

//將數據后移給x騰地，賦值

6.jj-1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

顯而易見，說一個算法A對于輸入x要用y秒運行是沒有意義的。所以我們更應該關注的是給一個算法的最通常的衡量標準。1.在什么機器上和怎樣執行的。2.用的是什么樣的編程語言。3.編譯器和程序員的能力如何。基于上述原因我們并不需要得出算法的確切時間1.8.1階的增長影響程序的運行時間的要素：1.與其它算法比較運行時間，估計的時間是相對的而不是絕對;2.其次，一個算法要獨立于機器，才能夠衡量性能；3.再者，它還應該是技術獨立的，也就是說，無論科技如何進步，我們對算法運行時間的測度始終成立；4.第四，最關心的是在大數據量輸入時，算法的運行情況。●我們甚至也并不需要得出算法的近似時間，●事實上，要精確計算所有的運算次數，如果不是不可能的話，也是非常麻煩的。由于只對大數據量輸入運行時間感興趣，所以可利用討論運行時間的增長率或增長的階的方法來度量算法的效率。見圖1.5

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

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

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

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

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

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

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

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

limnf(n)/g(n)=》f(n)=O(g(n))。●定義1.2說明f(n)不比g(n)的某個常數倍增長得更快;符號給出了算法運行時間的一個上界。●

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

f(n)=5n3+(n2).這樣表示對于低階項不感興趣。1.8.3符號●(讀作“大omega”)符號在運行時間的一個常數因子內提供一個下界。●例如算法INSERTIONSORT的運行時間是(n)。自底向上算法運算時間是(nlogn)●可解釋為：無論何時，當被排序的元素個數等于或超過某一個閾值n0時，那么對某個常數c>0，運行時間至少是n的c倍。自底向上的運行時間至少是nlogn的c倍。●符號也被廣泛用于表示問題的下界，換句話說,它通常用來表示解決某一問題的算法的下界（最小運行時間）。符號的定義：定義1.3令f(n)和g(n)是自然數集到非負實數集的兩個函數,如果存在一個自然數n0和一個常數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)的某個倍數增長慢，起碼是一樣快的)●從定義1.2與1.3可以看出：

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

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

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

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

●

可做如下解釋：

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

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

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

符號給出了算法運行時間增長率的一個精確描述；可以認為，類似于,類似于，而類似于。●定義1.4的一個重要推論是:f(n)=(g(n))當且僅當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

則考慮最高的項目階的漸進變化，則應該有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,也就是說

前者和后者的變化速度是一樣快的，所以有logn2=（logn）。對于固定常數k有lognk=（logn）.eg5.常數函數的特殊之處

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

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

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

如果還要保存用于后期的處理，則成了n*n!=（(n+1)!）。●概念：

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

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

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

通過如下的一些技術可以實現估算運行時間：

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

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

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

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

運算時間是

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

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

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

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

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

fori=2tonx=a[i];

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

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

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

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

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

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

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

當n=1時,C(n)=1;

當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的時間復雜性為(logn)。1.11.3使用遞推關系1.12最壞情況和最好情況的分析

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

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

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

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

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

1.12.1最壞情況分析

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