程序性能分析

1、7月-221第二章程序性能分析2.1概述2.2空間復雜度2.3時間復雜度2.4漸進符號7月-222第二章程序性能分析本章所介紹的程序性能分析和測量的概念涉及以下內(nèi)容：確定一個程序?qū)?nèi)存及時間的需求使用操作計數(shù)和執(zhí)行步數(shù)來測量一個程序的時間需求。使用漸進符號來描述復雜性 (O、o)利用計時函數(shù)測量一個程序的實際運行時間。7月-223排序的基本概念排序的定義簡單定義：排序是按照關(guān)鍵字的非遞減或非遞增順序?qū)σ唤M記錄重新進行整隊（或排列）的操作。數(shù)學定義：假設(shè)含有n個記錄的序列為： r1, r2, ,rn (a-1)它們的關(guān)鍵字相應為k1, k2, ,kn,對式(a-1)的記錄序列進行排序就是要確定序

2、號1,2, ,n的一種排列p1, p2,pn使其相應的關(guān)鍵字滿足如下的非遞減(增)關(guān)系： kp1 kp2 kpn (a-2)也就是使式(a-2)的記錄序列重新排列成一個按關(guān)鍵字有序的序列 rp1 rp2 rpn (a-3)7月-224排序的基本概念排序的目的是什么？便于查找排序算法的好壞如何衡量？時間效率排序速度（即排序所花費的全部比較次數(shù)）空間效率占內(nèi)存輔助空間的大小穩(wěn)定性若兩個記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。7月-225排序的基本概念排序的特性穩(wěn)定性與不穩(wěn)定性當待排記錄中的關(guān)鍵字ki(1,2,n)都不相同時，則任何一個記錄的無序序列經(jīng)排

3、序后得到的結(jié)果是惟一的。簡單地說，穩(wěn)定性排序-數(shù)據(jù)排序過后能使值相同的數(shù)據(jù)，保持原順序中之相對位置。反之，則稱為“不穩(wěn)定性排序” 。若排序的序列中存在兩個或兩個以上關(guān)鍵字相等的記錄時，則排序得到的記錄序列的結(jié)果不惟一。假設(shè)ki= kj (1i n, 1jn, ij )，且在排序前的序列中 ri 領(lǐng)先于rj (即ij ) 。若在排序后的序列中ri 總是領(lǐng)先于rj ，則稱所用的排序方法是穩(wěn)定的；反之，若可能使排序后的序列中 rj領(lǐng)先于ri ，則稱所用的排序方法是不穩(wěn)定的。7月-226排序的基本概念27169（1）317249（2）1701234567 排序前：79（1）9（2）1617242731

4、01234567 穩(wěn)定排序：79（2）9（1）161724273101234567 不穩(wěn)定排序：7月-227排序的基本概念根據(jù)在排序的過程涉及的存儲器不同，排序方法可分為兩類：1.內(nèi)部排序（Internal Sort）：在排序進行的過程中不使用計算機外部存儲器的排序過程。選擇排序、插入排序、冒泡排序、計數(shù)排序快速排序、歸并排序、希爾排序堆排序、基數(shù)排序2. 外部排序（External Sort）：在排序進行的過程中需要堆外存進行訪問的排序過程。7月-228排序的基本概念內(nèi)部排序的過程是一個逐步擴大記錄的有序序列的過程。通常在排序的過程中，參與排序的記錄序列可劃分兩個區(qū)域：有序序列區(qū)和無序序列區(qū)

5、，其中有序序列區(qū)的的記錄已按關(guān)鍵字非遞減有序排列。使有序序列中記錄的數(shù)目至少增加一個的操作稱為一趟排序。7月-229排序的基本概念思想：在排序過程序中，依次從待排序的記錄序列中選擇出關(guān)鍵字值最小的記錄、關(guān)鍵字值次小的記錄、，并分別有序序列中的第1個位置、第2個位置、，最后剩下一個關(guān)鍵字值最大的記錄位于序列的最后一個位置，從而使待排序的記錄序列成為按關(guān)鍵字值由小到大排列的的有序序列。有序序列 R1.i-1無序序列 Ri.n有序序列 R1.i-1RjRi有序序列 R1.i無序序列 Ri+1.n一趟排序后一趟排序開始7月-22102.1Introduction由于每個人編寫的程序各有各的風格，通常很

6、難判斷好壞。可以作為判斷的標準的應是“程序運行的效率”，也就是程序性能。我們所說的“程序運行的效率”是指在程序正確執(zhí)行的前提下，所用的時間最少、空間最少。但是“時間”與“空間”常常是“魚與熊掌”無法兼得，如果希望以最短的時間來完成該程序，則常常需要運用更多的存儲空間，來換取最短的執(zhí)行時間；如果希望以最小的存儲空間來完成該程序，相反的也必須用較久的時間，才能完成該程序。7月-22112.1Introduction所謂程序性能(Program Performance)，是指運行一個程序所需要的內(nèi)存大小和時間?？梢圆捎脙煞N方法來確定一個程序的性能，一個是分析的方法，一個是實驗的方法。在性能分析(Pe

7、rformance analysis)時，采用分析的方法(對時間而言也稱為Priori-Estimate事前預測)。在性能測量(Performance measurement)時，借助于實驗的方法(對時間而言也稱為Posteriori Testing事后測試)7月-2212空間復雜性(space complexity) 是指運行一個程序所需要的內(nèi)存大小。1. 我們對一個程序的空間復雜性感興趣的主要原因如下：如果程序運行在多用戶系統(tǒng)上，通常需要指明分配給該程序內(nèi)存的大小。對任何的計算機系統(tǒng)都有內(nèi)存的限制，通過分析我們可以事先知道是否有足夠的內(nèi)存來運行該程序。一個問題可能有不同的內(nèi)存解決方案；(不

8、同的編譯器所需內(nèi)存不同)?？梢岳每臻g復雜度來估算一個程序所能解決問題的最大規(guī)模；如電路模擬程序，模擬一個有C個元件、W個連線的電路，需要內(nèi)存為280K+10*(C+W)字節(jié)的內(nèi)存。如果可用內(nèi)存總量為640K，則最大可模擬的規(guī)模為C+W36K的電路。2.2 Space Complexity7月-22132. 空間復雜性的組成：指令空間(instruction space)是指用來存儲經(jīng)過編譯之后的程序指令所需的空間。數(shù)據(jù)空間(data space)是指用來存儲所有常量和所有變量值所需的空間。數(shù)據(jù)空間由兩部分組成：存儲常量和簡單變量、存儲復合變量。環(huán)境?？臻g(environment stack

9、space)用來保存函數(shù)調(diào)用時為恢復程序繼續(xù)運行的有關(guān)信息所需的存儲空間。2.2 Space Complexity7月-22142.2 Space Complexity2.1) 指令空間：程序所需要的指令空間的大小取決于以下因素把程序編譯成機器代碼的編譯器。編譯時實際采用的編譯器選項。如優(yōu)化選項、對齊選項、覆蓋選項等。目標計算機。如有無浮點處理器。7月-22152.2 Space Complexity2.2) 數(shù)據(jù)空間：對于簡單變量和常量來說，所需要的空間取決于所使用的計算機和編譯器以及變量和常量的數(shù)目。我們關(guān)心的是數(shù)據(jù)的字節(jié)數(shù)，每種數(shù)據(jù)類型所占的字節(jié)數(shù)與機器和編譯器有關(guān)。對于復合變量，需要進

10、行計算。如：double a100和int mazerowscols對于32位元機器及32位元編譯器所站存儲空間分別為8*100和4*rows*colsTypeSpace(byte)Rangechar1-128 127 (-27 27-1 )unsigned char10 255 ( 0 28-1 )short2-32768 32767 (-215 215-1 )int4-231 231-1 unsigned int40 65535 ( 0 216-1 )long4-231 231-1unsigned long40 232-1float43.4E38double81.7E308long dou

11、ble103.4E-4932 1.1E+4932pointer2near pointer/Segment Regpointer4far pointer7月-22162.2 Space Complexity2.3) 環(huán)境?？臻g：對于剛開始做性能分析的人，本部分常常容易被乎略，原因是他們不理解函數(shù)是如何被調(diào)用的及在函數(shù)被調(diào)用結(jié)束后發(fā)生了什么。每當一個函數(shù)被調(diào)用時，下面的數(shù)據(jù)將被保留在環(huán)境棧中：所有引用參數(shù)及常量引用參數(shù)的定義。返回地址。函數(shù)被調(diào)用時所有局部變量的值以及傳值形式參數(shù)的值（對某些編譯器：僅對于遞歸函數(shù)而言）。7月-22172.2 Space Complexity2.4) Summary

12、:程序所需要的空間取決于多種因素，有些因素在編寫程序時是未知的。即使這些因素已完全知道，我們也無法精確的分析一個程序所需要的空間。但是，我們可以確定程序某些部分對空間的需求，這些部分依賴于所解決問題實例的特征。一般來說，這些特征包含決定問題規(guī)模的那些因素；如輸入輸出的數(shù)量等。例如對n個元素排序，兩個nXn矩陣的加法，我們可以把n作為特征。7月-22182.2 Space Complexity任意程序P所需空間S(P)可以表示如下：S(P)=c + Sp(實例特征)其中c是一個常數(shù)，表示固定部分所需要的空間。Sp表示可變部分所需要的空間。固定部分，它獨立于實例的特征，一般來說它包含指令空間、簡單

13、變量及定長復合變量的空間和常量空間?？勺儾糠?，它由以下部分組成：復合變量所需的空間（其大小依賴于解決問題的規(guī)模），動態(tài)分配的空間（通常依賴于實例的特征），以及遞歸棧所需的空間遞歸?？臻g包括遞歸深度（即嵌套遞歸調(diào)用的最大層次）、局部變量和形參的空間。7月-22192.2 Space ComplexityS(P)=c + Sp(實例特征)；在分析程序空間復雜度時，我們將主要精力放在估算Sp上。對于任意給定的問題，首先需要確定實例的特征，以便于估算空間需求。實例特征的選擇是一個很具體的問題，我們將通過實際例子來說明。實例特征說明：指令空間：與實例特征無關(guān)的常數(shù)數(shù)據(jù)空間：常量和簡單變量-實例無關(guān)復合變

14、量(數(shù)組、鏈表、樹和圖等) -問題實例特征有關(guān)環(huán)境棧空間(函數(shù)調(diào)用)-是否遞歸?非遞歸：實例特征無關(guān)遞歸：實例特征相關(guān)在分析空間復雜度時我們忽略與實例特征無關(guān)的空間需求量7月-22202.2 Space ComplexityS(P)=c + Sp(實例特征)；例2-1：程序1-4SAbc(傳值T) =3*sizeof(T);（動態(tài)空間分配） SAbc(引用T)=0; SAbc(abc的大小)=0;template T Abc(T& a, T& b, T& c)return a+b+b*c+(a+b-c)/(a+b)+4；/程序1-4template T Abc(T a, T b, T c) ；

15、/程序1-47月-22212.2 Space Complexity例2-2：順序搜索template int SequentialSearch(T a, const T& x, int n)/在無序數(shù)組a0 :n-1中搜索x; 如找到返回其位置int i;for (i=0; in & ai !=x; i+) ;if (i=n) return -1; return i;/程序1-4選實例特征n: S順序搜索(n)=0；(數(shù)組空間在在調(diào)用函數(shù)中分配)實例特征如何選擇？空間復雜度？7月-22222.2 Space ComplexitySsum(n)=0；SRsum(n)=(Addr +sizeof(

16、int)+sizeof(ptr) )*(n+1)SFactorial(n)=(Addr +sizeof(int) )*Maxn,1Template T Sum(T a, int n)/計算a0:n-1的和T tsum=0;for (int i=0; in; i+)tsum+=ai;return tsum; /程序1-8Template T Rsum(T a, int n)/遞歸計算a0:n-1的和if (n0) return Rsum(a,n-1)+an-1; return 0; /程序1-9int Factorial(int n)/遞歸計算n!if (n =1) return 1;else

17、return n* Factorial(n-1); /程序1-77月-2223空間復雜度小結(jié)對非遞歸算法分析與實例特征有關(guān)的數(shù)據(jù)結(jié)構(gòu)的大小復合變量對遞歸算法還要分析遞歸調(diào)用的深度和實例特征的關(guān)系環(huán)境棧地址參數(shù)變量(類型、地址)復合變量 (數(shù)組、指針、結(jié)構(gòu))遞歸深度7月-22242.3Time Complexity時間復雜性(time complexity) 是指運行完該程序所需要的時間。1. 我們對一個程序的時間復雜性感興趣的主要原因如下：有些計算機需要用戶提供程序運行時間的上限，一旦達到時間上限，程序?qū)⒈粡娭平Y(jié)束。正在開發(fā)的程序可能需要提供一個滿意的實時響應。如交互程序、通訊程序。如果有多種

18、可選的方案來解決一個問題，那么具體決定采用哪個？時間是一個重要的因素。對于各種解決方案的時間及空間復雜性將采用加權(quán)的方式進行評估。7月-22252.3Time Complexity2. 時間復雜度的組成影響一個程序空間復雜性的因素也都能影響程序的時間復雜性。一個程序所占的時間T(P)=編譯時間+運行時間。由于編譯時間和實例特征無關(guān)，我們關(guān)注的程序運行時間，記做tp(實例特征)如果我們了解編譯器的特性，并且清楚運行的環(huán)境，我們就可以對程序P進行加、減、乘、除、比較、讀、寫等操作進行計算，從而可以得到如下公式：7月-22262.3Time Complexitytp(n)=caADD(n)+ csS

19、UB(n)+ cmMUL(n)+其中ca、cs、cm為一個加法、減法、乘法的時間，函數(shù)ADD、SUB、MUL為相應運算的次數(shù)。有兩個更可行的方法可用來估算運行時間：找出一個或多個關(guān)鍵操作，確定關(guān)鍵操作所需的執(zhí)行時間(操作計數(shù))。確定程序總的執(zhí)行步數(shù)。7月-22272.3Time Complexity3. 操作計數(shù)(Operation Counts)估算一個程序或函數(shù)的時間復雜性的一種方式就是首先選擇一種或多種操作（如加、減、乘），然后確定這種操作分別執(zhí)行了多少次。這種方法是否成功取決于識別關(guān)鍵操作的能力，這些關(guān)鍵操作對時間復雜性的影響最大。讓我們先看看實際的例子（根據(jù)例子具體學習）例2-8多項

20、式求值多項式P(x) = i=0ncixi, 如果cn0，則P是一個n維多項式。7月-22282.3Time ComplexityTemplate T ProcA(T coef,int n, const T& x)/計算n次多項式的值 coef0 :n為多項式的系數(shù)T y=1, value= coef0;for (i=1; i=n; i+) y*=x;value+=y*coefi;return value;/程序2-3Template T ProcB(T coef,int n, const T& x)/計算n次多項式的值 coef0 :n為多項式的系數(shù)T y=1, value= coefn;f

21、or (i=1; i=n; i+) value=value*x+coefn-i;return value;/程序2-4算法基于多項式分解：P(x) =(cnx + cn-1)*x + cn-2)*x + )*x + c0ProcA 執(zhí)行了 n 次加法；2n次乘法；ProcB 執(zhí)行了 n 次加法；n次乘法；7月-22292.3Time Complexity例2-9計算名次元素在隊列中的名次(rank)，可定義為隊列中所有比它小的元素再加上它左面和它相同的元素數(shù)目。如數(shù)組a=4,3,9,3,7作為隊列，則各個元素的名次為r=2,0,4,1,3。如何設(shè)計程序？復雜度為(n-1)n/2Template

22、 void Rank(T a, int n, int r)/計算a0 :n-1中n個元素的排名for (int i=0; in; i+) ri=0;/初始化/逐個比較所有元素for (i=1; in; i+) for (int j=0; ji; j+) if(aj =ai) ri+;else rj+;/程序2-5；a 4 3 9 3 7 對于i的每個取值，執(zhí)行i次比較。總比較次數(shù)：1+2+。+n-1i=1 1 0i=2 1 0 2i=3 2 0 3 1i=4 2 0 4 1 37月-22302.3Time Complexity例2-10計數(shù)排序在使用rank排名后，就可按遞增的順序?qū)?shù)組進行重

23、新排序我們使用附加數(shù)組u,來進行排序Rearrangs的復雜度為2n這種用程序2-5和2-6排序的方法稱為計數(shù)排序（Rank sort)復雜度(n-1)n/2+2nTemplate void Rearrangs(T a, int n int r)/按序重排數(shù)組a中的元素，T *u = new Tn+1; /輔助數(shù)組u/在u中移動到正確位置for (int i=0; in; i+) uri=ai;/move back to afor (i=0; in; i+) ai=ui;delete u;/程序2-6；7月-22312.3Time Complexity例2-11選擇排序初始狀態(tài)49138654

24、9276132752i=1133865492764912752i=2132765492764913852i=3132738492764916552i=4132738492764916552i=5132738492491655276i=6132738492491657652i=71327384924916576527月-22322.3Time Complexity例2-11選擇排序思路為選擇最小的數(shù)放在最前面；在剩下的元素重復此步驟。每個Min的比較次數(shù)為n-size-1;總的次數(shù)為 (n-1)n/2移動次數(shù)為3(n-1) 選擇排序的復雜度為(n-1)n/2+ 3(n-1)Template vo

25、id SelectionSort(T a, int n)/對數(shù)組a0 :n-1中的元素進行排序for (int size=0; sizen-1; size+) int j=Min(a, size, n); Swap(aj, asize);/程序2-7；Template Int Max (T a, int n)/Locate the largest element in a0:n-l int pos = 0;for (int i=0; in; i+) if (aposai) pos = i;return pos; /program1-31；7月-22332.3Time Complexity例2-

26、12冒泡排序37968548549637968963754896548377月-22342.3Time Complexity例2-12冒泡排序是一種簡單的排序方法，思路為把最大的元素移到右部。在冒泡過程中，對相臨的元素進行比較，如果左邊的元素大，左右交換。在一趟冒泡排序中最大的 元素一定在最右邊。元素比較次數(shù)為 (n-1)n/2，與選擇排序相同Template void Bubble(T a, int n)/把數(shù)組a0 :n-1中最大的元素通過冒泡移動到右邊（一次冒泡）for (int i=0; i ai+1) Swap(ai,ai+1);/程序2-8；Template void Bubble

27、Sort(T a, int n)/把數(shù)組a0 :n-1中的n個元素進行冒泡排序for (int i=n; i 1; i-) Bubble( a, i );/程序2-9；7月-22352.3Time Complexity通過已給出的例子我們知道時間復雜度和輸入數(shù)據(jù)有關(guān)，也就是實例的特征較為簡單，操作計數(shù)都是這些特征的良性函數(shù)(nice function)。如果我們加入一些其它特性，問題就會變得很復雜，例如Bobble所執(zhí)行的交換次數(shù)不僅依賴于n，而且還依賴于數(shù)組a中的具體情況。交換次數(shù)在0n-1之間變化。由于操作數(shù)不總是由所選定的實例特征唯一確定；我們會提出最好的、最壞的操作數(shù)是多少？下面我們來

28、討論這個問題。7月-22362.3Time Complexity例2-15再看計數(shù)排序：在已經(jīng)使用Rank計算出數(shù)組中元素的名次后，我們可以在原地進行排序。方法是如果ri!=i；把ai和ari進行交換；交換的結(jié)果是把ai放到該放的位置。該程序最少執(zhí)行了0次交換，最大2(n-1)次交換。因為每次交換需三次移動，所以該程序的最壞情況，時間增加，但節(jié)省了內(nèi)存。Template void Rearrangs(T a, int n int r)/原地重排數(shù)組a中的元素for (int i=0; in; i+) while( ri!=i ) /獲得應該排在ai處的元素 int t = ri; Swap(

29、ai, at ); Swap( ri, rt ); /程序2-11；4393720413i: ri:ai:0123494423904391479347月-22372.3Time Complexity例2-16再看選擇排序：前面的選擇排序有一個缺點，即使元素已經(jīng)排序它還在繼續(xù)執(zhí)行。改進方法是在查找最大元素時，順便檢查數(shù)組是否已經(jīng)排序。最好情況外循環(huán)僅執(zhí)行1次；a中元素進行了n-1次比較。最壞情況執(zhí)行的比較次數(shù)為(n-1)n/2。最壞與原程序一樣。Template void SelectionSort(T a, int n)/及時終止選擇排序bool sorted = false;for (int

30、 size=n; !sorted & (size1); size-) int pos = 0 sorted = true; for ( int i=1; i size; i+) /找最大元素 if (apos =ai) pos= i; /判定是否已為遞增排序 else sorted = false; /未按序排列 Swap(apos, asize-1);/程序2-12；7月-22382.3Time Complexity例2-17再看冒泡排序：我們同樣可以參考選擇排序的方法，可以設(shè)計一個及時的終止冒泡排序函數(shù)。改進方法是在冒泡中沒有交換，就可以終止冒泡過程。最好情況比較次數(shù)為n-1，最壞和原來一

31、樣。Template bool Bubble(T a, int n)/把數(shù)組a0 :n-1中最大的元素冒泡至右端bool swapped = false;for (int i=0; i ai+1) Swap(ai,ai+1);swapped = true; return swapped;void BubbleSort(T a, int n)/及時終止冒泡排序for (int i=n; i 1 & Bubble( a, i ); i-);/程序2-13；7月-22392.3Time Complexity插入排序初始狀態(tài)491386597761327492i=2i=3i=4i=5i=6i=7i=8

32、3849165977613274923849165977613274923865491659776132749238974916576971327492387649138657697274921313491273865769749213274912738976576492134927月-22402.3Time Complexity例2-18插入排序：我們可以以Insert函數(shù)為基礎(chǔ)，設(shè)計一個排序程序。我們知道如果只有一個元素的數(shù)組，是有序數(shù)組。這時再插入數(shù)據(jù)也是有序數(shù)組。最好情況比較次數(shù)為n-1，最壞為(n-1)n/2Template void Insert(T a, int & n, con

33、st T& x)/向有序數(shù)組a0 :n-1中插入元素xfor (int i=n-1; i=0 & x ai; i-) ai+1=ai;ai+1=x;void InsertionSort(T a, int n)/對a0 :n-1進行排序for (int i=1; in; i+) T t=ai; Insert(a, i, t);/程序2-14； 2-15是把兩個函數(shù)合一7月-22412.3Time Complexity4. 執(zhí)行步數(shù)(step-count)利用操作計數(shù)方法來估算程序的時間復雜性時，忽略了所選操作計數(shù)以外的其它操作的開銷。執(zhí)行步數(shù)(step-count) 統(tǒng)計程序或函數(shù)中全部的時間開

34、銷。與操作計數(shù)一樣，執(zhí)行步數(shù)也是實例特征的函數(shù)。盡管對特定的程序可能會有若干個特征（如輸入輸出的個數(shù)和大小），但可以把執(zhí)行步數(shù)看成是其中一部分特征的函數(shù)。語句頻度7月-22422.3Time Complexity在確定一個程序的執(zhí)行步數(shù)之前，必須確切地知道將要采用的實例特征。這些特征不僅定義了執(zhí)行步數(shù)表達式中的變量，而且定義了以多少次計算作為一步。在選擇了實例特征后，可以定義一個操作步(step). 操作步是獨立于所選特征的任意計算單位。如100次乘法可視為一步；但n次乘法不能視為一步，因為n是實例特征。同樣，在包含實例特征的多次計算不能算成是一步。7月-22432.3Time Complex

35、ity定義程序步程序步(program step)可以定義為一個語法或語義意義上的程序片段，該片段獨立于實例特征。如 return a+b+b*c+(a+b+c)/(a+b)+4;可以被視為一個程序步。同樣 x=y; 也可以被視為一個程序步。我們可以使用初值為0的全局變量count來確定一個程序或函數(shù)為完成預定任務(wù)所需的執(zhí)行步數(shù)。可以count引入到程序中，每當原程序的一條語句被執(zhí)行，就在count上累加該語句的執(zhí)行步數(shù)。當程序結(jié)束時count的值就是所需的執(zhí)行步數(shù)。7月-22442.3Time Complexity例2-19 把count引入到函數(shù)Sum(1-8)問執(zhí)行步數(shù)是多少？執(zhí)行步數(shù)為

36、2n+3;templateT Sum(T a, int n)/ Return sum of numbers a0:n - 1. T tsum = 0; count+; / for tsum = 0 for (int i = 0; i n; i+) count+; / for the for statement tsum += ai; count+; / for assignment count+; / for last execution of for count+; / for return return tsum;/程序2-167月-22452.3Time Complexity例2-20

37、把count引入到遞歸函數(shù)Rsum (1-9)templateT Rsum(T a, int n)/ Return sum of numbers a0:n - 1. count+; / for if conditional if (n 0) count+; / for return return Rsum(a, n-1) + an-1; count+; / for return return 0;/程序2-18令tRsum(n)為執(zhí)行步數(shù)，我們知道tRsum(0)=2tRsum(n)=2+tRsum(n-1)，n0;上式為遞歸等式。計算后得到tRsum(n)=2n+tRsum(0)=2(n+1

38、)我們注意到Rsum的執(zhí)行步數(shù)小于Sum,但由于執(zhí)行步數(shù)不是精確時間，目前還無法確定他們誰快。7月-22462.3Time Complexity例2-21矩陣加 執(zhí)行步數(shù)為2rows*cols+2rows+1;問題：如果rows比cols大，怎樣修改程序？templatevoid Add( T *a, T *b, T *c, int rows, int cols)/ Add matrices a and b to obtain matrix c. for (int i = 0; i rows; i+) for (int j = 0; j cols; j+) cij = aij + bij;/程

39、序2-19templatevoid Add( T *a, T *b, T *c, int rows, int cols)/ Add matrices a and b to obtain matrix c. for (int i = 0; i rows; i+) count+; / preceding for loop, rows for (int j = 0; j cols; j+) count+; / preceding for loop, rows*cols cij = aij + bij; count+; / assignment, rows*cols count+; / last ti

40、me of j for loop, rows count+; / last time of i for loop, 17月-22472.3Time Complexity我們也可以不使用count計數(shù)；而是建立一張表，在該表中列出每條語句所需要的執(zhí)行步數(shù)。在建立該表時，我們先確定該語句每一次執(zhí)行所需步數(shù)（記為s/e)以及該語句總的執(zhí)行次數(shù)（頻率）。利用這兩個量就可以確定每條語句的執(zhí)行步數(shù)。把所有語句相加就得到程序執(zhí)行步數(shù)。注意：一條語句的程序步數(shù)與該語句每次執(zhí)行所需步數(shù)有重要的區(qū)別，區(qū)別在于程序步數(shù)不能反映該語句的復雜程度。如 x=Sum(a,m)的程序步數(shù)為1，但該語句的導致count的變化為

41、1+2m+37月-22482.3Time Complexity語 句s/e頻率總步數(shù)T Sum(T a, int n)/ Return sum of a0:n -1. T tsum = 0; for (int i = 0; i 0) return Rsum(a, n-1)+an-1;return 0;00111000n+1n1000n+1n10總 計2n+27月-22492.3Time Complexity在某些情況，一條語句每次執(zhí)行所需要的執(zhí)行步數(shù)可能隨時發(fā)生變化。例如計算數(shù)組元素的和:i=0jai 對于j=0,1,n-1我們已知Sum(a,n)的執(zhí)行步數(shù)為2n+3,在函數(shù)中的步數(shù)為2j+6

42、;該函數(shù)總的執(zhí)行步數(shù)為:j=0n-1(2j+6)=n(n+5)語 句s/e頻率總步數(shù)void Inef(T a, T b, int n)/ Compute prefix sums. for (int j = 0; j n; j+) bj = Sum(a, j + 1);0012j+6000n+1n000n+1n(n+5)0總 計n2+6n+17月-22502.3Time Complexity語 句s/e頻率總步數(shù)int SequentialSearch(T a, T& x, int n)/順序搜索最壞情況 int i; for (i = 0; i n & ai != x; i+); if (i

43、 = n) return -1; return i;0011110001n+1100001n+1100總 計n+3語 句s/e頻率總步數(shù)int SequentialSearch(T a, T& x, int n)/順序搜索最好情況 int i; for (i = 0; i 0 ,則f(n)=O(nm)證明: f (n) i=0m|ai|ni nmi=0m|ai|ni-m nmi=0m|ai|7月-22552.4Asymptotic Notation例2-24、線性函數(shù)：f(n)=3n+2; f(n)=O(n)例2-25、平方函數(shù)：f(n)=10n2+4n+2; f(n)=O(n2)例2-26、

44、指數(shù)函數(shù)：f(n)=6*2n+n2; f(n)=O(2n)例2-27、常數(shù)函數(shù)：f(n)=2345; f(n)=O(1)例2-28、松散界限：10n+8=O(n2);6n2n+20=O(n22n ) 顯然、它們不是最小上限。例2-29、錯誤界限：3n+2O(1);2n2+4nO(n) 反證法證明不符合定義。（見書P57）7月-22562.4Asymptotic Notation2. 符號(漸進緊密下限)符號，用來估算函數(shù)f的下限值定義:符號 f (n)=(g(n) 當且僅當存在正的常數(shù)c和n0,使得對所有的nn0 ,有 f (n) cg(n) 定理1: 如果f(n)=amnm+a1n+a0 ,

45、且am0 ,則f(n)=(nm)7月-22572.4Asymptotic Notation3. 符號(漸進緊密限度)符號適用于同一個函數(shù)既可作為函數(shù)f的上限也可以作為f的下限的情形定義:符號 f (n)=(g(n) 當且僅當存在正的常數(shù)c1，c2和某個n0,使得對所有的nn0 ,有 c2g(n) f(n) c1g(n) 定理1: 如果f(n)=amnm+a1n+a0 ,且am0 ,則f(n)= (nm)7月-22582.4Asymptotic Notation4. 小寫o符號(非緊密上限)小寫o符號，用來估算函數(shù)f的下限值定義:小寫o f (n)=o(g(n) 當且僅當f(n)=O(g(n)

46、且 f(n)(g(n)例：計算3n+2 的小寫o 3n+2=O(n2) , 3n+2=(n) and 3n+2(n2) 3n+2=o(n2) but 3n+2o(n) 同樣我們可以定義小寫符號(非緊密下限)7月-22592.4Asymptotic Notation5.1 關(guān)于漸進符號的其它定理定理：對于任一個實數(shù)x0和任一個實數(shù)0下面的結(jié)論都是正確的：1) 存在某個n0使得對于任何nn0 ,有(logn)x(logn)x+。2) 存在某個n0使得對于任何nn0 ,有(logn)x n3) 存在某個n0使得對于任何nn0 ,有nx nx+。4) 對于任意實數(shù)y，存在某個n0使得對于任何nn0 ,

47、 有nx(logn)y nx+ 。5) 存在某個n0使得對于任何nn0 ,有nx1) (rn)E7:n! (n/e)n)E8:ni=1 1/i (log n)7月-22612.4Asymptotic Notation5.3 實用的規(guī)則S1: if b1 and a1 then logan (logbn) S2: if ba0 then an o(bn)S3: if a0 then logn o(an)S4: if a0 then an o(n!)S5: if ab then na O(nb)S6: if a0 and b1 then na o(bn)S7: if limnf (n)/g (n)

48、=c then f(n) (g(n) if limnf (n)/g (n)=0 then f(n) o(g(n) if limnf (n)/g (n)= then g(n) o(f(n) 7月-22622.4Asymptotic Notation6 復雜性分析舉例我們已經(jīng)學習了漸進符號的表示方法和他們的一些定理和公式。在不需要精確確定執(zhí)行步數(shù)的情況下，可以應用漸進符號來分析本章第三節(jié)關(guān)于執(zhí)行步數(shù)的情況。我們把使用漸進符號表示有關(guān)執(zhí)行步數(shù)的時間復雜性稱為漸進復雜性。語 句s/e頻率總步數(shù)T Sum(T a, int n)/ Return sum of a0:n -1. T tsum = 0; for (int i = 0; i n; i+) tsum += ai; return tsum;0011110001n+1n10(0)(0)(1)(n)(n