演算法分析 — Algorithm Analysis Interactive（C++）

CONTENTS · 內容目錄

P00為什麼要分析？ P01Big-O 記號 P02成長曲線實驗室 P03Anagram 四解法 P04vector 操作成本 P05unordered_map 成本 EX練習題 REF總覽比較

PROLOGUE · 開場

演算法分析：比「誰的程式快」更聰明的問法 cppds §2.1–2.2

同一個問題有很多寫法。「哪個好？」不能只用碼表量：機器快慢、資料大小都會干擾。演算法分析問的是：當輸入規模 n 變大，工作量怎麼成長？ 我們數「基本操作次數」T(n)，只留下成長最快的主導項。

兩種解法 CODE

// 迴圈版：加 n 次
long long sumOfN(long long n) {
    long long theSum = 0;
    for (long long i = 1; i <= n; i++)
        theSum = theSum + i;
    return theSum;
}
// 高斯公式版：三個運算，n 再大也一樣
theSum = (n * (n + 1)) / 2;

怎麼在 C++ 計時？

// ：夾住要量的程式碼
auto start = steady_clock::now();
// ... 要計時的程式 ...
secs = duration<double>(
    steady_clock::now() - start).count();

講義的實測：迴圈版 n 從 10⁵ 加到 10⁶，時間差不多也乘十；公式版對 10⁵ 到 10⁸ 四種 n 的耗時幾乎是同一個數字。短小的操作要重複跑很多次再取平均，雜訊才壓得下來。

benchmark 的干擾因素

CPU、編譯器最佳化（-O2 有時會把整個迴圈摺掉！）、當下的系統負載，都會影響碼表讀數。操作次數的成長級別才是演算法本身的性質，這就是接下來 Big-O 要抓的東西。

PART 01 · 記號

Big-O：只留主導項 cppds §2.3

T(n) = 5n² + 27n + 1005 → 當 n 夠大，n² 說了算：O(n²)。常數與低次項在成長率面前都是雜訊。

f(n)	名稱	n=10	n=1,000	n=10⁶	典型例子
1	常數	1	1	1	索引 a[i]、hash 查詢（平均）
log n	對數	3	10	20	binary search
n	線性	10	1,000	10⁶	走訪、sequential search
n log n	線性對數	33	10⁴	2×10⁷	merge sort
n²	平方	100	10⁶	10¹²	雙層迴圈、bubble sort
2ⁿ	指數	1,024	10³⁰¹	—	天真費波那契、河內塔

逐行數一次 T(n)

拿一段真的程式來數。三個賦值（3）、外圈跑 n 次的內圈各貢獻 n 次（3n²… 這裡照講義的例子）： T(n) = 3 + 3n² + 2n + 1 = 3n² + 2n + 4。 n 一大，3n² 說了算，其他項連同係數 3 全部丟掉：O(n²)。數的時候不用精確到每一行，抓住「哪一段被執行最多次」就夠了。

最好、最差、平均

有些演算法的表現不只看 n，還看資料內容。在陣列裡找一個值：運氣好第一格就中（best case，O(1)）、運氣差找到最後一格或根本不在（worst case，O(n)）、平均攤下來要看一半（average case）。講 Big-O 時預設講 worst case，因為它是保證；第 6 章的雜湊表會是「平均 O(1)、最差 O(n)」這種分開報的典型例子。

QUIZ · 讀程式數操作

for (i=0;i<n;i++) for (j=0;j<n;j++) k++; 之後接 for (i=0;i<n;i++) k++;，整段的 Big-O 是？

(A) O(n²)

(B) O(n² + n)

PART 02 · 實驗室

成長曲線實驗室：親眼看差距拉開 cppds §2.3

怎麼讀這張圖

n 小時大家擠在一起：常數項還有戲； n 一大，曲線層級分明：這就是為什麼我們只在乎 order of magnitude。勾選 2ⁿ 感受一下什麼叫「瞬間出框」。

PART 03 · 案例研究

Anagram 偵測：同一題的四種成長率 cppds §2.4

「earth 和 heart 是不是變位詞？」四種解法都對，但成長率天差地遠。這是「正確 ≠ 好」的最佳教材。

四解法總覽 CODE

// 解法 1 Checking Off：對 s1 每個字元，去 s2 找到就劃掉 → O(n²)
// 解法 2 Sort and Compare：兩字串排序後逐字比 → O(n log n)
// 解法 3 Brute Force：列出 s1 全部排列 → O(n!)，免談
// 解法 4 Count and Compare：數 26 個字母出現次數 → O(n)
bool anagramSolution4(string s1, string s2):
    int c1[26] = {0};  int c2[26] = {0}
    for (ch : s1): c1[ch - 'a']++
    for (ch : s2): c2[ch - 'a']++
    return c1 全等 c2

空間換時間

解法 4 用兩個 26 格計數陣列換到 O(n)。時間與空間的交易是演算法設計最常用的槓桿之一。

四個解法攤開看

解法 1：Checking Off，O(n²) CODE

bool anagramSolution1(string s1, string s2) {
    bool stillOK = (s1.length() == s2.length());
    vector<char> aList(s2.begin(), s2.end());
    for (每個 s1 的字元，stillOK 時) {
        在 aList 裡線性找它;            // 內圈：O(n)
        if (found) aList.erase(那一格);  // 劃掉
        else stillOK = false;
    }
    return stillOK;   // n 個字元 × 每個找 O(n) = O(n²)
}

完整版在 dscpp/anagram.hpp。比較次數是 1+2+…+n = n(n+1)/2，主導項 n²/2。

解法 2：Sort and Compare，O(n log n) CODE

bool anagramSolution2(string s1, string s2) {
    sort(s1.begin(), s1.end());
    sort(s2.begin(), s2.end());
    // 排序後逐字比對，一個不同就 false
    return s1 逐字等於 s2;
}   // 迴圈 O(n)，但 sort 是 O(n log n)：貴的那步說了算

解法 3：Brute Force，O(n!)

列出 s1 全部排列、看 s2 在不在裡面。 20 個字元的排列數是 20! ≈ 2.4×10¹⁸：就算一微秒生一個，也要七萬多年。正確、可寫、完全不可用，這種選項的存在是為了提醒你先估量級再動手。

解法 4：Count and Compare，O(n) CODE

bool anagramSolution4(string s1, string s2) {
    int c1[26] = {0};  int c2[26] = {0};
    for (i : s1) c1[i - 'a']++;
    for (i : s2) c2[i - 'a']++;
    for (i = 0; i < 26; i++)
        if (c1[i] != c2[i]) return false;
    return true;   // T(n) = 2n + 26 → O(n)
}

QUIZ · 解法 2 的陷阱

解法 2「排序後比較」看起來只有一個迴圈，為什麼不是 O(n)？

(A) 排序本身要 O(n log n)

(B) 字串比較是 O(n²)

PART 04 · C++ 容器

vector 的操作成本：為什麼 push_back 是攤銷 O(1) cppds §2.5–2.6

vector 底層是連續陣列。索引 O(1)； push_back 平常 O(1)，偶爾裝滿要翻倍搬家：把搬家成本平均到每次操作，仍是 O(1)（攤銷）。但 insert(begin(), x) 每次都要整體右移 → O(n)。

vector 成本表（背這張）

v[i] 讀寫O(1)

push_back / pop_backO(1) 攤銷

insert / erase（前端或中間）O(n)

走訪 / find（無序）O(n)

切一段（k 個元素）O(k)

sortO(n log n)

四種把 0..n−1 塞進 vector 的寫法 CODE

test1: v.insert(v.begin(), i)  // 前端插入：最慢
test2: v.push_back(i)           // 攤銷 O(1)
test3: v.reserve(n) 再 push_back // 連搬家都省了
test4: vector<int> v(n); v[i]=i  // 開好大小直接填

講義用 chrono 對四種寫法各跑 1000 次取平均：test1 慢一個數量級以上，後三種同級，reserve 再快一截。

量出 Big-O 的土方法

把 n 加倍再量一次，看時間變幾倍：接近 1 倍是 O(1)、2 倍是 O(n)、4 倍是 O(n²)。講義用這招驗證了 pop_back() 平坦不動、erase(begin()) 隨 n 線性爬升。

PART 05 · 雜湊容器

unordered_map / set：平均 O(1) 的代價與條件 cppds §2.8

unordered_map（雜湊表）讓「查 key」平均 O(1)：不用排序、不用走訪。細節（hash 函數、碰撞、載入因子）第 6 章展開；本章先記住成本表與「平均」兩個字的份量。

操作	vector（無序）	vector（已排序）	unordered_map/set
查找 contains(x)	O(n)	O(log n)	O(1) 平均／O(n) 最差
插入	O(1) 尾端	O(n)（挪位）	O(1) 平均
刪除	O(n)	O(n)	O(1) 平均
依序輸出	需先排序	O(n)	—（無序！）

怎麼選容器？

要次序（排名、範圍查詢）→ 排序 vector 或 map。
只要快速存在性/對應 → unordered_map。
小資料（< 100）→ 什麼都很快，選最簡單的。

EXERCISES · 練習

動手驗證 cppds §2 綜合

EXERCISE 1 · 主導項

T(n) = 3 + 100·log n + 0.001·n² 的 Big-O 是？

(A) O(n²)

(B) O(log n)

EXERCISE 2 · 巢狀但不滿

for (i=0;i<n;i++) for (j=i;j<n;j++) k++; 執行 k++ 幾次？Big-O？

(A) n(n+1)/2 次；O(n²)

(B) n²/2 次；O(n)

EXERCISE 4 · 講義練習：翻倍迴圈

int i = 1; while (i <= n) {{ for (j = 1; j <= i; j++) x++; i *= 2; }} 的複雜度是？

(A) O(n)

(B) O(n log n)

EXERCISE 5 · 講義補充練習（課堂跳過）：第 k 小

亂序數列找第 k 小的數，要求 O(n log n)。最直接的做法是？

(A) 整串 sort 一次，回傳第 k−1 格

(B) 跑 k 輪「找最小、刪掉」

EXERCISE 3 · 容器選擇

需求：不斷插入單字、隨時問「這個單字出現過嗎」。10⁶ 次操作，選哪個？

(A) unordered_set

(B) vector + 每次 find

REFERENCE · 總覽

本章總結 cppds §2 總覽

關鍵概念複習 ① 演算法分析比 benchmark 穩：數操作、看成長率。
② Big-O 三步驟：數 T(n) → 找主導項 → 丟係數。
③ Anagram 案例：同一題可以有 O(n!)、O(n²)、O(n log n)、O(n) 四種命運。
④ C++ 容器成本表要背：vector 索引 O(1)／前端插入 O(n)；unordered_map 平均 O(1)。
⑤ 「平均」有前提（好的 hash、健康的載入因子）：第 6 章雜湊專章見。

本章對應	cppds	自學頁
什麼是演算法分析	§2.1–2.2	P00
Big-O	§2.3	P01–P02
Anagram	§2.4	P03
C++ 集合效能（vector/string）	§2.5–2.7	P04
Hash Tables	§2.8	P05

演算法分析與 Big-O