---
# System prepended metadata

title: 時間複雜度

---

# 時間複雜度
## 簡單計算方式
計算每段迴圈的運行次數，加總即為這段程式的時間複雜度
## 複雜度表示
我們會以 $O(\ )$ 表示時間複雜度
Big-O 只顯示演算法執行次數部分的==最大指數、最高次方數或是常數1==，例如：$(123n+45)$次 $\rightarrow$ $O(n)$

## 常見複雜度計算

||$O(1)$||
```cpp
cout << "Hello World";
```
||$O(n)$||
```cpp
for(int i = 0; i < n; i++){
    cout << i << ' ';
}
```
||$O(n^2)$||
```cpp
for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        cout << "*";
    }
    cout << "\n";
}
```

## 複雜度大小比較
令 $n = 10^8$
$O(1) < O(log n) < O(n) \approx 1$ 秒 $< O(nlogn) < O(n^2) < O(2^n) < O(n!)$
