時間複雜度與二分搜
sprout 2021
請問這個程式會執行多久？
for (i = 0; i < 10; i++) { sum += a[i]; }
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\) 次基本運算
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\)
請問這個程式會執行多久？
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)\)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
sum += a[i][j];
}
}
時間複雜度：\(O(n^2)\)
How about this?
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
sum += a[i][j];
}
}
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]\)
- 再問中間的數字…
遞迴
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); // 在左邊
}
迴圈
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: 找一個數字開根號的值為多少
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
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
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
進入二檔