1-4　內存的使用：空間復雜度

1-4-1　基本概念

程序算法在執行時會需要如下兩種空間：

（1）程序輸入／輸出所需空間。

（2）程序執行過程中暫時存儲中間數據所需的空間。

程序輸入與輸出的空間是必需的，所以可以不用計算，所謂的空間復雜度（Space Complexity）是指執行算法暫時存儲中間數據所需的空間，這里所謂的空間是指內存空間，也可以稱空間成本。

例如，程序執行時，有時需要一些額外的內存暫時存儲中間數據，以便可以方便未來程序代碼的執行，存儲中間數據所需的內存空間多少，就是所謂的空間復雜度。

假設有一個數列，內含一系列數字，此系列數字有一個是重復出現，我們要找出那個重復出現的數字，如下所示：

如果我們采用重復遍歷方法，這個方法的演算步驟如下：

（1）如果這是第一個數字，不用比較，跳至下一個數字。

（2）取下一個數字，將此數字和前面的數字比較，檢查是否有重復，如果有重復，則找到重復數字，程序結束。如果沒有重復，則跳至下一個數字。

（3）重復步驟（2）。

整個執行過程如下：

過程1：

取第一個數字1，不用比較。

過程2：

取下一個數字3，將3和前面的1做比較，沒有重復。

過程3：

取下一個數字4，將4和前面的1、3做比較，沒有重復。

過程4：

取下一個數字5，將5和前面的1、3、4做比較，沒有重復。

過程5：

取下一個數字2，將2和前面的1、3、4、5做比較，沒有重復。

過程6：

取下一個數字3，將3和前面的1、3、4、5、2做比較，發現重復。

上述過程雖可以得到解答，但是這個程序的時間復雜度是O（n2）。為了提高效率，我們可以使用額外的內存存儲中間數據，這個額外內存就是空間復雜度。

我們來看相同的數據，假設在遍歷每個數據時，就將此數據放在一個字典形式的哈希表（Hash Table），筆者將在第8章說明表的建立方式，如下所示：

上述的字典哈希表左邊字段Key是鍵值，右邊字段Value是該鍵值出現的次數，每次遍歷一個數值時，先檢查該值在字典是否出現，如果沒有就將此數值依哈希表規則放入字典內。如果遍歷到最后一個數值是3，可以發現該值出現過，這時就獲得我們所要的解答了。

上述時間復雜度則是O（n），效率大大提高了，而使用額外暫時存儲的字典哈希表空間是n，相當于空間復雜度：

S(n) = O(f(n))

有的人也將空間復雜度的f（ ）省略表示為：

S(n) = O(n)

而原先使用重復遍歷找尋重復數字的空間復雜度是O（1），但是時間復雜度則是O（n2），其實在兩者取舍時，時間復雜度是優先于空間復雜度，因為算法的時間成本更重要，相當于用內存空間去換取時間。

1-4-2　常見的空間復雜度計算

　空間復雜度場景1

使用Python語言，可以使用下列語法將x、y兩個數字對調。

在內存內部，實際上是使用下列方式執行數值對調。

這個算法使用一個tmp內存空間，整個空間復雜度是O（1），我們也可以將此空間復雜度稱為常數空間。

　空間復雜度場景2

暫時存儲中間數據所需的空間與數據規模n呈線性正相關。例如，前一小節我們使用字典哈希表找尋重復的數據，此字典哈希表所使用的內存空間與原先數據是呈線性正相關的，這時的空間復雜度是O（n），我們也可以將此空間復雜度稱為線性空間。

　空間復雜度場景3

如果一個輸入數據是n，算法存儲中間數據所需的空間是n*n，這時空間復雜度是O（n2），我們也可以將此空間復雜度稱為二維空間。

　空間復雜度場景4

程序實例ch1_1.py：筆者在計算階乘問題時介紹了遞歸式調用（recursive call），在該程序中雖然沒有很明顯地說明內存存儲了中間數據，不過實際上是有使用內存的，筆者將對其進行詳細解說，下列是遞歸式調用的過程。

在編譯程序中是使用棧（stack）處理上述遞歸式調用，這是一種后進先出（last in first out）的數據結構，筆者將在第5章說明棧的建立方式，下列是編譯程序實際使用棧的情形。

數據放入棧稱推入（push）。上述計算3的階乘時，編譯程序其實就是將數據從棧中取出，此動作的術語稱取出（pop），整個概念如下：

從上述執行結果可以看到，棧所需的內存空間和遞歸式的深度有關，如果遞歸式調用深度是n，則空間復雜度就是O（n）。