空間複雜度 | APCS Guide

簡介

空間複雜度（Space Complexity）是指演算法執行時所需的記憶體空間。一般來說，複雜度高的演算法會消耗更多的記憶體空間，反之，複雜度低的演算法則消耗較少的記憶體空間。

不過實際上在任何的競賽獲 APCS 考試中，空間複雜度的重要性通常不如時間複雜度來得高，因為大部分的題目都不會特別太嚴格的限制記憶體空間的使用，不過還是建議在解題時可以稍微了解一下空間複雜度的概念。

計算方式

空間複雜度的計算方式和時間複雜度類似，也是使用 big-O 表示法來表示。不過空間複雜度的計算方式通常比較簡單，只需要計算演算法執行時所需要的額外空間即可。

考慮以下的例子：

cin >> n;

vector<int> a(n); // 宣告一個長度為 n 的陣列

for (int i = 0; i < n; i++) {
    cin >> a[i]; // 讀入 n 個數字
}

這個程式碼的空間複雜度是 $O(n)$ ，因為宣告了一個長度為 $n$ 的陣列，而這個陣列所佔用的空間就是 $O(n)$ 。

再來考慮以下的程式碼：

cin >> n;

vector<vector<int>> a(n, vector<int>(n)); // 宣告一個 n x n 的二維陣列

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cin >> a[i][j]; // 讀入 n x n 個數字
    }
}

這個程式碼的空間複雜度是 $O(n^2)$ ，因為宣告了一個 $n \times n$ 的二維陣列，而這個陣列所佔用的空間就是 $O(n^2)$ 。

就是這麼的簡單，只要計算演算法執行時所需要的額外空間即可。