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

📌 本頁使用方式（cppds Ch.2｜講義 02）

① 照節次讀：每一節先讀說明、動手玩互動元件，預測結果再按按鈕驗證。 ② 對照講義：頁上 §徽章對應 cppds 章節；細節與完整程式請回講義 02 與 cppds 原文。 ③ 每節做 quiz：答錯就回到該節重讀，不要往下跳。 ④ 最後翻關鍵詞彙卡（14 張）自測術語（中文為主、術語附英文），並用 REF 總覽區當速查表。標「講義補充」的節是課堂沒細講的延伸，第一輪可略過。

📑 講義 02 PDF 🖥 講義 02 HTML 📖 cppds 原文（AlgorithmAnalysis）📘 Hello 演算法（複雜度分析）🏠 章節總覽

CONTENTS · 內容目錄

P00為什麼要分析？ P01Big-O 記號 P02成長曲線實驗室 P03Anagram 四解法 P04vector 操作成本 P05string 操作成本 P06unordered_map 成本 EX練習題 REF總覽比較 CARD關鍵詞彙卡（14 張）

PROLOGUE · 開場

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

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

n	迴圈法（次加法）	高斯公式（次運算）	比值
1,000	1,000	3	333×
100,000	100,000	3	33,333×
10,000,000	10,000,000	3	3,333,333×

兩種解法 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 增加時各自的耗時變化。

從操作次數看效率

迴圈版逐項相加，加法次數隨 n 增加；公式版用固定次數的整數運算完成計算。接下來用 Big-O 描述操作次數如何隨輸入規模成長。

講義完整範例：同一題的兩張臉

講義 02 · sumOfN：好讀的版本

#include <iostream>
using namespace std;
 
long long sumOfN(long long n) {
    long long theSum = 0;
    for (long long i = 1; i <= n; i++) {
        theSum = theSum + i;
    }
    return theSum;
}
 
int main() {
    cout << sumOfN(10) << endl;
    return 0;
}
 

預期輸出

講義 02 · foo：一樣的演算法、糟糕的可讀性

long long foo(long long tom) {
    long long fred = 0;
    for (long long bill = 1; bill <= tom; bill++) {
        long long barney = bill;
        fred = fred + barney;
    }
    return fred;
}
 

foo(10) 的輸出

foo 和 sumOfN 做的事一模一樣、效率也一樣：可讀性跟效率是兩回事。演算法分析比的是後者：同一個問題，不同「解法」消耗的資源。

講義 02 · 用 chrono 量時間

#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;
 
long long sumOfN2(long long n, double& seconds) {
    auto start = steady_clock::now();
    long long theSum = 0;
    for (long long i = 1; i <= n; i++) theSum = theSum + i;
    seconds = duration<double>(steady_clock::now() - start).count();
    return theSum;
}
 
int main() {
    double secs;
    cout << sumOfN2(10, secs) << endl;   // secs 由參考參數帶回
    return 0;
}
 

預期輸出

steady_clock 是單調時鐘，適合量耗時（system_clock 會被校時影響）。量出來的秒數用傳參考的 seconds 帶回：一個函式想「回傳兩個值」時的慣用手法。

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²)。數的時候不用精確到每一行，抓住「哪一段被執行最多次」就夠了。

常用計數公式：$\sum_{i=1}^n 1=n$，而 $\sum_{i=1}^n i=n(n+1)/2\in\Theta(n^2)$。前者對應單層固定工作，後者常出現在逐輪縮短的巢狀迴圈。

Big-O 與最好、最差、平均

有些演算法的表現不只看 n，還看資料內容。在陣列裡找一個值：運氣好第一格就中（best case，O(1)）、運氣差找到最後一格或根本不在（worst case，O(n)）、若假設目標位置均勻分布，期望看一半（average case）。Big-O 是「上界」記號，不等於 worst case；應先說明分析哪一種輸入情況，再為那個成本函數寫界。average case 也不等於 amortized：後者不假設隨機輸入，而是把一串操作中偶發的昂貴成本攤回每次操作。

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)

講義 02 · 練習題原始碼：T(n) 逐項數

int n = 100;
// 從這裡開始數
int a = 5;
int b = 6;
int c = 10;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        int x = i * i;
        int y = j * j;
        int z = i * j;
    }
}
for (int k = 0; k < n; k++) {
    int w = a * k + 45;
    int v = b * b;
}
int d = 33;
 

逐項數：開頭 3 個指定；雙層迴圈本體 3 個指定，各跑 n² 次；單層迴圈 2 個指定，跑 n 次；收尾 1 個。T(n) = 3 + 3n² + 2n + 1，只留主導項就是 O(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 (char ch : s1) c1[ch - 'a']++;
    for (char ch : s2) c2[ch - 'a']++;
    for (int i = 0; i < 26; ++i) if (c1[i] != c2[i]) return false;
    return true;
}

空間換時間

解法 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²)
}

完整版在 pythonds3/cppds/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)

完整程式見上方「四解法總覽」（動畫逐行對照的就是它）。兩個 26 格計數陣列各掃一遍，最後比對 26 格：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)，偶爾裝滿要搬到較大的緩衝區。課堂動畫用容量加倍說明幾何成長。但 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 線性爬升。

講義完整範例：把四種寫法真的量一次

講義 02 · 四種填滿 vector 的方式

#include <iostream>
#include <vector>
#include "pythonds3/cppds/dstimer.hpp"
using namespace std;
 
void test1(int n) { vector<int> v; for (int i = 0; i < n; i++) v.insert(v.begin(), i); }
void test2(int n) { vector<int> v; for (int i = 0; i < n; i++) v.push_back(i); }
void test3(int n) { vector<int> v; v.reserve(n);
                    for (int i = 0; i < n; i++) v.push_back(i); }
void test4(int n) { vector<int> v(n); for (int i = 0; i < n; i++) v[i] = i; }
 
int main() {
    void (*tests[])(int) = {test1, test2, test3, test4};
    const char* names[] = {"insert at front", "push_back", "with reserve", "direct index"};
    for (int k = 0; k < 4; k++) {
        DSTimer t;
        for (int r = 0; r < 1000; r++) tests[k](1000);
        printf("%-16s%9.2f ms\n", names[k], t.millis());
    }
}
 

耗時比較範例

insert at front   285.31 ms
push_back            6.42 ms
with reserve         3.85 ms
direct index         2.10 ms

前端插入每次都要搬動整段資料，所以慢兩個量級。push_back 偶爾要搬家；容量加倍是課堂模型，C++ 標準不規定倍率，只保證攤還 O(1)。先 reserve 可避免這次建表過程中的重新配置。

講義 02 · erase(begin) vs pop_back：n 變大會怎樣

#include <iostream>
#include <vector>
#include "pythonds3/cppds/dstimer.hpp"
using namespace std;
 
int main() {
    printf("%-10s%14s%12s\n", "n", "erase(begin)", "pop_back");
    for (int n = 2500000; n <= 10000000; n += 2500000) {
        vector<int> x(n);
        DSTimer te;
        for (int r = 0; r < 100; r++) x.erase(x.begin());
        double eraseT = te.millis();
        vector<int> y(n);
        DSTimer tp;
        for (int r = 0; r < 100; r++) y.pop_back();
        printf("%-10d%14.5f%12.5f\n", n, eraseT, tp.millis());
    }
}
 

耗時比較範例

n           erase(begin)    pop_back
2500000        155.20031     0.00022
5000000        311.87542     0.00021
7500000        468.11289     0.00023
10000000       625.40067     0.00022

從需要做的工作看成本：erase(begin()) 要把後續元素往前搬，單次操作是 O(n)；pop_back() 只移除尾端元素，單次操作是 O(1)。下圖比較兩種操作隨資料量增加的耗時。

vector 前端刪除與尾端刪除的耗時比較；每組 100 次操作，縱軸為微秒的對數刻度 — 比較 vector 從前端與尾端刪除元素的耗時。前端刪除需要搬移後續元素，尾端刪除則不需要。

PART 05 · C++ 字串

std::string：連續儲存帶來的成本模型 cppds §2.7

C++11 起，std::string 的字元連續儲存。索引與 size() 是 O(1)，尾端加入是攤還 O(1)；中間插入或刪除最差 O(n)，因為後續字元需要搬移。

操作	複雜度	原因
s[i] / s.size()	O(1)	連續儲存與直接位址計算
s.push_back(ch)	攤還 O(1)	偶爾重新配置並搬移整串
s.insert / s.erase	最差 O(n)	搬移操作位置後方的字元

不要過度推論一般子字串搜尋不會因為連續儲存就自動變成 O(log n)；成本取決於搜尋演算法與兩個字串的長度。

講義 02 · std::string 的成本實驗

#include <iostream>
#include <string>
using namespace std;
 
int main() {{
    string s = "data";
    s.push_back('!');
    s.insert(0, "C++ ");
    cout << s << " | size=" << s.size() << endl;
}}
 

預期輸出

C++ data! | size=9

PART 06 · 雜湊容器

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)	—（無序！）

容器	估計比較／探查次數（10 萬元素查 1000 次）
vector 線性查找	約 50,000,000 次
排序 vector + binary search	約 17,000 次
unordered_set	約 1,200 次（平均每查 1.2 次探查）

怎麼選容器？

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

講義完整範例：contains 的兩個世界

講義 02 · vector 線性掃描 vs unordered_map 雜湊

#include <unordered_map>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include "pythonds3/cppds/dstimer.hpp"
using namespace std;
 
int main() {
    printf("%-10s%10s%12s\n", "n", "vector", "hash table");
    for (int n : {250000, 500000, 1000000}) {
        vector<int> x(n);
        unordered_map<int, int> m;
        for (int j = 0; j < n; j++) { x[j] = j; m[j] = 0; }
        int hits = 0;
        DSTimer tv;
        for (int r = 0; r < 100; r++)
            hits += (find(x.begin(), x.end(), rand() % n) != x.end());
        double vecT = tv.millis();
        DSTimer tm;
        for (int r = 0; r < 100; r++) hits += m.count(rand() % n);
        printf("%-10d%10.3f%12.3f\n", n, vecT, tm.millis());
    }
}
 

耗時比較範例

n             vector  hash table
250000         8.512       0.011
500000        17.204       0.012
1000000       35.917       0.012

vector 的 find 逐一比對元素，搜尋成本隨資料量增加。雜湊表的 count 利用雜湊值定位；雜湊分布良好、負載因子受控時，平均查詢成本為 O(1)，最差為 O(n)。

vector 線性搜尋與雜湊表成功查詢的耗時比較；每組 100 次操作，縱軸為微秒的對數刻度 — 比較 vector 線性搜尋與雜湊表查詢的耗時。觀察資料量增加時，逐一比對與利用雜湊定位的成本差異。

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 章雜湊專章見。

本課程校正版：Ch2 容器複雜度總覽

只保留本章已出現的結構；$n$ 是目前元素或字元數。「—」表示固定大小容器沒有該操作。

Ch2 結構	存取	搜尋	插入	刪除	總儲存量
`std::array<T,N>`	索引 O(1)	線性掃描 O(n)	— 固定大小	— 固定大小	O(n)
`std::vector<T>`	索引 O(1)	依值 O(n)	尾端攤銷 O(1)；前／中 O(n)	尾端 O(1)；前／中 O(n)	O(n)，capacity 可大於 size
`std::string`	索引 O(1)	單字元掃描 O(n)；子字串依演算法	單字元尾加攤銷 O(1)；前／中 O(n)	尾端 O(1)；前／中 O(n)	O(n)
`std::unordered_map<K,V>`	用 key，非索引	key：平均 O(1)、最壞 O(n)	平均 O(1)、最壞 O(n)	平均 O(1)、最壞 O(n)	O(n) entries + buckets