# 【5-0】複雜度估計法

複雜度是我們用來分析程式碼效率的工具，分成「空間複雜度」、「時間複雜度」。

讓我們用簡單的例子來了解：

假設班上 50 位同學，要登記 3 次數學小考成績，我們在 [【3-3】二維陣列](https://hackmd.io/@LAfWxjSxRASps-4O_bppsA/rklX2HZHll) 學習過怎麼處理：

#include<bits/stdc++.h>

using namespace std;

int main(){
    int a[3][50];
    
    for(int i=0;i<3;i++){
        for(int j=0;j<50;j++){
            cin >> a[i][j];
        }
    }
    return 0;
}

你需要在紙上畫 150 格來登記成績，這就叫空間複雜度
你需要寫 150 次成績，這就叫時間複雜度

## 複雜度

通常，我們都是用最糟情況來估計複雜度，例如抽獎中頭獎，我們當然有可能第一抽就抽中，但最糟糕的情況是抽到最後一次才中。

所以，發明出了 Big O，標記為 $O()$，是上限的意思，該程式碼最糟糕的情況，不會超過這個限制。

### 空間複雜度

空間複雜度（Space Complexity） 是用來衡量程式在執行時「會額外佔用多少記憶體空間」的。

### 時間複雜度

時間複雜度（Time Complexity） 是用來衡量「當輸入變大時，程式需要花費多少步驟或時間」來完成執行。

## 估計法原則

* 忽略所有常數
* 忽略所有的非最高次項

像是 $n^3+2n^2+nlogn+123456$，用big O 標記為$O(n^3)$

也許在 $n = 1$ 的時候，我們的複雜度估計出來非常不準，但數字拉大來看，確實會接近於 $n^3$，而我們通常會認定 $n$ 很大，因為太小的 $n$ 就算估計不準，對程式運行的效率也不會有太大影響。

## 怎樣的複雜度才合理

原則上時間複雜度以 $10^8$ 為上限，超過就很難在 1 秒內跑完：空間複雜度的部分比較不會超標，大概抓 $10^8$ 是合理範圍。

## 常見的時間複雜度

這些方法在之後都會學習到，這邊先看看就好了：

| 表記法 | 常見情境範例 |
|-------------|-------------------------------|
| $O(1)$ | 常數操作、陣列取值 |
| $O(\log n)$ | 二分搜尋 |
| $O(n)$ | 單一迴圈、線性掃描 |
| $O(n \log n)$ | 快速排序、合併排序 |
| $O(n^2)$ | 巢狀雙迴圈 |
| $O(2^n)$ | 子集合枚舉、暴力遞迴 |
| $O(n!)$ | 全排列、暴力搜尋 |

## 複雜度估計練習

例題：

int a[1000]; // 複雜度O(1)
int a[n];    // 複雜度O(n)
int b[n][n]; // 複雜度O(n^2)

for(int i=0;i<n;i++){
    // 複雜度O(n)
}

for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        // 複雜度O(n^2)
    }
}

練習題：

int sum=0;
for (int i = 1; i < n; i *= 2) {
    sum+=i;
}

<details> <summary>解答</summary>
O(log n)
</details>
<br>

int f(int n){
    if(n == 0) return 0;
    if(n == 1) return 1;
    return f(n - 1) + f(n - 2);
}

<details> <summary>解答</summary>
O(2^n)
</details>
<br>

int l = 0, r = n - 1;
while (l <= r) {
    int m = (l + r) / 2;
    if (a[m] == x) break;
    else if (a[m] < x) l = m + 1;
    else r = m - 1;
}

<details> <summary>解答</summary>
O(log n)
</details>
<br>

int a = 5, b = 7;
int c = a * b + 10;

<details><summary>解答</summary>
O(1)
</details>
<br>

int sum = 0;
for(int i = 0; i < n; i++){
    sum += a[i];
}

<details><summary>解答</summary>
O(n)
</details>
<br>

for(int i = 1; i <= n; i++){
    int x = i;
    while(x > 1){
        x /= 2;
    }
}

<details><summary>解答</summary>
O(n log n)
</details>
<br>

void permute(vector<int>& nums, int l, int r) {
    if (l == r) return;
    for (int i = l; i <= r; i++) {
        swap(nums[l], nums[i]);
        permute(nums, l + 1, r);
        swap(nums[l], nums[i]);
    }
}

<details><summary>解答</summary>
O(n!)
</details>

---

聯絡方式：[e-mail]
最後編修時間：2025/07/04 子柚筆