# 空間複雜度(Space Complexity)
空間複雜度(Space Complexity)是指執行演算法時，單一時間點所需耗費的記憶體空間

同樣可使用大Ｏ符號(Big-O Notation)表示<u>最差的執行情況</u>，即「執行所需耗費的最大記憶體空間」
</br>

# 常見情境
* 取陣列最大值

空間複雜度：`O(1)`

無論陣列大小為何，皆只需要一個 `max` 變數空間。即所耗費的記憶體不會根據輸入項 n 的變動而改變

public int findMax(int[] nums) {
    int max = nums[0]; 
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > max) {
            max = nums[i];
        }
    }
    return max;
}

</br>

* 建立陣列

空間複雜度：`O(n)`

依據輸入項 n 的值，建立對應大小的陣列，執行所需耗費的記憶體，會隨著輸入項 n 變動而改變

public int[] createArray(int n){
    int[] array = new int[n];
    for(int i=0;i<n;i++){
        array[i] = i;
    }
    
    return array;
}

</br>

* 建立二維陣列

空間複雜度：`O(n²)`

依據輸入項 n 的值，建立 n * n 的二維陣列，執行所需耗費的記憶體為輸入項 n 的平方

public int[][] createTwoArray(int n){
    int[][] array = new int[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            array[i][j] = i * j;
        }
    }
    
    return array;
}

</br>

# 遞迴與迴圈的空間複雜度差異
在相同需求的前提下，「使用遞迴實作」以及「使用迴圈實作」的空間複雜度，皆有所不同。
</br>

## 遞迴
遞迴是以自己呼叫自己的方式實作，執行所需的最大記憶體空間，是遞迴堆疊呼叫到最深層的時候，故其<u>空間複雜度與遞迴深度相關</u>。
</br>

### 以遞迴實作的Fibonacci數列
Fibonacci數列的第 n 項為前兩項(n-1、n-2)的加總

若以遞迴方式向下取值，每項皆會呼叫2次遞迴方法
例：

f(7) = f(7-1) + f(7-2)
－－－－－－－－－－－－－－
f(n) = f(n-1) + f(n-2)

而即便每項皆呼叫2次遞迴方法，但同一時間仍只會執行其一計算，`n-2`項需待`n-1`項計算完才會進入。且進入`n-2`項計算前，`n-1`已計算完的記憶體空間將會做釋放

故同一時間點所佔用的最大記憶體空間，仍與遞迴深度相關，其空間複雜度可記為`Ｏ(n)`

public class Fibonacci {
    public int fibonacci(int n) {
        if (n <= 1) {
            return n; 
        }
        
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        Fibonacci fibonacci = new Fibonacci();
        int n = 7;
        System.out.println("Fibonacci of " + n + " is: " + fibonacci.fibonacci(n));
    }
}

</br>

### 以遞迴實作的二分搜尋(Binary Search)
同理，二分搜尋法的最差執行次數為`O(log n)`，所對應的遞迴最大深度同為`log n`，故其空間複雜度可記為`O(log n)`

public static void main(String argv[]){
    int[] array = new int[]{2, 3, 4, 5, 6};
    int target = 5;
    int targetIndex = binarySearch(array, target, 0, array.length - 1);
}

public int binarySearch(int[] array, int target, int left, int right){
    if(left > right){
        // not found
        return -1;
    }
    
    int midIndex = (left + right) / 2;
    int midValue = array[midIndex];
    
    if(target > midValue){
        return binarySearch(array, target, midIndex + 1, right);
    }else if(target < midValue){
        return binarySearch(array, target, left, midIndex - 1);
    }else{
        return midIndex;
    }
}

</br>

## 迴圈
迴圈每次計算所使用的記憶體空間均會重建，迴圈進入時建立，迴圈結束時釋放

單以迴圈本身的控制而言，執行所需佔用的最大記憶體空間，不會根據輸入項 n 的變動而改變

但若在迴圈的邏輯區塊中，有使用Array、List等其他物件，執行所需佔用的最大記憶體空間，也將隨之增長
</br>

### 以迴圈實作的Fibonacci數列
僅單純使用`int`變數，而未使用`Array`或`List`等其他物件

因此，執行所需的最大記憶體空間，將不會隨著輸入項 n 的變動而改變，故其空間複雜度可記為`O(1)`

public class Fibonacci {
    public int fibonacci(int n) {
        if (n <= 1) {
            return n;  
        }
        
        int a = 0, b = 1;
        
        for (int i = 2; i <= n; i++) {
            int next = a + b;  
            a = b;              
            b = next;           
        }
        
        return b;  
    }

    public static void main(String[] args) {
        Fibonacci fibonacci = new Fibonacci();
        int n = 7;  
        System.out.println("Fibonacci of " + n + " is: " + fibonacci.fibonacci(n));
    }
}

</br>

### 以迴圈實作的二分搜尋(Binary Search)
於迴圈中，有使用`Array`物件。執行所需的最大記憶體空間，將隨著輸入項`array`的變動而改變，其空間複雜度可記為`O(n)`

public static void main(String argv[]){
    int[] array = new int[]{2, 3, 4, 5, 6};
    int target = 5;
    int targetIndex = binarySearch(array);
}

public int binarySearch(int[] array) {
    int left = 0;
    int right = array.length - 1;
    int target = 5;
    while(left <= right) {
        int midIndex = (left + right) / 2;
        int midValue = array[midIndex];

        if(target > midValue) {
            left = midIndex + 1;
        }else if(target < midValue) {
            right = midIndex - 1;
        }else {
            return midIndex;
        }
    }

    //not found
    return -1;
}

</br>

# 權衡(Trade Off)
一般來說，「空間複雜度(Space Complexity)」與「時間複雜度(Time Complexity)」兩者是互相`trade off`的

當追求更快的計算速度時，可以在程式多使用些記憶體來輔助計算，以加快計算速度與減少重複計算

反之，當記憶體資源不太充足時，可以多花費一些時間，來執行其計算
</br>

# 總結
綜合「空間複雜度(Space Complexity)」與「時間複雜度(Time Complexity)」兩者來看

大家通常會比較關注於「執行所需花費的時間」，也就是所謂的「時間複雜度(Time Complexity)」，而非「執行需佔用多少的記憶體空間」

源由是因現代硬體技術的快速發展，致使執行設備(PC/NB/手機等)的總記憶體量，皆遠超於「執行需佔用的記憶體空間」，只要不達到總記憶體的上限而造成OS的滿載，皆為可容忍的程度。且大多執行設備也能透過擴充的方式，增加總記憶體空間

除非，是在嵌入式設備、IOT主機板或雲端架構以量計價的訂閱中，才會特別關注所佔用的記憶體大小。

否則，多數情況仍以「執行所需花費的時間」為主，來討論其演算法的好壞。
</br>

>[!Tip]
文章內容皆為個人整理的觀點，以及整理後的個人想法，如內容有錯誤或疑慮的部分，歡迎提出討論，收到後會盡快修正！