---
# System prepended metadata

title: 時間複雜度
tags: [演算法, 資料結構, leetcode觀念]

---

# 時間複雜度（Time Complexity）
常見的時間複雜度，若使用大Ｏ符號(Big-O Notation)表示，可簡單分為以下幾種
* O(1)：常數複雜度
* O(log n)：對數複雜度
* O(n)：線性複雜度
* O(n log n)：線性對數複雜度
* O(n²)：平方複雜度
* O(2^n)：指數複雜度
* O(n!)：階層複雜度

複雜度的排序(由左最低至右最高)
```
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)
```
</br>

![image](https://hackmd.io/_uploads/r1fDlaKQ1l.png)
    ∆ Big-O Notation - 參考來源：https://www.bigocheatsheet.com/
</br>

## 如何判斷複雜度 ?
平常在開發程式時，我們可以如何判斷，自己所撰寫的程式碼，是屬於哪一種時間複雜度？

簡單舉幾個例子

* <u>變數或陣列元素的讀取/賦值</u>，時間複雜度是最簡單的 `O(1)`
```
int[] array = new int[]{2, 3, 4, 5, 6};
System.out.println(array[0]);
```
</br>

* <u>二分搜尋法</u>，時間複雜度為 `O(log n)`，因為在最壞的情況下，也只需要執行陣列的一半大小
```
int[] array = new int[]{2, 3, 4, 5, 6};
public int binarySearch() {
    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>

* <u>走訪一個陣列</u>，時間複雜度為 `O(n)`，因為會依據輸入項(n)的大小，執行對應的次數(n)
```
int[] array = new int[]{2, 3, 4, 5, 6};
for(int value : array) {
    System.out.println(value);
}
```
</br>

* <u>雙層迴圈</u>，時間複雜度為 `O(n²)`，如：輸出二維陣列的內容，迴圈總執行次數為 `n * n`
```
int[][] twoDimensionalArray = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
};

for(int i=0;i<twoDimensionalArray.length;i++) {
    for(int j=0;j<twoDimensionalArray[i].length;j++) {
        System.out.println(twoDimensionalArray[i][j]);
    }
}
```

相同大小的三層迴圈，其時間複雜度為`O(n^3)`；四層為`O(n^4)`，以此類推

</br>

# 方法的複雜度
方法內可能不會只有單一的賦值/取值或是迴圈，也有可能會是包含一連串的組合處理。如：
```
public void test(int n) {
    int[] array = new int[n];
    int[][] twoArray = new int[n][n];

    for(int i=0;i<n;i++){
        array[i] = i+1;
    }

    for(int i=0;i<twoArray.length;i++) {
        for(int j=0;j<twoArray[i].length;j++) {
            twoArray[i][j] = array[i] * array[j];
        }
    }
}
```

陣列長度的宣告，時間複雜度為`O(1)`
```
int[] array = new int[n];
int[][] twoArray = new int[n][n];
```

array 一維陣列的走訪，時間複雜度為`O(n)`
```
for(int i=0;i<n;i++){
    array[i] = i+1;
}
```

twoArray 二維陣列的走訪，時間複雜度為 `O(n²)`
```
for(int i=0;i<twoArray.length;i++) {
    for(int j=0;j<twoArray[i].length;j++) {
        twoArray[i][j] = array[i] * array[j];
    }
}
```

test()方法的時間複雜度便可合記為
```
O(n²) + O(n) + O(1)
```

但由於多項式的特性，『當n越大時，最高項次為影響結果的最大因素』，
故test()方法的時間複雜度可省略記為
```
O(n²) 
```
</br>

# 遞迴的複雜度
前述例子的時間複雜度，皆為同一次方法呼叫內的處理，若以自己呼叫自己的遞迴寫法，其時間複雜度又為何？

以經典的<u>Fibonacci數列</u>為例
![Fibonacci (1)](https://hackmd.io/_uploads/rkXl2Bifke.jpg)
</br>

數列規則的部分可歸納為`n = (n-1) + (n-2)`，如：`13 = 8 + 5`、`21 = 13 + 8`等
![Fibonacci-2](https://hackmd.io/_uploads/H1o02riGyg.jpg)
</br>

程式的部分，則可以使用遞迴的方式實現
```
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));
    }
}

```
由於每個 `n` 皆是由前兩項的值加總而出( `n-1` 與 `n-2` ），故其時間複雜度會以2的次方開始，<u>呈指數級的方式成長</u>，時間複雜度則可記為 `O(2^n)`
</br>

### 記憶化的遞迴
此時，如果我們使用一個Map，為其加上記憶的機制，已計算過的`n`將不繼續遞迴加總，改由Ｍap中直接取出。

因省略了後續的遞迴，其時間複雜度會變為 `O(n)`

「每項只計算一次，不重複計算」
```
import java.util.HashMap;
import java.util.Map;

public class Fibonacci {
    Map<Integer, Integer>  map;
	
    public Fibonacci() {
        map = new HashMap<Integer, Integer>();
    }
	
    public int fibonacci(int n) {
        if (n <= 1) {
            return n; 
        }
        
        if(map.containsKey(n)) {
        	return map.get(n);
        }else {
        	int sum = fibonacci(n - 1) + fibonacci(n - 2);
        	map.put(n, sum);
        	return sum;
        }
        
    }

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

當然，若自己呼叫自己的次數有所差異，或是有著其他輔助的優化機制，其時間複雜度也就會有所改變，而非每種遞迴的時間複雜度皆是`O(2^n)` 或是 `O(n)`，仍以實際的執行步驟為主。
</br>

# 總結
時間複雜度是演算法中，相當重要的評估指標。

在相同輸入項的前提下，不同時間複雜度的演算法，執行所需耗費的時間皆有所差異。

而當輸入項的資料量級越大時，如：百萬、千萬級別以上，不同複雜度之間，所相差的時間也會更加顯著，開發團隊越需要確定每個常用的方法，其時間複雜度為何？以避免造成整個系統的效能低下。

下次開發程式時，不妨也試著思考看看，自己開發出的類別方法，是屬於哪一種時間複雜度？以及是否存在更低複雜度的優化寫法？
</br>

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

# 參考文獻
https://www.bigocheatsheet.com/

