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

2、取程序在真實環境的實際運行時間。定義 空間復雜度是程序運行所需的存儲空間；時間復雜度是程序的運行時間。1 空間復雜度程序運行所需空間包括兩部分：1. 定長空間需求：即與程序輸入、輸出無關的空間。2. 變長空間需求：即與求解的問題實例相關的結構化變量所占的空間大小。如果是遞歸程序，還應加上遞歸時所需工作空間的大小。任何程序所需的空間大小就是上述兩塊空間的總和。但分析一個程序的空間復雜度，通常僅僅考察變長空間需求。看下面例子：代碼1：float abc(float a, float b,float c)return a+b+b*c+(a+b-c)/(a+b)+4.00;函數abc的輸入是三個簡單變

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

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

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

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