# 演算法和複雜度 Sprout 2020 --- ### 演算法的定義 「任何良定義的具體計算步驟的一個序列」-- 維基 --- ### 演算法的特徵 1. 具有零個或以上的輸入量 2. 一個以上的輸出量 3. 算法的描述不可有歧義 4. 必須在有限步驟內完成任務 5. 可行（能用既有的基本運算重複有限次實現） -- Donald Knuth --- ### 哪個演算法比較好？ 當兩個**程式**對於所有可能的輸入都能輸出正確的結果時，通常我們會考慮兩個要素： * 哪一個程式花的空間（記憶體）較少？ * 哪一個程式可以跑得比較快？ ---- 有沒有可能程式 A 在某些情況下跑得比 B 快，但其他情況不是？ --- ### 哪個程式跑得比較快？ * 算法所需的基本運算步驟越少，程式就越快？ ----  ---- 實際上，需要考慮不同的基本運算在處理器之間和之內的差異、計算機組織的排程行為、快取等...。 --- ### 複雜度 一樣的算法就連在同一種實作下，都有可能有不同的執行速度，討論不同算法的優劣就變得更困難。 ---- 因此衍生了複雜度的概念，例如: 如果我們說一個算法當 $N$ 為輸入大小時的複雜度是 $O(N)$，那麼我們可以找到一個常數 $c$ 和 $n$ 使得對於任意 $n \leq N$，$執行步數 \leq cN$。 ---- ### 複雜度（白話文） 一個算法的複雜度是 $O(N)$，則我們可以找到（決定）一個常數 $c$，並且當 $N$ 夠大時，執行基本運算的次數永遠不會超過 $cN$。 --- ### 用複雜度比較算法的好處 * 可以不用考慮環境差異（因為單位基本運算消耗的時間理論上與 $N$ 無關） * 可以用漸進的角度良好定義優劣 ---- 較差的算法在 $N$ 小時，可能有較小的執行時間。  --- ### 複雜度分析 ```cpp // Selection Sort for (int i = 0; i < N - 1; ++i) { // N int min_index = i; for (int j = i + 1; j < N; ++j) { // N * N if (arr[j] < arr[min_index]) { min_index = j; } } std::swap(arr[i], arr[min_index]); } ``` -> $O(N^2)$ ---- ```cpp for (int i = 0; i < N; ++i) { // N int j = i; while (j < N && arr[i] == arr[j]) ++j; // ? i = j; } ``` -> $O(N)$ --- # 二分搜 ---- ### 單調遞增函數  對於任意 $x_0 < x_1$，有 $f(x_0) \leq f(x_1)$。 ---- ### 問題 對於任意 $x$，你知道怎麼求 $f(x)$。 現在給你 $y$，請你求出 $x$ 使得 $f(x) = y$。 ---- [0, 3, 7, 11, 19, 27] find 11 ---- 好簡單??? ----  ----  --- ### 例子 給你數列 $a = [0, 1, 2, 3, 6, 8, 9, 10]$，求 $2$ 在哪。 * 從左邊往右邊掃？ -> 這次問你 $10$ 在哪 -> $O(N)$ 跑好跑滿 * 從右邊往左邊掃？ -> ... * 從中間往外面掃？ -> ... 怎麼做都是 $O(N)$ ? ---- ### 觀察 $a = [0, 1, 2, 3, 6, 8, 9, 10]$ * 數字是升序的 ---- $a = [?, ?, ?, [3], ?, ?, ?, ?]$ * 先問中間的數字 * 2 一定在 3 的左邊！ ---- $a = [?, ?, ?, 3, X, X, X, X]$ ---- $a = [?, [1], ?, 3, X, X, X, X]$ * 再問中間的數字 * 2 一定在 1 的右邊！ ---- $a = [X, 1, ?, 3, X, X, X, X]$ ---- $a = [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 find_index(int *a, int L, int R, int Q) { if (R < L) return -1; // O(1) int M = (L + R) / 2; // O(1) if (a[M] == Q) return M; // O(1) // 以下 T((R-L+1) / 2) 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 (lb <= rb) { int mb = (lb + rb) / 2; if (arr[mb] == please_find) { ans = mb; break; } if (arr[mb] < please_find) { lb = mb + 1; } else { assert(please_find < arr[mb]); rb = mb - 1; } } ``` --- ### 練習 NEOJ#148 Guess Number --- ## 小結 * Big-O 複雜度分析利用漸進函數描述算法最差的運算次數 * 當搜尋問題具有單調性時可以用二分搜做到 $O(lgN)$ 的查詢次數