演算法

Big O 描述的是 n 變大時成本怎麼長，不是實際要花多久：平均和最差、均攤、被省略的常數，各自在什麼時候會騙人。

插入、合併、快速、堆積四種排序放在同一份資料上比較：誰快取決於資料原本長什麼樣子。

也包含：計數排序與基數排序

在排好序的資料裡，每看一格就丟掉一半：一百萬筆最多只要看二十格。

兩個索引一起往前走，每一步都排除掉不可能的答案：把原本要兩層迴圈的問題變成走一遍就好。

先花 O(n) 算好前綴和，之後任何區間的總和都只要一次減法；反過來，差分陣列讓「整段都加上一個數」也只要改兩格。

把每個區間的起點和終點當成事件排好，從左掃到右：會議室要幾間、行事曆怎麼合併、哪些時段重疊，都變成一次排序加一次掃描。

在一大段文字裡找一個字串：暴力法最差 O(nm)；KMP（Knuth-Morris-Pratt）利用已經比對過的資訊從不回頭，Rabin-Karp 用滾動雜湊一次比一整段。

BFS（Breadth-First Search，廣度優先搜尋）、Dijkstra、A* 在同一張地圖上找路：BFS 不管路有多難走，Dijkstra 管，A* 還知道終點大概在哪個方向。

也包含：Bellman-Ford 與 Floyd-Warshall

走遍一張圖的兩種方式：BFS（Breadth-First Search，廣度優先搜尋）用佇列一圈一圈往外擴，DFS（Depth-First Search，深度優先搜尋）用堆疊一路走到底再回頭。換一個資料結構，走法就完全不同。

也包含：強連通分量

有先後依賴的工作要排出一個合法順序：每次挑一個沒有前置條件的出來做。圖裡有環就排不出來，而這正好能用來偵測循環依賴。

用最少的總成本把所有點連起來。Kruskal 從最便宜的邊開始挑、用並查集避免成環；Prim 從一個點往外長、用堆積挑最近的。

一個管線網路最多能送多少水？Ford-Fulkerson 不斷找還有剩餘容量的路徑；同一套方法也能解工作分配這類二分匹配問題。

把大問題拆成重疊的小問題，每個小問題只算一次、填進表格。以編輯距離為例，看表格一格一格填滿。

也包含：考題：費氏數列

把問題切成幾個小一號的同樣問題，解完再合起來。畫出遞迴樹，每一層做多少事、有幾層，就是它的 Big O。

每一步都挑眼前最好的，從不回頭。有些問題這樣就是最佳解（區間排程），有些問題這樣會錯（某些面額的找零），差別在能不能證明。

一步一步做選擇，發現走不通就退回上一步換一個選擇。以 N 皇后為例，看剪枝如何讓搜尋量從天文數字降到幾千步。

在陣列裡找兩個加起來等於目標的數：暴力兩層迴圈、排序後雙指標、雜湊表一次掃過，成本從 n² 一路降到 n。

只要前 k 個，就不必把全部排好：整個排序、維持大小為 k 的堆積、Quickselect、桶排序，四種做法放在一起比。

數地圖上有幾塊相連的陸地：BFS（廣度優先搜尋）、DFS（深度優先搜尋）、並查集都能解，差在額外記憶體，以及陸地一格一格加進來時能不能接著算。

一個一個合併是 O(kN)；用堆積每次挑最小的開頭，或兩兩分治合併，都降到 O(N log k)。

經典的 O(n²) 動態規劃，對上用二分搜尋維護「每種長度的最小結尾」的 O(n log n) 做法。

用雜湊集合記住走過的節點要 O(n) 記憶體；快慢指標（Floyd）只用兩個指標，就能找到環和環的入口。

數字一個一個進來，隨時要答出中位數：每次重新排序、維持排序好的陣列，或用一大一小兩個堆積，成本差了好幾個數量級。

每一格能積多少水，取決於左右兩邊最高的牆：暴力法 O(n²)、前綴最大值用 O(n) 空間、雙指標只要 O(1) 空間，加上單調堆疊，四種做法放在一起比。

給一堆會議時段，最少需要幾間會議室？用最小堆積追蹤最早結束的會議，或用掃描線數同時在開的會議數。

一串字能不能切成字典裡的詞？單純回溯會一再重算同樣的後綴而變成指數時間；記憶化、由下而上的動態規劃、BFS（Breadth-First Search，廣度優先搜尋）都把它降到多項式時間。