一個程式對記憶體和時間的需求稱為程式性能(program performance)。要對數據結構和算法設計方法給予科學的評價，就必須能夠計算程式性能。
基本介紹
- 中文名：程式性能
- 外文名：program performance
- 定義：程式對記憶體和時間的需求
- 方法：分析方法、實驗方法
- 系統：計算機
- 套用學科：計算機原理
概述,算法,空間複雜度,時間複雜度,
概述
程式性能是指運行程式所需要的記憶體和時間的多少。有兩種方法來確定一個程式的性能：一個是分析方法；另一個是實驗方法。在性能分析(performance analysis)時，採用分析方法，而在性能測量(performance measurement)時，使用實驗方法。
應用程式的性能很大程度上依賴於所採用的算法，從這個意義上講，算法是程式的靈魂。運行時間和占用空間是算法性能最關鍵的指標，可以考察這些指標的實際值，比如可利用計時工具來考察運行時間，又如作業系統中的相關工具可以查看占用空間。從效率觀點看，高效的算法意味其執行過程消耗的機器資源較少，而計算機系統必要的構成是CPU和記憶體，那么肯定得要求算法的執行過程應儘量少占用處理機時間和記憶體。
不過，這些具體且“實際”的指標值卻是不“實用”的性能指標，一方面，不同的計算機由於性能各異造成指標值不同；另一方面，這些指標值隨著輸入數據不同而相差較大．顯然，可以在某些條件上給出具體的指標值，但這無法適用於所有情況。鑒於此，理論分析工具的呼喚是必然的，而如今此方面的研究已經成長為算法分析(Algorithm Analysis)這個專門的領域。
算法分析一般是理論上的，它可以在算法運行之前進行預判，也可以在算法運行之後進行總結改進，但算法分析代替不了實際的性能測試，必須在真正的計算機上利用實際的編譯器得到可執行的代碼運行，根據實測效果進行最佳化並重新給出更精準的分析，這樣才能達到最佳的效果。
時間複雜度(Time complexity)，算法完全運行所需運算時間。
空間複雜度(Space complexity)，算法完全運行所需存儲空間。
這兩個指標衡量了算法的時空效率，為區分數據取值情況對性能分析帶來的影響，可將時間複雜度和空間複雜度加上一定的限制：
最壞情況下的時間/空間複雜度，對於指定問題規模量，輸入遍取所有可能情況下時問/空間複雜度的最大值。
最好情況下的時間/空間複雜度，對於指定問題規模量，輸入遍取所有可能情況下時間/空間複雜度的最小值。
平均情況下的時間/空間複雜度，對於指定問題規模量，輸入遍取所有可能情況下時間/空間複雜度的數學期望，通常假設輸入數據滿足等機率分布。
算法
空間複雜度
空間複雜度(space complexity)是指一個算法運行所需的時間。一個算法的運行時間取決於算法所需執行的語句(運算)的多少。算法的時間複雜度通常用該算法執行的總語句(運算)的數量級決定。
就算法分析而言，一條語句的數量級即執行它的頻數，一個算法的數量級是指它的所有語句執行頻數之和。
研究的原因：
(1)如果一個程式要運行在一個多用戶計算機系統中，那么需要指明該程式所需記憶體的大小。
(2)在任何一個計算機系統上運行程式，都需要知道是否有足夠的記憶體可以用來運行該程式。
(3)一個問題可能有若干個解決方案，它們對記憶體的需求各不相同。比如，某個C++編譯器僅需要1MB的空間，而另一個C++編譯器可能需要4MB的空間，如果計算機記憶體少於4MB，那么只能選擇第一個編譯器。即使計算機有足夠的記憶體．如果兩個編譯器作用相同，那么也寧願使用較小的編澤器，以便把更多的記憶體留作他用。
(4)利用空間複雜度可以估算一個程式所能解決的問題最大可以是什麼規模。
時間複雜度
算法的空間複雜度是指算法運行的存儲空間，是實現算法所需的記憶體空間的大小。
一個程式運行所需的存儲空間通常包括固定空間需求與可變空間需求兩部分。固定空間需求包括程式代碼、常量與靜態變數等所占的空間。可變空間需求包括局部作用域非靜態變數所占用的空間、從堆空間中動態分配的空間與調用函式所需的系統棧空間等。
通常用算法設定的變數(數組)所占記憶體單元的數量級來定義該算法的空間複雜度。如果一個算法占的記憶體空間很大，在實際套用時該算法也是很難實現的。
研究的原因：
1、有些計算機需要用戶提供程式運行時間的上限，一旦達到這個上限，程式將被強制結束。可以簡單地指定時間上限為幾千年．可是，如果程式因為數據問題而陷入死循環，可要為機時付出巨額資金。因此希望時間上限應該稍大於所期望的運行時間。
2、正在開發的程式可能需要一個令人滿意的實時回響(realtime response)。例如，所有互動式程式都必須如此。一個文本編輯器(text editor)，游標上移一頁或下移一頁需要1min．就很難找到用戶；一個電子製表軟體(spreadsheet)，對一個單元重新計值需要幾分鐘，就沒人樂意買賬；一個資料庫管理系統(database management system)，對一個關係進行排序時，用戶可以有時間去喝兩杯咖啡，就不可能有市場。為互動式套用所設計的程式都必須具有令人滿意的實時回響。
3、如果一個問題有多種解決方案，那么具體採用哪一種方案，主要根據這些方案的性能差異。對於各種方案的時間和空間性能，採用加權測量方式進行評價。
