<style> .reveal .slides { text-align: left; } p, h1, h2, h3, h4, h5, h6 { font-weight: 200px !important; font-family: arial-next !important; } </style> # time complexity 作者: royyaha --- ### Why we need to know the complexity for an algorithm? ---- ### 我們需要一種好的語言来比较不同算法做同樣工作的速度，或者它们使用的内存量。 ---- ### for example: ### how many time we need to calculate $2^n$ ---- ### ? times($n=32$ for example) $2^1 = 2$ $2^2 = 2^1 \times 2 = 4$ $2^3 = 2^2 \times 2 = 8$ $2^4 = 2^3 \times 2 = 16$ . . $2^{31} = 2^{30} \times 2 = 2147483648$ $2^{32} = 2^{31} \times 2 = 4294967296$ ---- ### $n$ times($n=32$ for example) $2^1 = 2$ $2^2 = 2^1 \times 2 = 4$ $2^3 = 2^2 \times 2 = 8$ $2^4 = 2^3 \times 2 = 16$ . . $2^{31} = 2^{30} \times 2 = 2147483648$ $2^{32} = 2^{31} \times 2 = 4294967296$ ---- ### ? times($n=32$ for example) $2^1 = 2$ $2^2 = 2^1 \times 2^1 = 4$ $2^4 = 2^2 \times 2^2 = 16$ $2^8 = 2^4 \times 2^4 = 256$ $2^{16} = 2^8 \times 2^8 = 65536$ $2^{32} = 2^{16} \times 2^{16} = 4294967296$ ---- ### $logn$ times($n=32$ for example)? $2^1 = 2$ $2^2 = 2^1 \times 2^1 = 4$ $2^4 = 2^2 \times 2^2 = 16$ $2^8 = 2^4 \times 2^4 = 256$ $2^{16} = 2^8 \times 2^8 = 65536$ $2^{32} = 2^{16} \times 2^{16} = 4294967296$ --- ## 如何表示時間複雜度？ ---- ##### 通常用$O(f(n))$來表示時間複雜度，比如說: $O(n^2logn)$ ##### $n$通常表示輸入的大小 ###### 如果输入的是一個陣列，$n$將是數組的大小 ###### 如果是輸入是一個字串，$n$是字串的長度。 --- 如何計算複雜度？ ---- 我們假設所有的操作都需要花費一樣的時間！ 包括 • 加減乘除 • 取餘數 • 位運算 • 存取記憶體 • 判斷運算子 • 賦值運算子 • …… ---- ##### $O(1)$ 程式範例 ``` cpp int a = 1, b = 2, c = 3, d = 4; // 變數宣告O(1) a = (b + c) * d; // 加減乘除O(1) ``` ---- ##### $O(n)$ 程式範例 ###### 明顯發現和輸入n有關係 ###### 問題：為什麼常數不重要？ ``` cpp for (int i = 1; i <= 3*n; i++) { // code } ``` ``` cpp for (int i = 1; i <= n+5; i++) { // code } ``` ``` cpp for (int i = 1; i <= n; i += 2) { // code } ``` ---- ##### $O(n^2)$ 程式範例 ``` cpp for (int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { // code } } ``` ###### 一段程式碼的時間複雜度，取決於時間複雜度最大的段落 ``` cpp for(int i = 0; i < n; i++) { // code } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { // code } } ``` ---- 從上面的例子可以發現，n * 常數次不會對程式的執行效率有明顯的變化，所以我們直接忽略n以外的常數 --- #### 一秒大約可以執行$10^8$次 ---- [小測驗1] $O(..)$? ``` cpp // Floyd-Warshall for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } ``` ---- [小測驗2] 輸入$n < 10^6$，時限2s 需要一個時間多快的演算法 ( a ) $O(n^2)$ ( b ) $O(n!)$ ( c ) $O(nlogn)$ ----  ---- [小測驗3] 實戰估複雜度時間！ [ZJ e346: 區間和練習](https://zerojudge.tw/ShowProblem?problemid=e346) ---- [挑戰1] 2D區間和? [ZJ a694: 吞食天地二](https://zerojudge.tw/ShowProblem?problemid=a694) --- 遞迴的時間複雜度(待續...) --- 資料來源： [資訊之芽](https://www.csie.ntu.edu.tw/~sprout/algo2018/ppt_pdf/complexity.pdf) [CPH](https://cses.fi/book/book.pdf) Algorithms and Complexity