空間複雜性

程式的空間複雜性（space complexity）是指運行完一個程式所需要的記憶體大小，是計算機算法分析的重要概念之一，可以利用空間複雜性來估算一個程式所能解決的問題的最大規模。

基本介紹

• 中文名：空間複雜性
• 外文名：space complexity
• 實質：所需的存儲空間資源耗費量的估計
• 研究背景：確定程式性能
• 組成：指令空間、數據空間、環境棧空間
• 套用學科：計算機科學、建築學、測繪科學
• 簡介：運行完一個程式所需要的記憶體大小

簡介

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

研究背景

程式性能

程式性能（program performance），是指運行一個程式所需要的記憶體大小和時間。

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

研究原因

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

·如果程式將要運行在一個多用戶計算機系統中，可能需要指明分配給該程式的記憶體大小。

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

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

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

空間複雜性的組成

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

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

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

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

指令空間

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

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

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

·目標計算機

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

空間複雜性示例

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

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

數據空間

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

環境棧

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

·返回地址。

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

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

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

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