《程序的性能分析》word版

1、學習程序算法的一個總要目標就是學會判斷程序性能的優(yōu)劣。當然判斷的標準有很多，至少包括如下幾點：1. 程序是否符合任務的規(guī)范說明。2. 程序是否正確。3. 是否有配套文檔，說明程序的用法和原理。4. 程序是否根據(jù)邏輯關(guān)系分解成能有效執(zhí)行的函數(shù)。5. 程序代碼是否易讀。以上判據(jù)至關(guān)重要，對構(gòu)建大規(guī)模程序系統(tǒng)，顯得更為關(guān)鍵。然而若要指出上述標準卻并非易事。除了上述一般性判據(jù)之外，以下兩條判據(jù)更加具體。6. 程序是否能夠高效使用主存和輔存。7. 程序的運行時間是否令人滿意最后這兩條可以分兩方面來討論：第一方面的性能估計與機器無關(guān)，來推斷程序的空間代價和時間代價，稱為性能分析；第二方面稱為性能度量，即獲

2、取程序在真實環(huán)境的實際運行時間。定義 空間復雜度是程序運行所需的存儲空間；時間復雜度是程序的運行時間。1 空間復雜度程序運行所需空間包括兩部分：1. 定長空間需求：即與程序輸入、輸出無關(guān)的空間。2. 變長空間需求：即與求解的問題實例相關(guān)的結(jié)構(gòu)化變量所占的空間大小。如果是遞歸程序，還應加上遞歸時所需工作空間的大小。任何程序所需的空間大小就是上述兩塊空間的總和。但分析一個程序的空間復雜度，通常僅僅考察變長空間需求?？聪旅胬樱捍a1：float abc(float a, float b,float c)return a+b+b*c+(a+b-c)/(a+b)+4.00;函數(shù)abc的輸入是三個簡單變

3、量，輸出返回一個簡單變量。根據(jù)以上分類，這個函數(shù)只有定長空間需求，因此空間復雜度為0.代碼2：float sum(float list, int n)float tempsum =0;int i;for(i=0;i<n;i+)tempsum+=listi;return tempsum;代碼2的輸出只有一個簡單變量，但輸入比上例增加了一個數(shù)組，這里變長空間需求依賴于數(shù)組參量是如何傳入函數(shù)的。不同語言的處理各不相同，對于Pascal語言，數(shù)組參量是按值傳遞的，也就是說這個函數(shù)在執(zhí)行時，整個數(shù)組被復制到函數(shù)的臨時存儲空間。這樣空間復雜度就為n，n是數(shù)組長度。c語言的參數(shù)傳遞方法雖然也是傳值調(diào)用

4、，但c只傳遞數(shù)組一個元素的首地址，并不復制數(shù)組，因而空間復雜度為0.代碼3：float sum(float list, int n)if(n) return sum(list,n-1)+listn-1;else return 0;代碼3也是增加了一個數(shù)組，不過這個球和程序是遞歸程序，編譯器要為每次遞歸調(diào)用保存參量、局部變量、返回地址。一次遞歸所需的空間就是兩個參量加上返回地址的字節(jié)數(shù)。比較求和和程序的循環(huán)實現(xiàn)和遞歸實現(xiàn)，前者無變長空間需求，而后者的開銷要大許多。2 時間復雜度程序的時間開銷是編譯時間和運行（執(zhí)行）時間的總和。編譯時間與定長空間需求類似，同樣與實例特征無關(guān)，而且，程序經(jīng)檢驗確定其

5、正確性之后，編譯結(jié)果可不斷執(zhí)行。所以時間復雜度僅考慮程序的執(zhí)行時間。比較簡單的方法，是統(tǒng)計執(zhí)行時所需各種操作的次數(shù)。這種方法的計數(shù)結(jié)果與機器無關(guān)，但首先要把程序分成獨立的程序步。這里要注意：a=2；是一個程序步，a=2*b-a+5/4*6;也是一個程序步。雖然執(zhí)行時間不同，但都被看作一步。有時候，執(zhí)行同樣的功能，遞歸程序的程序步比相應循環(huán)程序步少，初看令人驚奇，但不要忘記，程序步的計數(shù)告訴我們程序以多少個步驟執(zhí)行，并沒有告訴我們每一步的執(zhí)行時間。事實上遞歸程序的執(zhí)行一般而言要比循環(huán)程序慢，所以花的時間往往要比循環(huán)程序多一些。還有要注意的是，只有在程序的相應特征（n,m,p,q,r.）選定后，才

6、可以定義什么是程序步。程序步是與特征無關(guān)的計算單位。所以，10次加法可以是一個程序步，1000次乘法也可以是一個程序步。但n次加法卻不可以是一個程序步，因為它的大小已經(jīng)與相應特征有關(guān)了。3 漸進記號O由于程序步不能表示程序運行每一步的時間，因此即使用精確的程序步值做比較，結(jié)果也是不準確的。只有在程序步數(shù)目相差很大時，例如3n+3和100n+10相比才有意義。對于多數(shù)情形，能夠給出如下論斷就可以了，如，其中和是非負常量。原因是當n充分大的時候，上式中前者會明顯比后者運行的更快，而n比較小的時候，快慢是不確定的（取決于和的取值）。但是不論取何值，總存在一個n值，之后，復雜度為的程序總沒有復雜度為的程序運行的快，這個n值稱為失衡點（break even point）。一旦知道了一定存在一個失衡點，然后形式地得到程序的復雜度，我們所需的信息已經(jīng)足夠了。不再需要刻意找出精確值。我們把這種存在失衡點的