# 單元一 時間複雜度（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）
搜尋過程從陣列的中間元素開始，如果中間元素正好是要搜尋的元素，則搜尋過程結束。
如果某一特定元素大於或者小於中間元素，則在陣列大於或小於中間元素的那一半中搜尋，而且跟開始一樣從中間元素開始比較。
如果在某一步驟陣列為空，則代表找不到。這種搜尋演算法每一次比較都使搜尋範圍縮小一半。
``` 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)
```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)
:::
## 結語
本篇講義簡約講述了時間複雜度的觀念。時間複雜度作為我們評估演算法效能的重要指標之一，在後續學習演算法及應用上扮演十分重要的角色。尤其在訓練競程時，如何優化時間複雜度更是至關重要。透過對時間複雜度的分析，我們可以更好地理解不同演算法之間的效能差異，並選擇最適合特定應用場景的演算法。
希望這份講義能夠幫助各位深入理解時間複雜度的概念，提升演算法分析和設計能力，並在實際應用中取得更好的效果。
Sign in with Wallet
Connect another wallet