# 複雜度 #### Author: PixelCat ---- ## 概要 1. 什麼是複雜度 2. 如何計算複雜度 3. 複雜度的記號 4. 為何複雜度重要 --- ## 什麼是複雜度 ---- 競程中的複雜度可以指： 1. 時間複雜度 2. 空間複雜度 其中時間複雜度更常被討論 ---- 舉個例子   誰要跑比較久? ---- 這樣呢?  那要看N是多少 ---- 程式(演算法)執行需要時間 這個時間常常跟輸入的數值有關 我們想知道一支程式(大概)要跑多久 ---- **複雜度**的功能有 1. 估計需要的時(空)間與輸入大小的關係 2. 輸入變大的時候所需時(空)間增長多快 --- ## 複雜度計算 ---- 就時間複雜度而言 我們難以真的計算輸入變大會變慢幾秒 退而求其次，我們計算 > 輸入大小與「基本操作數」的關係 ---- ### 基本操作? 最簡單的操作，快如閃電 ---- ```cpp= a * b //OWO a % b //OWO ``` 加減乘除取模都是基本操作 ```cpp= arr[i] = x; //OWO ``` 陣列存取也是基本操作 ```cpp= if(a == b) {} //OWO ``` 條件判斷同樣是基本操作 ---- ```cpp= for(int i = 0; i < 10000; i++) {} //NOPE ``` 迴圈不是，他可能執行好多好多次 ```cpp= double PI = acos(-1); //OWO sort(arr, arr + n); //NOPE ``` [呼叫函數](https://hackmd.io/@PixelCat/rk7moqETd#/)是嗎? :::spoiler 那要看函數裡面藏了什麼 <div style="font-size:20px; line-height: normal;"> <p> 事實上，在我的電腦上，cos()大約: <ul> <li>比乘法慢200倍</li> <li>比亂數產生(mt19937)慢20倍</li> <li>比模運算慢10倍</li> </ul><br/><br/> 不過因為它的計算時間仍然是一個常數<br/> 所以歸類在基本操作之一 </p> </div> ::: ---- 於使我們可以算算輸入是某個數字的時候 程式會執行多少個基本操作 --- ## 來幾顆{栗|例}子 :::spoiler 好ㄘ  ::: ---- 幾個基本操作? ```cpp= a = a * a; a = (a + 5) % 1000; ``` $3$ 個 ---- 幾個基本操作? ```cpp= for(int i = 0; i < N; i++){ a[i] = a[i-1] + 10; } ``` $N$ 個 ---- 幾個基本操作? ```cpp= for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ t += a[i] * a[j]; } } ``` $N^2$ 個 ---- 幾個基本操作? ```cpp= for(int i = 0; i < N; i++){ for(int j = i + 1; j < N; j++){ t += a[i] * a[j]; } } ``` $\dfrac{1}{2}N^2 - \dfrac{1}{2}N$ 個 ---- 幾個基本操作? ```cpp= for(int m = 0; m < (1 << N); m++){ for(int i = 0; i < N; i++) for(int j = 0; j < N; j++){ if( (m & (1 << i)) && (m & (1 << j)) ) t++; } } ``` $N^2\,2^N$ 個 ---- 幾個基本操作? ```cpp= int f(int x){ if(x == 0) return 0; return x + f(x-1); } f(N) ``` 也是 $N$ 個 ---- 幾個基本操作? ```cpp= void f(int x){ if(x == 1) return; for(int i = 0; i < x; i++){ a[i]++; } f(x/2); } f(N) ``` 第一層遞迴 $N$ 個，之後一直砍一半 $N + \dfrac{N}{2} + \dfrac{N}{4} + \cdots = 2N$ 個 ---- 我們會算複雜度了，好耶 --- ## 記號與表示法 ---- > 我跟你說，我的程式複雜度是 > $\dfrac{20}{15}N^4 + 3N^3 - \dfrac{7}{5} N^2 - 5N + 31$ > 所以........ 你說完我都睡著了又醒了 ---- 有必要嗎? $N$ 越來越大的時候... ---- $$ \begin{split} N &= 1000 \\ N^2 &= 1000000 \\ \frac{3}{2}N^2 &= 1500000 \\ 7N^2 &= 7000000 \end{split} $$ 有沒有係數好像差不多? ---- $$ \begin{split} N &= 1000 \\ N^2 &= 1000000 \\ N^2 + N &= 1001000 \\ N^2 + 3N + 45 &= 1003045 \end{split} $$ 有沒有低次項好像差不多? ---- 於是我們會捨棄係數、留下最高的次方 例如：$\dfrac{5}{2}N^2 + 2N + 64 \in \mathcal{O}(N^2)$ ---- 這個 $\mathcal{O}$ 叫做Big-O $f(n) \in \mathcal{O}(g(n))$ 代表： $n$ 越來越大的時候，$f(n)$ 不會長得比 $g(n)$ 還快 換句話說，$g(n)$ 可以大概代表 $f(n)$ 有多大、成長多快 ---- 我們時常用Big-O來表示複雜度 類似的符號還有 $\Theta$、$\Omega$ 但是相對不常見，請 [左轉](https://zh.wikipedia.org/wiki/%E5%A4%A7%CE%A9%E7%AC%A6%E5%8F%B7) [維基](https://zh.wikipedia.org/wiki/%E5%A4%A7%CE%98%E7%AC%A6%E5%8F%B7) --- ## 來幾顆{栗|例}子．再 :::spoiler 好ㄘ好ㄘ  ::: ---- 時間複雜度是多少? ```cpp= a = a * a; a = (a + 5) % 1000; ``` $\mathcal{O}(1)$，也叫做「常數」 ---- 時間複雜度是多少? ```cpp= for(int i = 0; i < N; i++){ a[i] = a[i-1] + 10; } ``` $\mathcal{O}(N)$，也叫做「線性」 ---- 時間複雜度是多少? ```cpp= for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ t += a[i] * a[j]; } } ``` $\mathcal{O}(N^2)$ ---- 時間複雜度是多少? ```cpp= for(int i = 0; i < N; i++){ for(int j = i + 1; j < N; j++){ t += a[i] * a[j]; } } ``` 也是 $\mathcal{O}(N^2)$ ---- 時間複雜度是多少? ```cpp= for(int m = 0; m < (1 << N); m++){ for(int i = 0; i < N; i++) for(int j = 0; j < N; j++){ if( (m & (1 << i)) && (m & (1 << j)) ) t++; } } ``` $\mathcal{O}(N^2\,2^N)$ ---- 時間複雜度是多少? ```cpp= int f(int x){ if(x == 0) return 0; return x + f(x-1); } f(N) ``` $\mathcal{O}(N)$ ---- 時間複雜度是多少? ```cpp= void f(int x){ if(x == 1) return; for(int i = 0; i < x; i++){ a[i]++; } f(x/2); } f(N) ``` 依然是 $\mathcal{O}(N)$ ---- 好耶 --- ## 為何複雜度? ---- 算這個有什麼用? 估計操作數(執行時間)能幹嘛? ---- _Codeforces 1549E_ 時(空)間限制  輸入大小限制  ---- _AtCoder ABC207E_ 時(空)間限制  輸入大小限制  ---- 一般情況下 電腦每秒大約可以執行 $10^8$ 個基本操作 把題目給的數值限制代入你的複雜度 比 $10^8$ 還低? 你的程式很可能一秒內跑得完 太高了? 可能會<font color="#FC6">TLE</font>，有沒有更快的演算法? ---- ### 常見的時間複雜度與輸入限制 | 複雜度 | 輸入範圍 | |:--------------------- |:--------------- | | $\mathcal{O}(1)$ | $N\leq 10^{18}$ | | $\mathcal{O}(\log N)$ | $N\leq 10^{18}$ | | $\mathcal{O}(N)$ | $N\leq 10^7$ | | $\mathcal{O}(N\log N)$ | $N\leq 10^6$ | ---- ### 常見的時間複雜度與輸入限制 | 複雜度 | 輸入範圍 | |:--------------------- |:--------------- | | $\mathcal{O}(N^2)$ | $N\leq 3000$ | | $\mathcal{O}(N^3)$ | $N\leq 300$ | | $\mathcal{O}(2^N)$ | $N\leq 20$ | | $\mathcal{O}(N!)$ | $N\leq 13$ | ---- 那空間呢? 每題都有點不一樣，通常可以用 $10^6$~$10^7$ 個`int` 大部分題目不會刻意要求空間要夠小 ---- 了解複雜度之後 我們就可以在寫程式之前先估計自己的演算法是不是夠快 就可以避免寫完才發現穩妥妥的<font color="#FC6">TLE</font> ---- 不過複雜度畢竟是估計 複雜度夠好不保證一定能過 複雜度太差不代表一定沒救 假如只差一點點也都值得一試 --- ## 卡常? ---- 卡常數是另外一個相關的問題 前面說複雜度會忽略係數 但在複雜度很接近上限的時候，可能執行時間乘一個常數就會從<font color="#8F6">AC</font>變<font color="#FC6">TLE</font> ---- ### 避免? 1. 改善實作細節 2. 避免不必要的高科技 3. ~~毒瘤~~ --- ## 以上 ---- 一開始可能不習慣先計算複雜度再下手 容易花式<font color="#FC6">TLE</font>還不知道為什麼 我就曾經在 $N, Q\leq 10^5$ 的題目使用 $\mathcal{O}(NQ)$的做法，還以為是自己常數太大 ---- 複雜度越到後面會顯得越重要 同時也與經驗多寡高度相關 ---- > 早く！もっと早く！！！ > — 桐谷和人