---
# System prepended metadata

title: 單元一 時間複雜度（Time Complexity）

---

# 單元一 時間複雜度（Time Complexity）

時間複雜度是算法分析中的一個重要概念，用於衡量**一個算法執行所需時間的量度。** 
當我們討論一個算法的時間複雜度時，我們通常會關注它的執行時間如何隨著輸入的規模增加而增長，因此可用於**衡量演算法執行速度快慢去評判設計的好壞與否。**
本文將介紹時間複雜度的基本概念及一些簡化的方法。

## 簡介
時間複雜度是衡量算法執行時間的一個重要概念。此刻的時間指的是**執行步數**。當每行程式碼被執行一次，我們記為一個步驟。以下我們以簡單的程式碼為例。
```c++ = 
string welcome = "Hello World!"
cout << welcome << endl;
```
在上述程式碼中，宣告字串welcome視為一個步驟，執行輸出也是一個步驟，故總共執行了兩個步驟。如果整段程式碼都沒有用到迴圈或遞迴，則步驟次數通常以 1 表示，至於原因後續內容會提到。
```c++ = 
int n;
cin << n;
for(int i = 0 ; i < n ; i ++){
cout << "Hello World!" << endl;
}
```
這段則是從 1 迭代到 n 的迴圈，步驟次數應為 n+2，但在 n 趨近於無限大時，我們會盡量化簡時間複雜度，省去係數並只採最高次方項，因此這段程式碼的時間複雜度為 O(n) 。

時間複雜度的重要性在於可以幫助我們預測算法的效率和性能，通常用**大 O 符號（Big O notation）來表述**。

## 大O符號（Big O notation）

大O符號（O）是一種用於描述算法時間複雜度的符號表示法，用於表示算法執行時間的上界。當我們說一個算法的時間複雜度為O(f(n))時，意味著該算法的執行時間不會超過某個與f(n)相關的函數。換句話說，它表示當輸入規模增加時，算法的執行時間不會增長得比f(n)更快。

### 常見的大 O 符號

#### O(1)：常數時間複雜度。
無論輸入規模大小如何，算法的執行時間都是固定的。
（1可替換為任何常數。）
##### Ex、判斷一個數值的奇偶
``` c++=
int main() {
    int num;
    cin >> num;
    if (num % 2 == 0) {
        cout << "這個數是偶數" << endl;
    } 
    else {
        cout << "這個數是奇數" << endl;
    }
    return 0;
}
```
此程式的時間複雜度是 O(1)。
無論輸入的數值位數有多少，該程式只執行一次運算（num % 2 == 0）。即使位數很大，執行的操作步數仍相同，執行時間也不會增加。



#### O(log n)：對數時間複雜度。
此處的log n算法的執行時間與輸入規模的對數成正比。
##### Ex、二分搜尋法（Binary Search）

搜尋過程從陣列的中間元素開始，如果中間元素正好是要搜尋的元素，則搜尋過程結束。

如果某一特定元素大於或者小於中間元素，則在陣列大於或小於中間元素的那一半中搜尋，而且跟開始一樣從中間元素開始比較。

如果在某一步驟陣列為空，則代表找不到。這種搜尋演算法每一次比較都使搜尋範圍縮小一半。
![時間複雜度](https://hackmd.io/_uploads/Sy33VvBy0.jpg)



``` C++=
// 二分搜尋法
int binary_search(const vector<int>& array, int target) {
    int left = 0;
    int right = array.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (array[mid] == target) {
            return mid; // 找到目標，返回索引
        } else if (array[mid] < target) {
            left = mid + 1; // 目標在右半部分
        } else {
            right = mid - 1; // 目標在左半部分
        }
    }

    return -1; // 沒有找到目標
}

int main() {
    vector<int> array = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target = 11;

    int index = binary_search(array, target);

    if (index != -1) {
        cout << "目標 " << target << " 在陣列中的索引為: " << index << endl;
    } else {
        cout << "目標 " << target << " 不在陣列中" << endl;
    }

    return 0;
}

```
每次迭代，搜索範圍縮小一半，因此執行時間以對數增長。因此，對於大小為n的已排序陣列，二分搜尋法的時間複雜度是 O(log n)。

#### O(n)：線性時間複雜度。
算法的執行時間與輸入規模成正比。

##### Ex、簡易搜索（Sequential Search）
透過經歷整個陣列的元素搜索目標。
``` c++=
#include <iostream>
#include <vector>

// 簡易搜尋法
int simple_search(const std::vector<int>& array, int target) {
    for (int i = 0; i < array.size(); ++i) {
        if (array[i] == target) {
            return i; // 找到目標，返回索引
        }
    }
    return -1; // 沒有找到目標
}

int main() {
    std::vector<int> array = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target = 11;

    int index = simple_search(array, target);

    if (index != -1) {
        std::cout << "目標 " << target << " 在陣列中的索引為: " << index << std::endl;
    } else {
        std::cout << "目標 " << target << " 不在陣列中" << std::endl;
    }

    return 0;
}
```
在最壞情況下，當目標不在陣列中時，我們需要遍歷整個陣列，因此簡易的線性搜索法的時間複雜度為 O(n)。


:::success
以上的層級對於演算法來說是最為理想的狀態，一般來說，我們會希望一個演算法至少能比 O(n²) 還要快。
:::

#### O(n²)：平方時間複雜度。
算法的執行時間與輸入規模的平方成正比。
##### Ex、氣泡排序法(Bubble Sort)

![bubble_sort](https://hackmd.io/_uploads/BJ9Uc_EC6.png)

```c++=

// 氣泡排序
void bubble_sort(vector<int>& array) {
    int n = array.size();
    int temp;
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (array[j] > array[j + 1]) {
                temp = array[j];
                arrar[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

int main() {
    vector<int> array = {12, 3, 6, 8, 1, 17, 5};

    bubble_sort(array);

    cout << "排序後的陣列: ";
    for (int num : array) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}
```
氣泡排序法的主要是通過重複經過待排序的元素，每次比較相鄰的兩個元素，如果它們的順序錯誤則交換它們，直到整個數組都是按照順序排列。整個排序過程的時間複雜度是O(n²)。

#### O(mⁿ)：指數時間複雜度。
算法的執行時間與輸入規模的指數成正比。
##### Ex、嵌套遍歷二維數組
```c++=
int main() {
    vector<int> array = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    // 一維數組的兩次迴圈遍歷
    for (int i = 0; i < array.size(); ++i) {
        cout << array[i] << " "; // 單次遍歷，O(1)
    }
    cout << endl;

    return 0;
}
```
這個程式示例中，我們使用了嵌套迴圈遍歷二維數組，其時間複雜度是O(mⁿ)，其中m是二維數組的行數，n是二維數組的列數。第一次迴圈用於遍歷行，第二次迴圈用於遍歷列，每次遍歷中的每個操作都是常數時間複雜度。


## 最壞/平均情況時間複雜度
相同大小的不同輸入值仍可能造成演算法的執行時間不同，因此我們通常使用演算法的**最壞情況複雜度**，記為 T(n) ，定義為任何大小的輸入 n 所需的最大執行時間。另一種較少使用的方法是**平均情況複雜度**，通常有特別指定才會使用。



## 加速程式執行的秘訣？


在C++中，文字被輸出前，它會先到一個「緩衝區」，到一個特定的時間再一次輸出出去，因為分次輸出是很耗資源的事。強制將緩衝區的資料釋放（輸出）的動作稱為 flush。在 stdio，把標準輸出流 flush 是 fflush(stdout)，而在 iostream，這個動作是 cout << flush。

緩衝區的釋放是決定效率的關鍵因素。printf 是不會自動釋放緩衝區的，scanf 也不會強制釋放，但 cin 就會了，因為在要求使用者輸入之前，應該先讓使用者看見先前輸出的文字。若要提升效率，則要取消強制釋放：
:::success
cin.tie(0);
:::
tie 是 ios 的一個方法，也就是說，cin、cerr、cout 都有這個方法，cin 和 cerr 預設是有 tie cout 的，所以在使用 cin、cerr 時，cout 的緩衝區會先被釋放，tie(0) 就可以解除。

此外，C++ 中有兩種輸入輸出系統：stdio 和 iostream，C++ 會讓 iostream 和 stdio 同步，來避免混用時發生無法預期的問題，所以這個額外的動作會造成效率降低，而把同步解除會效率增加。用了以下這個之後，iostream 和 stdio 不能混用。
:::success
ios_base::sync_with_stdio(false);
:::

## 實作練習
Q：請求出此段程式的 T(n)

```c++=
int find_max(const vector<int>& arr) {
    int max = arr[0];
    for (int i = 1; i < arr.size(); ++i) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

int main() {
    vector<int> arr = {3, 7, 2, 8, 1, 9, 4, 6, 5};
    int max_element = find_max(arr);
    cout << "最大元素: " << max_element << endl;
    return 0;
}

```
:::spoiler Ans：
O(n)
:::


## 結語

本篇講義簡約講述了時間複雜度的觀念。時間複雜度作為我們評估演算法效能的重要指標之一，在後續學習演算法及應用上扮演十分重要的角色。尤其在訓練競程時，如何優化時間複雜度更是至關重要。透過對時間複雜度的分析，我們可以更好地理解不同演算法之間的效能差異，並選擇最適合特定應用場景的演算法。
希望這份講義能夠幫助各位深入理解時間複雜度的概念，提升演算法分析和設計能力，並在實際應用中取得更好的效果。





