複雜度 - HackMD

--- title: 複雜度 # 簡報的名稱 tags: 7th 教學 # 簡報的標籤 slideOptions: # 簡報相關的設定 theme: black # 顏色主題 transition: 'slide' # 換頁動畫' --- # 複雜度 #### Author: PixelCat ---- ## 概要 1. 什麼是複雜度 2. 如何計算複雜度 3. 複雜度的記號 4. 為何複雜度重要 --- ## 什麼是複雜度 ---- 競程中的複雜度可以指： 1. 時間複雜度 2. 空間複雜度其中時間複雜度更常被討論 ---- 舉個例子 ![](https://i.imgur.com/nI8CsCQ.png) ![](https://i.imgur.com/0pcgizf.png) 誰要跑比較久? ---- 這樣呢? ![](https://i.imgur.com/Ey7pfaD.png) 那要看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;"> 事實上，在我的電腦上，cos()大約: <ul> <li>比乘法慢200倍</li> <li>比亂數產生(mt19937)慢20倍</li> <li>比模運算慢10倍</li> </ul> 不過因為它的計算時間仍然是一個常數 所以歸類在基本操作之一 </div> ::: ---- 於使我們可以算算輸入是某個數字的時候程式會執行多少個基本操作 --- ## 來幾顆{栗|例}子 :::spoiler 好ㄘ ![](https://i.imgur.com/7DMaT31.png) ::: ---- 幾個基本操作? ```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 好ㄘ好ㄘ ![](https://i.imgur.com/7DMaT31.png) ::: ---- 時間複雜度是多少? ```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_ 時(空)間限制 ![](https://i.imgur.com/BXBTIMQ.png) 輸入大小限制 ![](https://i.imgur.com/losuhdO.png) ---- _AtCoder ABC207E_ 時(空)間限制 ![](https://i.imgur.com/8sZU7CN.png) 輸入大小限制 ![](https://i.imgur.com/SjLh4D2.png) ---- 一般情況下電腦每秒大約可以執行 $10^8$ 個基本操作把題目給的數值限制代入你的複雜度比 $10^8$ 還低? 你的程式很可能一秒內跑得完太高了? 可能會TLE，有沒有更快的演算法? ---- ### 常見的時間複雜度與輸入限制 | 複雜度 | 輸入範圍 | |:--------------------- |:--------------- | | $\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` 大部分題目不會刻意要求空間要夠小 ---- 了解複雜度之後我們就可以在寫程式之前先估計自己的演算法是不是夠快就可以避免寫完才發現穩妥妥的TLE ---- 不過複雜度畢竟是估計複雜度夠好不保證一定能過複雜度太差不代表一定沒救假如只差一點點也都值得一試 --- ## 卡常? ---- 卡常數是另外一個相關的問題前面說複雜度會忽略係數但在複雜度很接近上限的時候，可能執行時間乘一個常數就會從AC變TLE ---- ### 避免? 1. 改善實作細節 2. 避免不必要的高科技 3. ~~毒瘤~~ --- ## 以上 ---- 一開始可能不習慣先計算複雜度再下手容易花式TLE還不知道為什麼我就曾經在 $N, Q\leq 10^5$ 的題目使用 $\mathcal{O}(NQ)$的做法，還以為是自己常數太大 ---- 複雜度越到後面會顯得越重要同時也與經驗多寡高度相關 ---- > 早く！もっと早く！！！ > — 桐谷和人

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.