時間複雜度與二分搜 === sprout 2021 --- 請問這個程式會執行多久？ ```cpp= for (i = 0; i < 10; i++) { sum += a[i]; } ``` --- ```cpp= for (i = 0; i < 10; i++) { sum += a[i]; } ``` | 指令 | 次數 | | ----------- | ---- | | i = 0 | 1 | | sum += a[i] | 10 | | i++ | 10 | | i < 10 | 11 | --- | 指令 | 次數 | 花費時間 | | ----------- | ---- |----| | i = 0 | 1 | c1 | | sum += a[i] | 10 | c2 | | i++ | 10 | c3 | | i < 10 | 11 | c4| 總共：$c1 + 10 \times c2 + 10 \times c3 + 11 \times c4$ --- 每個指令的執行速度不盡相同 且需要考量的點很多 (不同架構、快取...) 因此在評估程式的效能時 通常可以無視這之間的差距 (但是 +, - 會比 /, % 快速) ---  --- | 指令 | 次數 | 花費時間 | | ----------- | ---- |----| | i = 0 | 1 | c1 | | sum += a[i] | 10 | c2 | | i++ | 10 | c3 | | i < 10 | 11 | c4| 總共執行：$1 + 10 + 10 + 11$ 次基本運算 --- ```cpp= for (i = 0; i < n; i++) { sum = sum + a[i]; } ``` --- | 指令 | 次數 | | ----------- | ---- | | i = 0 | 1 | | sum += a[i] | n | | i++ | n | | i < 10 | n + 1 | 總共執行：1 + n + n + (n + 1) 次基本運算 也就是 $3n + 2$ --- 請問這個程式會執行多久？ ```cpp= for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { sum += a[i][j]; } } ``` --- | 指令 | 次數 | | ----------- | ---- | | i = 0 | n | | i < n | n + 1 | | i++ | n | | j = 0 | n | | j < n | n * (n + 1) | | j++ | n * n | | sum += a[i][j] | n * n | --- 總共執行：$n + (n + 1) + n + n + n \times (n + 1) + n \times n + n \times n$ 也就是 $3n^2 + 5n + 1$ --- 比較一下這兩個多項式 $3n + 2$ vs $3n^2 + 5n + 1$ 哪一個看起來比較大？ n 我要帶多少進去？ --- $100n + 1000$ vs $2^n + n$ n = 5? n = 12? --- 我們需要比較兩個多項式的漸進行為 因此衍生出了 Big-O 符號 --- ## Big-O $f(n) = O(g(n))$ 代表 $g(n)$ 是 $f(n)$ 的漸進上界 講白話一點就是 $f(n) = O(g(n))$ 代表當n夠大時 我們能找到一個常數 $c$ 使得 $c \times g(n)$ 大於 $f(n)$ --- 對於一個式子 我們取用次方數最高、n 很大時影響最大的項 並且將常數移除 當作時間複雜度 --- $3n + 2 => O(n)$ $3n^2 + 5n + 1 => O(n^2)$ $2^n + 5 => O(2^n)$ --- ```cpp for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { sum += a[i][j]; } } ``` 時間複雜度：$O(n^2)$ --- How about this? ```cpp for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { sum += a[i][j]; } } ``` --- ```cpp for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { sum += a[i][j]; } } ``` $n + (n - 1) + (n - 2) + .... + 1 = \frac{(1 + n) \times n}{2} = \frac{n^2+n}{2}$ 時間複雜度：$O(n^2)$ --- 較差的時間複雜度在 $n$ 小時 可能有較好的執行時間  --- 電腦一秒約可以做 $10^8$ 次基本運算 因此可以將程式的時間複雜度算出來 帶入數字判斷量級是否小於 $10^8$ --- 有經驗的人可以透過測資大小直接推算 題目要求的程式的時間複雜度大概是什麼 | N | 複雜度 | | --- | ------ | | $10$ | $O(n!)$ | | $20$ | $O(2^n\times n)$ | | $2000$ | $O(n^2)$ | | $10^5$ | $O(nlogn)$ | | $10^7$ | $O(n)$ | | $10^{18}$ | $O(1)$ | --- ## 二分搜 --- 猜數字 1 ~ 100 中猜我想的數字 我會告訴你我想的比你猜多還大或小 請問我最小猜幾次能猜到 --- 猜數字 1 ~ 100 中猜我想的數字 我會告訴你我想的比你猜多還大或小 請問我最小猜幾次能保證猜到? --- 100, 50, 25, 13, 7, 4, 2, 1 --- 給你遞增數列 $[0, 1, 2, 3, 6, 8, 9, 10]$ 求 $2$ 在哪 從左到右掃過陣列是 $O(N)$ 沒有用到遞增數列的性質！ ---- ### 觀察 $[0, 1, 2, 3, 6, 8, 9, 10]$ * 數字是升序的 ---- $[?, ?, ?, [3], ?, ?, ?, ?]$ * 先問中間的數字 * 2 一定在 3 的左邊！ ---- $[?, ?, ?, 3, X, X, X, X]$ ---- $[?, [1], ?, 3, X, X, X, X]$ * 再問中間的數字 * 2 一定在 1 的右邊！ ---- $[X, 1, ?, 3, X, X, X, X]$ ---- $[X, 1, [2], 3, X, X, X, X]$ * 再問中間的數字... ---- ## 遞迴 ```cpp int find_index(int *a, int L, int R, int Q) { if (R < L) return -1; // 解空間是空集合 -> 無解 int M = (L + R) / 2; if (a[M] == Q) return M; // 找到了 if (a[M] < Q) return find_index(a, M+1, R, Q); // 在右邊 return find_index(a, L, M-1, Q); // 在左邊 } ``` --- ## 迴圈 ```cpp int ans = -1; while (l <= r) { int mid = (l + r) / 2; if (arr[mid] == please_find) { ans = mid; break; } if (arr[mid] < please_find) { l = mid + 1; } else { assert(please_find < arr[mid]); r = mid - 1; } } ``` --- 複雜度分析 $N$ 為序列長度 因為每一次可能的解答的集合都會減少一半 $N$ 一直除以$2$要除幾次才能等於 $1$ 因此複雜度為 $O(logN)$ --- 我們也可以利用二分搜的概念去逼近答案 Ex: 找一個數字開根號的值為多少 --- ```cpp double sqrt(double n) { double l = -INF, r = INF; while(r - l < eps) { double mid = (l + r) / 2; if (mid * mid < n) l = mid; else r = mid; } return l; } ``` --- 練習時間 NEOJ 148 --- ## WA ```cpp int l = 1, r = 100; while(l != r){ int mid = (l+r)/2; if (less(mid)) r = mid-1; else l = mid; } guess(l); ``` --- ## AC ```cpp int l = 1, r = 101; while(r - l != 1){ int mid = (l+r)/2; if (less(mid)) r = mid; else l = mid; } guess(l); ``` --- ## Bonus problem NEOJ 364 --- 進入二檔 ---