複雜度

什麼是複雜度

複雜度是用來形容某個函數和它的參數的關係的東西，最常用的表示方法是 Big-O notation，正式的定義是：

對於兩個函數 和 ，如果存在正數 和 ，對於所有的 都滿足 ，那麼 。

用圖形來看，就是把 乘上某個數字 ，使得 的圖形在某個點之後就會一直在 上方。

複雜度表示函數的值如何隨著它的參數成長，換句話說，一個函數的複雜度是它的「成長率」，當一個函數的複雜度越大，就表示它成長得越快。一種簡單的算法是，把 中的所有低次項和係數去掉，就是它的複雜度了，因為當 變得很大，非最高次的項和係數對函數值的影響就不大了。例如 的複雜度就是 ，因為當 逐漸變大， 和 就對 的值影響不大了，複雜度給我們一種方式來表示「這個函數的結果大概是多少」。

而時間複雜度和空間複雜度就是表示程式消耗的時間和空間如何成長，也是一種用來比較演算法好壞的方式，像是同樣的問題，有作法 A 和作法 B，它們的時間複雜度分別是 和 ，我們就可以透過它們的時間複雜度，知道當 到達一定的大小時，B 就會比 A 快得多，所以 B 是比 A 好的作法。

既然要比大小，就要知道怎麼比。如果 的話就知道 （也就是 ），如果 而且 的話，就代表 。

順帶一提，根據定義， 是成立的，例如 是成立的，而且 也是成立的，所以複雜度的表示不是唯一的，但我們會選擇最小的那一個，然後用最簡單的方法把它表示出來，這樣做才是有意義的。沿用剛剛的例子，因為 ，所以我們會說 的複雜度是 而不是另外兩個。

常見用語：

• 線性複雜度： 稱為線性複雜度， 可以說成 對 呈線性（ is linear to ）。
• 常數複雜度：。

時間複雜度

時間複雜度就是用複雜度來描述程式執行的時間如何隨輸入的數字成長，例如：

1
2
3
4
5
6
7
8
9
10
11

int n;
cin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++) cin >> v[i];
for(int i = 0; i < n - 1; i++){
    for(int j = 0; j < n - i - 1; j++){
        if(v[j] > v[j + 1]) swap(v[j], v[j + 1]);
    }
}
for(int i = 0; i < n; i++) cout << v[i] << " ";
cout << "\n";

這是用 Bubble sort 排序一個陣列，輸入或輸出一個數字是時間複雜度是 ，所以輸入的部分需要花 的時間，而第 5 到 9 行的巢狀迴圈，最裡面的第 7 行總執行次數是 ，最後輸出也要花 的時間。這個 是所有部分當中花費時間最久的，也稱為瓶頸，所以這個程式的總時間複雜度是 。

像這種迴圈執行次數很好算的，時間複雜度的算法很簡單，就是巢狀的迴圈執行次數相乘、非巢狀的取最大，不過也會有次數不好算的，像是：

1
2
3
4
5
6
7
8
9
10
11
12
13

int n;
cin >> n;

stack<int> st;
for(int i = 0; i < n; i++){
    int t;
    cin >> t;
    while(!st.empty() && st.top() <= t) st.pop();
    if(st.empty()) cout << "-1 ";
    else cout << st.top() << " ", st.pop();
    st.push(t);
}
cout << "\n";

這個是輸入一個陣列，然後對每一個元素輸出它左邊第一個比它大的數字（用單調隊列），沒有就輸出 -1。第 8 行的 while 執行次數是不固定的，所以不能用巢狀迴圈次數相乘的方法。注意到每執行一次都會從 stack pop 掉一個東西，所以我們可以知道，執行次數也就是 pop 次數，一定不超過 push 次數，而 push 次數顯然是 ，得出這個 while 的總執行次數是 ，總時間複雜度是 。

真正的執行時間

程式執行的時間會受到很多其他因素影響，所以是不能從時間複雜度知道實際的執行時間確切是多少的，但可以估算。估算的方法是，把數字都代進複雜度後，得到的數字大約 是一秒。

常數

前面提到複雜度的估算方法是把低次項和常數全部拿掉，而且不管把複雜度乘上任何常數，都還會是一樣的東西，因為它對函數值影響不大，但是，這個常數真的不重要嗎？

舉個例子：

1
2
3
4
5

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        for(int k = 0; k < 10; k++) /*...*/;
    }
}

這裡有三層的巢狀迴圈，總時間複雜度是 ，我們在計算複雜度時把 丟掉了，但那個 不重要嗎？這要依 的大小而定，這和我們在想複雜度時的概念相反，算複雜度丟掉常數是因為數字大的時候它不重要，但實際上是數字越大時它越重要：如果 ，那 ，已經接近極限了，再乘上一個 ，就會變 ，如果時限是 1 秒，這就有點緊了。

這個例子是屬於「看得到」的常數，還有的常數是「看不到」的，像是雖然加、減、乘、除、模的複雜度都是 ，但除和模的所需時間其實是比其他的略久的，模 次沒有在 1 秒內跑完也是有可能發生，還有像 unordered_map、unordered_set 這種 hash table 雖然查詢、修改的複雜度都是 ，但常數是很大的，有時候也會發生用 的 map 或 set 比 unordered 版快的狀況。

總而言之，常數是很捉摸不定的，有時候一個看起來久到爆的東西，也可能會因為編譯器優化而變得超快，這就只能慢慢累積經驗了。

空間複雜度

空間的狀況比時間單純許多，因為空間用了多少通常很好算，也可以用 sizeof() 來看用了多少空間。只是需要記得一些容器的空間常數比較大，例如空 deque 的大小比空 vector 大。