空間複雜性

空間複雜性(space complexity)計算機算法分析的重要概念之一，是計算中所需的存儲空間資源耗費量的估計。如果一個問題的大小為n，解這個問題的某一算法所需的輔助存儲空間為n的某個函數S(n)，則稱S (n)為該算法的空間複雜性。例如，n個整數的分類問題，當用歸併分類算法時，空間複雜性為O(n)，當用直接插入分類算法時，空間複雜性為O(1)(一個與n無關的常數)。 ^[1] 

程序性能（program performance），是指運行一個程序所需要的內存大小和時間。

可以採用兩種方法來確定一個程序的性能，一個是分析的方法，一個是實驗的方法。在進行性能分析（performance analysis）時，採用分析的方法，而在進行性能測量（performance measurement）時，藉助於實驗的方法。

對一個程序的空間複雜性感興趣的主要原因如下：

·如果程序將要運行在一個多用户計算機系統中，可能需要指明分配給該程序的內存大小。

·對任何一個計算機系統，想提前知道是否有足夠可用的內存來運行該程序。

·一個問題可能有若干個內存需求各不相同的解決方案。

·可以利用空間複雜性來估算一個程序所能解決的問題的最大規模 ^[2] 

程序所需要的空間主要由以下部分構成：

·指令空間（instruction space）指令空間是指用來存儲經過編譯之後的程序指令所需的空間。

·數據空間（data space）數據空間是指用來存儲所有常量和所有變量值所需的空間。數據空間由兩個部分構成：存儲常量和簡單變量所需要的空間；存儲複合變量所需要的空間，這一類空間包括數據結構所需的空間及動態分配的空間。

·環境棧空間（environment stack space）環境棧用來保存函數調用返回時恢復運行所需要的信息。例如，如果函數fun1調用了函數fun2，那麼至少必須保存fun2結束時fun1將要繼續執行的指令的地址。

程序所需要的指令空間的數量取決於如下因素：

·把程序編譯成機器代碼的編譯器。

·編譯時實際採用的編譯器選項。

·目標計算機

在決定最終代碼需要多少空間的時候，編譯器是一個最重要的因素。圖給出了用來計算表達式a + b + b * c + ( a + b - c ) / ( a + b ) + 4的三段可能的代碼，它們都執行完全相同的算術操作（如每個操作符都有相同的操作數），但每段代碼所需要的空間都不一樣。所使用的編譯器將確定產生哪一種代碼

另外一種可以顯著減少程序空間的編譯器選項就是覆蓋選項，在覆蓋模式下，空間僅分配給當前正在執行的程序模塊。在調用一個新的模塊時，需要從磁盤或其他設備中讀取，新模塊的代碼將覆蓋原模塊的代碼。所以程序空間就等價於最大的模塊所需要的空間（而不是所有模塊之和）。

目標計算機的配置也會影響代碼的規模。如果計算機具有浮點處理硬件，那麼每個浮點操作可以轉換成一條機器指令。如果沒有安裝浮點處理硬件，必須生成仿真的浮點計算代碼。 ^[2] 

對於簡單變量和常量來説，所需要的空間取決於所使用的計算機和編譯器以及變量與常量的數目。之所以如此是因為我們通常關心所需內存的字節數。由於每字節所佔用的位數依賴於具體的機器環境，因此每個變量所需要的空間也會有所不同。此外，存儲2¹⁰⁰也將比存儲2³需要更多的位數。

在剛開始從事性能分析時，分析員通常會忽略環境棧所需要的空間，因為他們不理解函數是如何被調用的以及在函數調用結束時會發生什麼。每當一個函數被調用時，下面的數據將被保存在環境棧中：

·返回地址。

·函數被調用時所有局部變量的值以及傳值形式參數的值（僅對於遞歸函數而言）。

·所有引用參數及常量引用參數的定義。

每當遞歸函數被調用時，不管該調用是來自外部或a的當前賦值、n的值以及程序運行結束時的返回地址都被存儲在環境棧之中。

值得注意的是，有些編譯器在保留局部變量的值、傳值形式參數的值以及引用參數和常量引用參數的定義時，對於遞歸函數和非遞歸函數一視同仁，而有些編譯器則僅為遞歸函數保存上述內容。所以實際使用的編譯器將影響環境棧所需要的空間。 ^[2]