時間複雜度與二分搜
===
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
---
進入二檔
---
Google Drive
Gist
Clipboard
Sign in with Wallet
