寫程式時，你可能會覺得：「這段程式碼跑起來很快啊！」
但如果 資料量暴增 100 倍，還能撐得住嗎？ ?
這就是 Big O 計算複雜度 的關鍵，它能幫你判斷演算法的極限，確保你的程式不會因為資料變大而變慢到炸裂。
什麼是 Big O？
Big O 主要衡量 輸入大小 (n) 增加時，演算法的時間或空間需求如何變化。
舉個例子：
這段程式碼無論 n 多大，都只做 一次運算，所以時間複雜度是 O(1)（常數時間）。
但如果你寫成這樣呢？
void printAllElements(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << endl;
}
}
這段程式碼會跑 n 次，所以時間複雜度是 O(n)（線性時間）。
常見 Big O 時間複雜度
? O(1) - 常數時間
不管 n 多大，運行時間都一樣。
範例：
int getFirstElement(vector<int>& arr) {
return arr[0]; // 只執行一次
}
適用場景：陣列索引存取、Hash Table 查找
? O(n) - 線性時間
輸入 n 越大，執行時間等比例成長。
範例：
? O(log n) - 對數時間
每次運算都將 n 縮小一半，常見於 二分搜尋。
範例：
? O(n log n) - 歷史最常見的排序時間
這是 最佳排序演算法（Merge Sort、Quick Sort） 的時間複雜度。
範例（Merge Sort）：
void mergeSort(vector<int>& arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right); // 合併
}
適用場景：快速排序、合併排序
? O(n²) - 超爛暴力法
當 n 增加，運行時間 呈平方成長。
範例（Bubble Sort）：
void bubbleSort(vector<int>& arr) {
for (int i = 0; i < arr.size(); i++) {
for (int j = 0; j < arr.size() - i - 1; j++) {
if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
}
}
}
適用場景：暴力解法、雙層迴圈搜尋、未最佳化的排序
? O(2ⁿ) - 指數時間
每多一個輸入，運行時間會 指數級成長，爆炸快！
範例（遞迴 Fibonacci）：
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
適用場景：遞迴解法（未優化）、組合問題（旅行推銷員問題）
? Big O 速查表
| 時間複雜度 | 表現 | 範例 |
|---|---|---|
| O(1) | ? 超快 | 陣列索引、Hash Table 查找 |
| O(log n) | ⚡ 高效 | 二分搜尋、Balanced Tree |
| O(n) | ?♂️ 線性增長 | 遍歷陣列、鏈結串列 |
| O(n log n) | ? 最佳排序 | Merge Sort, Quick Sort |
| O(n²) | ? 超慢 | 雙層迴圈、Bubble Sort |
| O(2ⁿ) | ? 指數爆炸 | 費氏數列、遞迴組合問題 |
? Big O 重要觀念
1️⃣ 忽略常數：
O(2n) ≈ O(n)、O(5 log n) ≈ O(log n)- 因為 n 越大，常數影響越小。
2️⃣ 只看最壞情況：
- 別只管平均情況，要考慮最糟時效能是否崩潰。
3️⃣ 空間複雜度 也要考慮！
- O(1) 空間（原地操作）比 O(n) 空間（額外記憶體）更高效。
? 總結
? Big O 是衡量演算法效能的標準，讓你避免效能災難。
? 盡量選擇 O(log n) 或 O(n) 的演算法，避免 O(n²) 以上的暴力法。
? 學會二分搜尋、快排、動態規劃，提升你的演算法功力！
問題：你遇過最慘的效能崩潰是什麼？留言分享！?
評論