# 時間複雜度（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>
∆ 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>為例
</br>
數列規則的部分可歸納為`n = (n-1) + (n-2)`，如：`13 = 8 + 5`、`21 = 13 + 8`等
</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/
Sign in with Wallet
Connect another wallet