時間複雜度與二分搜

sprout 2021

請問這個程式會執行多久？

for (i = 0; i < 10; i++) {
    sum += a[i];
}

for (i = 0; i < 10; i++) {
    sum += a[i];
}

總共：\(c1 + 10 \times c2 + 10 \times c3 + 11 \times c4\)

每個指令的執行速度不盡相同
且需要考量的點很多 (不同架構、快取…)
因此在評估程式的效能時
通常可以無視這之間的差距
(但是 +, - 會比 /, % 快速)

總共執行：\(1 + 10 + 10 + 11\) 次基本運算

for (i = 0; i < n; i++) {
    sum = sum + a[i];
}

總共執行：1 + n + n + (n + 1) 次基本運算
也就是 \(3n + 2\)

請問這個程式會執行多久？

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        sum += a[i][j];
    }
}

總共執行：\(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\)

有經驗的人可以透過測資大小直接推算
題目要求的程式的時間複雜度大概是什麼

二分搜

猜數字
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

進入二檔