複雜度分析

tags: Competitive Programming Note

本文已停止更新，新版請至 WiwiHo 的競程筆記

什麼是複雜度

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

$f(n)$ 和

$g(n)$，如果存在正數

$c$ 和

$n_0$，對於所有的

$n\ge n_0$ 都滿足

$f(n)\le cg(n)$，那麼我們說

$f(n)\in g(n)$。用圖形來講，就是把

$g(n)$ 乘上某個數字

$c$，使得

$cg(n)$ 的圖形在某個點之後就會一直在

$f(n)$ 上方。

複雜度表示函數的值如何隨著它的參數成長，換句話說，一個函數的複雜度是它的「成長率」，當一個函數的複雜度越大，就表示它成長得越快。一種簡單的估算方法是，把

$f(n)$ 除了最高次項以外都去掉，然後再把最高次項的係數丟掉，就是它的複雜度了，因為當

$n$ 變得很大，非最高次的項和係數對函數值的影響就不大了。例如

$f(n)=2n^2+n-1$ 的複雜度就是

$O(n^2)$，因為當

$n$ 逐漸變大，

$n$ 和

$-1$ 就對

$f(n)$ 的值影響不大了，複雜度給我們一種方式來表示「這個函數的結果大概是多少」。

而大家常聽到的時間複雜度和空間複雜度就是表示程式消耗的時間和空間如何成長，也是一種用來比較演算法好壞的方式，像是同樣的題目，有作法 A 和作法 B，它們的時間複雜度分別是

$O(n^2)$ 和

$O(n)$，我們就可以透過它們的時間複雜度，知道當

$n$ 到達一定的大小時，B 就會比 A 快得多，所以 B 是比 A 好的作法。

不過既然要拿複雜度來比大小，我們總得定義什麼是大、什麼是小。雖然直覺通常可以看得出來哪個比較好，但這邊還是給一下嚴謹定義：當

$n$ 趨近於無限大時，我們把

$\frac{g(n)}{f(n)}$ 分成三種狀況：無限大、收斂到

$0$ 和收斂到某個非零常數，首先第一種狀況很顯然會發生在

$g(n)$ 成長得比

$f(n)$ 快的狀況，這個時候我們知道

$O(g(n))$ 比

$O(f(n))$ 差（複雜度較大）；第二種狀況就是第一種狀況倒過來（

$\underset{x\to \mathrm{\infty }}{lim}\frac{1}{x}=0$），也就是

$O(g(n))$ 比

$O(f(n))$ 好（複雜度較小）；第二和三種狀況都是收斂到某個常數，根據定義，這表示

$O(f(n))\in O(g(n))$，但第三種況不一樣的是，你會發現

$\frac{f(n)}{g(n)}$ 也收斂到非零常數，所以

$O(g(n))\in O(f(n))$，顯然這表示

$O(f(n))=O(g(n))$，它們兩個是一樣的。

順帶一提，根據定義，

$f(n)\in O(f(n))$ 是成立的，例如

$2n^2+n-1\in O(2n^2+n-1)$ 是成立的，而且

$2n^2+n-1\in O(n^3)$ 也是成立的，所以複雜度的表示不是唯一的，但我們會選擇最小的那一個，然後用最簡單的方法把它表示出來，這樣做才是有意義的。沿用剛剛的例子，因為

$2n^2+n-1\in O(2n^2+n-1)=O(n^2)\in O(n^3)$，所以我們會說

$2n^2+n-1$ 的複雜度是

$O(n^2)$ 而不是另外兩個。

說了那麼多抽象的東西，打比賽的時候，實際的使用才是最重要的。當你對題目有想法時，你應該先估出時間複雜度，確認不會 TLE 才開始寫，確認的方法很簡單，把所有變數的最大值代入後，一秒大約可以跑

${10}^8$ 到

${10}^9$，這會依常數（待會會提到）而定，但差不多就是這個範圍，

${10}^8$ 是保守估計，通常會更快一些。至於空間複雜度，因為具體的空間不難算，你就把所有容器的空間大小加起來就是了，所以我覺得空間複雜度沒那麼實用 (?)，具體的時間不可能算出來，所以時間複雜度是很有用的。

一些用詞

• 常數：
  $O(1)$ 稱作常數複雜度。
• 線性：
  $O(n)$ 稱為線性複雜度，如果
  $f(n)\in O(n)$ 我們也說「
  $f(n)$ 的複雜度與
  $n$ 呈線性」。

STL 的複雜度

打比賽、做題目，都很難不用到 STL，所以我們勢必得要知道 STL 中各種操作的複雜度。

https://en.cppreference.com/w/ 這個網站中有所有 STL 裡的東西的說明，還有它們的複雜度，如果不知道複雜度或不知道怎麼用都可以到這裡去查，而且 CMS 左下角的 Documentation 點進去可以看到一樣的東西，所以只要比賽系統是 CMS，比賽時也可以看。

時間複雜度的範例

我們來看一些程式碼，算算看它們的時間複雜度。

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++){ //迴圈 1
    for(int j = 0; j < n - i - 1; j++){ //迴圈 2
        if(v[j] > v[j + 1]) swap(v[j], v[j + 1]);
    }
}
for(int i = 0; i < n; i++) cout << v[i] << " ";
cout << "\n";

這是用氣泡排序把

$v$ 中的數字由小排到大。首先，輸入、輸出的複雜度我們視為和字元數呈線性，而一個數字的位數依輸入限制而定，但頂多就

$18$、

$19$ 位（long long 的上限），所以輸入一個數字的複雜度我們視為是常數。

先看到一開始，我們輸入了一個數字

$n$，這麼做的複雜度是

$O(1)$，然後我們開了一個大小

$n$ 的 vector，這麼做的複雜度是

$O(n)$，接著我們又輸入

$n$ 個數字，這也是

$O(n)$，再來是一個巢狀迴圈，顯然迴圈 1 會跑

$n-1\in O(n)$ 次，而迴圈 2 在每一次迴圈 1 會跑

$n-i-1<n\in O(n)$ 次，而 swap 的複雜度是

$O(1)$，最後輸出

$v$ 的複雜度和輸入一樣，也是

$O(n)$，所以我們現在知道總時間複雜度是

$O(n^2)$。

你可能會想，為什麼

$n-i-1$ 複雜度是

$O(n)$？總複雜度不能更小嗎？所以我們再仔細觀察一下：迴圈 1 總共跑了

$n-1$ 次，在這之中的

$i$ 分別是

$0,1,2,...,n-2$，所以迴圈 2 在其中會跑的次數分別是

$n-1,n-2,...,1$，加起來就是

$\sum _{i=0}^{n-1}i=\frac{n(n-1)}{2}\in O(n^2)$，和剛剛得出的結果是一樣的。

比賽時估複雜度可以用一點直覺，如果你很懷疑直覺得出的，也可以像這樣認真確認一次，不過只要確保不會 TLE，複雜度算得比較大是沒有關係的。

再來看一個複雜點的例子：

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";

這會對於每一個輸入的

$n$ 個數字，輸出最近的在它左邊且比它大的數字，沒有的話就輸出 -1。（請先不要理會為什麼這樣做是對的。）

在這當中，用到了 STL 中的 stack，經過查文件得知，在這裡有做的所有 stack 的操作，做一次的時間複雜度都是

$O(1)$。

在氣泡排序的例子中，我們透過內外迴圈次數相乘的方法估算出複雜度，但是在這個例子中，外層的 for 迴圈每跑一次，內層的 while 迴圈會跑幾次，並不像上一個例子一樣是簡單地遞減，也不是只跟

$n$ 這個數字有關係。

既然不能知道它每一次會跑幾次，那就來算它總共會跑幾次吧。注意到輸入的

$n$ 個數字分別只會被 push 進 stack 恰一次，同樣地，也只會被 pop 恰一次，而內層的 while 迴圈每跑一次就會有一個東西被 pop 掉，所以我們可以知道，內層迴圈總共最多只會跑

$n$ 次，而外層迴圈也是總共

$n$ 次，所以總時間複雜度是

$O(n)$。

像這樣子計算總共的次數而得出的複雜度，稱為「均攤」。

之後的課程還會出現各式各樣的複雜度和各種計算，大家可以慢慢學習。

常數

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

如果你去看別人比賽的心得文，常常會看到「卡常」、「壓常」之類的詞彙，這些東西就是跟常數有關的，而且有時候還會是決定勝負的關鍵，所以，雖然算複雜度時我們說常數不重要，但實際上，還是有場合會是重要的。

前面有提到，在時間上，把所有變數的最大值代入複雜度，大約

${10}^8$ 到

${10}^9$ 算一秒。來舉個例子：

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

這裡有三層的巢狀迴圈，總時間複雜度是

$O(n)\times O(n)\times O(10)=O(10n^2)=O(n^2)$，我們在計算複雜度時把

$10$ 丟掉了，但那個

$10$ 不重要嗎？這要依

$n$ 的大小而定，這和我們在想複雜度時的概念相反，算複雜度丟掉常數是因為數字大的時候它不重要，但實際上則是數字越大時它越重要：如果

$n\le 10000$，那

$n^2={10}^8$，已經接近極限了，再乘上一個

$10$，就會變

${10}^9$，如果時限是 1 秒，這就有點緊了。

把常數變小的作法就叫「壓常」，如果題目的限制讓你一定要壓常，我們就說這個題目「卡常」，不過正常的題目是不會卡常的（\sout{台灣不正常的題目很多就是了}），所以還是可以放心地把常數丟掉，感覺很緊再仔細看看常數。

這個例子是屬於「看得到」的常數，還有的常數是「看不到」的，像是雖然加、減、乘、除、模的複雜度都是

$O(1)$，但除和模的所需時間其實是比其他的略久的，模

${10}^8$ 次沒有在 1 秒內跑完也是有可能發生，還有像 unordered_map、unordered_set 這種 hash table 雖然查詢、修改的複雜度都是

$O(1)$，但常數是很大的，有時候也會發生用

$O(\log n)$ 的 map 或 set 比 unordered 版快的狀況。

總而言之，常數是很捉摸不定的，有時候一個看起來久到爆的東西，也可能會因為編譯器優化而變得超快，這就只能慢慢累積經驗了，或是你也可以去看別人的心得文，看他們有沒有抱怨用了什麼而被卡常 (?)。

除了在時間會發生常數的問題，空間也是會有，不過因為空間的具體用量很好算，大概用了幾 byte 是算得出來的，所以被卡空間很容易就可以發現了。

練習

1. 請比較以下複雜度的大小關係：

   1. $O({\log }_{2}n)$ 和
      $O({\log }_{10}n)$
   2. $O(\log n)$ 和
      $O(\log n^2)$
   3. $O(n)$ 和
      $O(\log 2^n)$

2. 請計算以下程式碼的時間複雜度：

   1. code

      ​​​​​​​ int n;
      ​​​​​​​ cin >> n; //n >= 1
      
      ​​​​​​​ vector<int> a(n); 
      
      ​​​​​​​ //a[i] 的範圍在 [1, C]，C 是某個整數
      ​​​​​​​ for(int i = 0; i < n; i++) cin >> a[i]; 
      
      ​​​​​​​ int cnt = 0;
      ​​​​​​​ for(int i = 0; i < n; i++){
      ​​​​​​​     int t = a[i];
      ​​​​​​​     while(t){
      ​​​​​​​         cnt++;
      ​​​​​​​         t >>= 1;
      ​​​​​​​     }
      ​​​​​​​ }
      
      ​​​​​​​ cout << cnt << "\n";
      

   2. code

      ​​​​​​​ int n, k;
      ​​​​​​​ cin >> n >> k; //n,k >= 1
      
      ​​​​​​​ deque<int> dq;
      ​​​​​​​ vector<int> a(n), ans(n);
      
      ​​​​​​​ for(int i = 0; i < n; i++){
      ​​​​​​​     cin >> a[i];
      ​​​​​​​     while(!dq.empty() && dq.front() <= i - k){
      ​​​​​​​         dq.pop_front();
      ​​​​​​​     }
      ​​​​​​​     while(!dq.empty() && a[dq.back()] < a[i]){
      ​​​​​​​         dq.pop_back();
      ​​​​​​​     }
      ​​​​​​​     dq.push_back(i);
      ​​​​​​​     ans[i] = a[dq.front()];
      ​​​​​​​ }
      
      ​​​​​​​ for(int i = 0; i < n; i++) cout << ans[i] << " ";
      ​​​​​​​ cout << "\n";
      

   3. code

      ​​​​​​​ int n;
      ​​​​​​​ cin >> n;
      
      ​​​​​​​ set<int> s;
      ​​​​​​​ for(int i = 0; i < n; i++){
      ​​​​​​​     int t;
      ​​​​​​​     cin >> t;
      ​​​​​​​     s.insert(t);
      ​​​​​​​ }
      
      ​​​​​​​ for(int i : s) cout << i << " ";
      ​​​​​​​ cout << "\n";
      

3. 請計算以下程式碼的空間複雜度：

   1. code

      ​​​​​​​ int n;
      ​​​​​​​ cin >> n;
      
      ​​​​​​​ vector<vector<int>> a(n, vector<int>(n));
      ​​​​​​​ //...
      

   2. code

      ​​​​​​​​int n;
      ​​​​​​​​cin >> n;
      
      ​​​​​​​​for(int i = 0; i < n; i++){
      ​​​​​​​​    vector<int> a(n);
      ​​​​​​​​    //...
      ​​​​​​​​}
      

答案

1. 1. 由換底公式
      ${\log }_{\alpha }x=\frac{{\log }_{\beta }x}{{\log }_{\beta }\alpha }$ 可知，
      ${\log }_{10}n={\log }_{2}n\times \frac{1}{{\log }_{2}10}$，因此
      $O({\log }_{2}n)=O({\log }_{10}n)$。事實上只要
      $\log$ 的底數是常數，都可以根據換底公式透過乘上一個常數互相轉換，因此無論底數是哪個常數，都可以直接記為
      $O(\log n)$。
   2. $\log n^2=2\log n$，因此
      $O(\log n^2)=O(2\log n)=O(\log n)$。
   3. 同上，
      $O(\log 2^n)=O(\log n)$，因此
      $O(n)>O(\log 2^n)=O(\log n)$。
2. 1. 第 12 行處的 while 的終止條件是
      $t$ 為
      $0$，而
      $t$ 的初始值跟
      $a[i]$ 有關，這個迴圈每跑一次，就會執行一次 t >>= 1，也就是
      $t$ 會變成
      $\lfloor \frac{t}{2}\rfloor$，因此會跑
      $\lfloor {\log }_{2}a[i]\rfloor$ 次，所以總次數會是
      $\sum _{i=0}^{n-1}\lfloor {\log }_{2}a[i]\rfloor$ 次（也就是
      $cnt$ 最後的值），而
      $a[i]$ 的最大值是
      $C$，可以得出總複雜度為
      $O(n\log C)$。
   2. 與裡 stack 的例子相似，每個東西都只會被放進 deque 裡一次，同樣也只會被拿出來一次，因此總複雜度是
      $O(n)$。
   3. 這個程式碼做的事情非常簡單，就是把所有東西丟進 set 再把 set 裡的東西印出來而已。查表之後可以得知，insert 一次的複雜度是
      $O(\log sz)$，
      $sz$ 是當時 set 的大小，所以 insert
      $n$ 次的複雜度是
      $O(n\log n)$。
3. 1. vector 裡面有
      $n$ 個大小是
      $n$ 的 vector，因此空間複雜度是
      $O(n^2)$。
   2. 迴圈執行
      $n$ 次，每次會開一個大小是
      $n$ 的 vector，但是開始下一次前，這個 vector 會被丟掉，才會再開一個新的，因此空間複雜度是
      $O(n)$。