我們昨天介紹了什麼是時間複雜度，那今天來看什麼是空間複雜度吧 !
☆*: .｡. o*(≧▽≦)*o .｡.:*☆

什麼是空間複雜度?

空間複雜度 (Space Complexity)是用來衡量演算法在執行過程中，隨著資料量 n 的增加，所需的記憶體空間會如何成長，和時間複雜度 (Time Complexity)表示方法一樣通常都為 Big O

!! 但嚴格上來說空間複雜度是分為兩部份 :
空間複雜度 = 輸入空間 (Input Space)+輔助空間 (Auxiliary Space)

輸入空間 (Input Space) : 輸入資料所佔的空間
輔助空間 (Auxiliary Space): 演算法執行過程中所額外使用的暫存空間，包括 :

• 額外宣告的變數
• 執行過程中新建立的陣列或資料結構
• 函式呼叫時系統自動使用的堆疊空間（Stack Space）
  • 在遞迴演算法中尤其重要，因為每次遞迴呼叫都會新增一層堆疊空間

但要注意的是，我們平常說的「這個演算法空間複雜度是 O(1)」嚴格上指的是「這個演算法輔助空間是 O(1)」
因為輸入資料要佔多少空間是看資料量決定的，所以比較演算法效率時，不會把輸入空間也算進去
接下來用幾個例子來講解 :

範例一 : O(1) — 常數空間

int findMax(int arr[], int n) {
    int maxVal = arr[0];      // 額外用了 1 個變數
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }
    return maxVal;
}

輸入空間 : arr佔 O(n)
輔助空間: 只用到 maxVal、i 兩個變數，不會隨 n 變多而增加，所以是 O(1)

範例二 : O(n) — 線性空間

int* reverseArray(int arr[], int n) {
    int* result = new int[n];   // 建立了一個大小為 n 的新陣列
    
    for (int i = 0; i < n; i++) {
        result[i] = arr[n - 1 - i];
    }
    return result;
}

函式把原陣列arr反轉後，放到一個新陣列result回傳

輸入空間: arr佔 O(n)
輔助空間:額外建立的 result 陣列，大小也是 n，所以是 O(n)

範例三:遞迴的空間複雜度,很容易被忽略的地方

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

這個函式本身沒有宣告陣列，乍看之下輔助空間好像是 O(1),但遞迴呼叫本身會佔用空間——每呼叫一次 factorial，系統就會在記憶體的「呼叫堆疊(Call Stack)」上多疊一層，記錄這一層要做的事跟要傳回哪裡。
這部分的堆疊空間也算在輔助空間 裡，不是在輸入資料的空間。

數學推導 :遞迴呼叫堆疊怎麼算?

以 factorial(4) 為例，展開呼叫的過程會是這樣:

factorial(4)
  → factorial(3)
      → factorial(2)
          → ...
              → factorial(1)   ← 到這裡才開始往回傳值

每往下呼叫一次，堆疊就多疊一層，一路疊到 factorial(1) 才停止,所以疊的層數(深度)是:

總共疊了 n 層,每一層佔用的空間是固定的(常數),假設每層佔用空間為 c,則總空間為:

所以factorial(n) 雖然程式完全沒有宣告陣列，但輔助空間是 O(n)，而不是 O(1)，這邊可以再多加注意喔 !

參考資料

1. https://www.reddit.com/r/learnpython/comments/lbh5oz/whats_the_difference_between_auxiliary_space_and/?tl=zh-hant
2. https://www.geeksforgeeks.org/dsa/g-fact-86/
3. https://zh.wikipedia.org/wiki/%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6
4. Hello 算法 https://www.hello-algo.com/zh-hant/chapter_computational_complexity/space_complexity/#4-o2n