程序性能

程序性能是指運行程序所需要的內存和時間的多少。有兩種方法來確定一個程序的性能：一個是分析方法；另一個是實驗方法。在性能分析(performance analysis)時，採用分析方法，而在性能測量(performance measurement)時，使用實驗方法。 ^[1] 

應用程序的性能很大程度上依賴於所採用的算法，從這個意義上講，算法是程序的靈魂。運行時間和佔用空間是算法性能最關鍵的指標，可以考察這些指標的實際值，比如可利用計時工具來考察運行時間，又如操作系統中的相關工具可以查看佔用空間。從效率觀點看，高效的算法意味其執行過程消耗的機器資源較少，而計算機系統必要的構成是CPU和內存，那麼肯定得要求算法的執行過程應儘量少佔用處理機時間和內存。

不過，這些具體且“實際”的指標值卻是不“實用”的性能指標，一方面，不同的計算機由於性能各異造成指標值不同；另一方面，這些指標值隨着輸入數據不同而相差較大．顯然，可以在某些條件上給出具體的指標值，但這無法適用於所有情況。鑑於此，理論分析工具的呼喚是必然的，而如今此方面的研究已經成長為算法分析(Algorithm Analysis)這個專門的領域。

算法分析一般是理論上的，它可以在算法運行之前進行預判，也可以在算法運行之後進行總結改進，但算法分析代替不了實際的性能測試，必須在真正的計算機上利用實際的編譯器得到可執行的代碼運行，根據實測效果進行優化並重新給出更精準的分析，這樣才能達到最佳的效果。

時間複雜度(Time complexity)，算法完全運行所需運算時間。

空間複雜度(Space complexity)，算法完全運行所需存儲空間。

這兩個指標衡量了算法的時空效率，為區分數據取值情況對性能分析帶來的影響，可將時間複雜度和空間複雜度加上一定的限制：

最壞情況下的時間/空間複雜度，對於指定問題規模量，輸入遍取所有可能情況下時問/空間複雜度的最大值。

最好情況下的時間/空間複雜度，對於指定問題規模量，輸入遍取所有可能情況下時間/空間複雜度的最小值。

平均情況下的時間/空間複雜度，對於指定問題規模量，輸入遍取所有可能情況下時間/空間複雜度的數學期望，通常假設輸入數據滿足等概率分佈。 ^[2] 

時間複雜度是指一個算法運行所需的時間。一個算法的運行時間取決於算法所需執行的語句(運算)的多少。算法的時間複雜度通常用該算法執行的總語句(運算)的數量級決定。

就算法分析而言，一條語句的數量級即執行它的頻數，一個算法的數量級是指它的所有語句執行頻數之和。

研究的原因：

1、有些計算機需要用户提供程序運行時間的上限，一旦達到這個上限，程序將被強制結束。可以簡單地指定時間上限為幾千年．可是，如果程序因為數據問題而陷入死循環，可要為機時付出鉅額資金。因此希望時間上限應該稍大於所期望的運行時間。

2、正在開發的程序可能需要一個令人滿意的實時響應(realtime response)。例如，所有交互式程序都必須如此。一個文本編輯器(text editor)，光標上移一頁或下移一頁需要1min．就很難找到用户；一個電子製表軟件(spreadsheet)，對一個單元重新計值需要幾分鐘，就沒人樂意買賬；一個數據庫管理系統(database management system)，對一個關係進行排序時，用户可以有時間去喝兩杯咖啡，就不可能有市場。為交互式應用所設計的程序都必須具有令人滿意的實時響應。

3、如果一個問題有多種解決方案，那麼具體採用哪一種方案，主要根據這些方案的性能差異。對於各種方案的時間和空間性能，採用加權測量方式進行評價。 ^[1] 

算法的空間複雜度是指算法運行的存儲空間，是實現算法所需的內存空間的大小。

一個程序運行所需的存儲空間通常包括固定空間需求與可變空間需求兩部分。固定空間需求包括程序代碼、常量與靜態變量等所佔的空間。可變空間需求包括局部作用域非靜態變量所佔用的空間、從堆空間中動態分配的空間與調用函數所需的系統棧空間等。

通常用算法設置的變量(數組)所佔內存單元的數量級來定義該算法的空間複雜度。如果一個算法佔的內存空間很大，在實際應用時該算法也是很難實現的。 ^[3] 

研究的原因：

(1)如果一個程序要運行在一個多用户計算機系統中，那麼需要指明該程序所需內存的大小。

(2)在任何一個計算機系統上運行程序，都需要知道是否有足夠的內存可以用來運行該程序。

(3)一個問題可能有若干個解決方案，它們對內存的需求各不相同。比如，某個C++編譯器僅需要1MB的空間，而另一個C++編譯器可能需要4MB的空間，如果計算機內存少於4MB，那麼只能選擇第一個編譯器。即使計算機有足夠的內存．如果兩個編譯器作用相同，那麼也寧願使用較小的編澤器，以便把更多的內存留作他用。

(4)利用空間複雜度可以估算一個程序所能解決的問題最大可以是什麼規模。 ^[1]