深度探秘

演算法是「解法本身」，程式只是它的某種語言版本

一個常見的疑問

剛開始學寫程式時，大家很愛比較：「同一題，你的程式跟我的長得不一樣，到底誰寫得比較好？」

要回答這個問題，得先分清楚兩個容易混在一起的概念：

• 演算法 (algorithm)：一份抽象、一步一步的解題步驟說明。它不綁定任何程式語言，只要給定輸入，就能產生正確結果。
• 程式 (program)：把某個演算法用某種程式語言寫出來的成品。

同一個演算法，可以有「無數種」程式寫法——換個語言、換個變數名、換種寫法，都還是同一個演算法。

看下面兩段 Python，它們其實是同一個演算法（用累加器把 1 到 n 加起來），只是寫法天差地遠：

def sum_of_n(n):
    the_sum = 0
    for i in range(1, n + 1):
        the_sum = the_sum + i
    return the_sum

def foo(tom):
    fred = 0
    for bill in range(1, tom + 1):
        barney = bill
        fred = fred + barney
    return fred

foo 變數名亂取、還多了一個沒必要的指派，所以可讀性很差——但解法的本質完全一樣。

生活妙喻

食譜 vs 一盤端出來的菜

把演算法想成「食譜」

• 演算法就像一份食譜：先打蛋、再加糖、攪拌、進烤箱 180 度 20 分鐘。它描述的是「怎麼做」，跟你用哪個品牌的烤箱、用中文還是英文寫食譜都無關。
• 程式則是照著食譜實際做出來的那盤菜：同一份食譜，阿明做一盤、阿華做一盤，賣相可能差很多，但「做法」是同一套。

所以當我們問「誰的程式比較好」，其實有兩種完全不同的問法：

sum_of_n 和 foo 在「可讀性」上分高下，但在「演算法效率」上根本是同一回事。

實用超能力

把焦點放在「運算資源」上

演算法分析在比什麼？

演算法分析 (algorithm analysis) 的核心：比較不同演算法使用運算資源的多寡，藉此說「這個比那個好，因為它更省」。

運算資源主要看兩種：

flowchart TD
    A[運算資源] --> B[空間 記憶體用量]
    A --> C[時間 執行所需步數]
    C --> D[本章重點 用 Big-O 描述時間]

• 空間 (space)：解題需要多少記憶體。通常由問題本身決定，偶爾某些演算法有特別的空間需求才需特別說明。
• 時間 (time)：執行所需的時間，又叫 execution time / running time，是本章的主要焦點。

實戰心法：當你看到兩段功能相同但寫法不同的程式，先問自己——「它們是不是同一個演算法？」如果是，那效率就一樣，差別只在風格；如果不是，才需要進一步用後面要學的 Big-O 來比效率。

深度探秘

用碼錶量真實秒數：benchmark 分析

最直覺的做法：拿碼錶計時

想知道 sum_of_n 跑多久？最直覺的方式就是基準測試 (benchmark)：記下開始時間、跑完記下結束時間，相減就是花的秒數。

Python 的 time 模組有個 time() 函式，會回傳目前的系統時鐘秒數，前後各叫一次就能算出耗時：

import time

def sum_of_n_2(n):
    start = time.time()
    the_sum = 0
    for i in range(1, n + 1):
        the_sum = the_sum + i
    end = time.time()
    return the_sum, end - start

實測時可以看到一個規律：當 n 變成 10 倍，耗時也大約變成 10 倍。

這暗示了 sum_of_n 的耗時和 n 大致成正比——但這還不是重點。

生活妙喻

不同跑道、不同天氣下的碼錶成績

用碼錶比兩個選手公平嗎？

還有一種完全不同的解法，直接套用數學公式，不用迴圈：

$$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$$

def sum_of_n_3(n):
    return (n * (n + 1)) / 2

它快得驚人，而且不論 n 多大，耗時幾乎都是固定的一點點。

問題來了：如果我在老舊電腦上跑這個公式版、在最新電腦上跑迴圈版，碼錶可能反而說迴圈版比較快！

用碼錶量秒數，就像在不同跑道、不同天氣、不同鞋子下幫兩位選手計時——你量到的是「這次比賽的條件」，不是「選手本身的實力」。

flowchart TD
    A[同一段演算法] --> B[換一台電腦]
    A --> C[換一種語言]
    A --> D[換一個時段 系統忙碌程度]
    B --> E[碼錶秒數都不同]
    C --> E
    D --> E
    E --> F[無法當成演算法本身的客觀指標]

實用超能力

我們真正想要的：與實作無關的衡量

為什麼 benchmark 不夠用？

benchmark 量到的「真實秒數」其實依賴一堆與演算法無關的東西：

• 哪一台機器（CPU 新舊、規格）
• 哪一種程式語言、哪一版編譯器/直譯器
• 跑的時段（系統當下忙不忙）

換台機器或換個語言，數字就變了。所以它不能拿來公平比較「演算法本身」。

我們真正想要的是一種與程式、與電腦都無關的衡量方式——只描述演算法本身、可以跨實作比較。

實戰心法：

1. benchmark 仍然有用——當你想知道「在我這台機器上、現在這個版本」實際多快時。
2. 但要比較「演算法誰比較好」時，碼錶會騙你，得改用下一節要學的 Big-O：它只看『工作量隨問題規模 n 怎麼成長』，不看你用哪台機器。

深度探秘

用步數函數 T(n) 描述工作量

數步數，而不是數秒數

既然碼錶會被環境干擾，那就改成數演算法要做幾個基本動作。先選一個合理的「基本運算單位」，再數它做了幾次。

以 sum_of_n 為例，選「指派 (assignment) 次數」當基本單位：

• 一開始 the_sum = 0：1 次
• 迴圈裡 the_sum = the_sum + i 跑 n 次：n 次

把總步數寫成一個函式 $T$：

$$T(n) = 1 + n$$

讀作：「解決規模為 $n$ 的問題要花 $1 + n$ 步。」這裡的 $n$ 稱為問題規模 (size of the problem)。

規模越大，要做的步數通常越多——加總前 100,000 個整數，當然比加總前 1,000 個花更多步。我們想看的就是：步數如何隨 n 變化。

生活妙喻

看跑車輸給卡車？看主導項就懂了

n 變大時，誰在主導？

電腦科學家更進一步：精確步數不重要，重要的是「成長最快的那一項」。

看另一個例子：

$$T(n) = 5n^2 + 27n + 1005$$

• 當 $n$ 很小（1、2），看起來是常數 1005 最大。
• 但當 $n$ 越來越大，$n^2$ 那一項會狠狠壓過其他項——其他項變得微不足道。
• 連 $n^2$ 前面的係數 5 也變得不重要。

所以我們說它的數量級 (order of magnitude) 是 $f(n) = n^2$，記成 $O(n^2)$。

這就像高速公路上比拉力：起步時小排量的車（常數項）可能領先，但路一拉長，大馬力的引擎（最高次項）一定遠遠甩開所有人。我們在乎的是『路夠長之後誰贏』。

flowchart TD
    A[T n 等於 5n平方 加 27n 加 1005] --> B[n 很小時 常數 1005 看起來最大]
    A --> C[n 很大時 n平方 項壓過一切]
    C --> D[丟掉低次項與係數]
    D --> E[數量級 O n平方]

實用超能力

Big-O：丟掉常數與係數

化簡成 Big-O 的兩條規則

數量級函式描述 $T(n)$ 中隨 $n$ 增加成長最快的部分，常稱為 Big-O 記號（O 代表 order），寫成 $O(f(n))$。

把 $T(n)$ 化成 Big-O，只要兩步：

1. 找出最高次（成長最快）的項 —— 其他低次項全部丟掉。
2. 丟掉那一項的常數係數。

回到 sum_of_n：$T(n) = 1 + n$。當 $n$ 變大，常數 1 越來越不重要，丟掉它：

$$T(n) = 1 + n ;\Rightarrow; O(n)$$

再看 $T(n) = 5n^2 + 27n + 1005$：保留最高次 $n^2$、丟掉係數 5 與其他項：

$$O(n^2)$$

實戰心法：拿到一個步數式，先圈出指數最高的項，再把數字係數擦掉，剩下的就是 Big-O。它告訴你「規模放大時，工作量會怎麼長」，而不是「現在精確幾步」。

深度探秘

七種你會一再遇到的成長等級

常見的數量級家族

研究演算法時，會反覆碰到下面這幾個 Big-O 函式。由慢成長（好）到快成長（壞）排列：

越往下走，n 變大時耗時暴增得越誇張。挑演算法時，當然希望盡量往表格上方靠。

生活妙喻

小 n 看不出差別，大 n 見真章

為什麼要看「n 很大」的時候？

當 n 很小時，這些函式擠在一起、難分高下——常數項甚至可能讓『理論上較慢』的演算法暫時跑贏。但只要 n 一拉大，它們之間的差距就壁壘分明。

想像四個人爬樓梯到不同樓層：搭電梯（$\log n$）、走樓梯（$n$）、每層都繞一圈再上（$n^2$）、每層把所有組合都走一遍（$2^n$）。只爬 2 層，大家差不多；但要上 100 層，搭電梯的早就到了，$2^n$ 那位可能這輩子都到不了。

flowchart TD
    A[n 很小] --> B[各等級擠在一起 難分高下]
    C[n 很大] --> D[O log n 最快]
    C --> E[O n 次之]
    C --> F[O n平方 明顯變慢]
    C --> G[O 2的n 次方 爆炸性變慢]

這也是為什麼 Big-O 永遠在問：「當 n 趨近很大，誰主導？」

實用超能力

最佳、最差、平均情況

同一演算法也可能有好幾個臉孔

有時候演算法的效能不只看問題規模 n，還取決於資料的實際內容。這時要分三種情況描述：

• 最佳情況 (best case)：資料剛好讓它跑超快。
• 最差情況 (worst case)：碰到特別刁鑽的資料，跑得特別慢。
• 平均情況 (average case)：一般狀況下落在兩者之間。

例子：在一堆名單裡找某個名字。如果要找的人剛好排第一個（最佳），找一次就好；如果排最後或根本不在（最差），得整份翻完。同一個『逐一找』演算法，會因資料而有天壤之別。

實戰心法：

1. 報告效率時，講清楚你說的是哪一種情況——很多演算法的『最差』比『平均』糟很多。
2. 不要被某個特別好（或特別壞）的個案誤導，要看它在實務上最常發生的情況，並對最差情況有心理準備。

深度探秘

拆成區塊、逐塊累加步數

把程式拆成幾塊來數

看一段示範程式（它不做什麼有意義的事，但很適合練習分析）：

a = 5
b = 6
c = 10
for i in range(n):
    for j in range(n):
        x = i * i
        y = j * j
        z = i * j
for k in range(n):
    w = a * k + 45
    v = b * b
d = 33

把指派次數拆成四塊累加：

1. 開頭 a, b, c 三個指派：常數 3。
2. 雙層巢狀迴圈裡有 3 個指派，各跑 $n^2$ 次：$3n^2$。
3. 單層迴圈裡有 2 個指派，各跑 $n$ 次：$2n$。
4. 最後 d = 33：常數 1。

加起來：

$$T(n) = 3 + 3n^2 + 2n + 1 = 3n^2 + 2n + 4$$

生活妙喻

巢狀迴圈＝乘法

迴圈巢狀就是次數相乘

判斷迴圈貢獻多少次數，有個超好用的直覺：迴圈疊幾層，n 就乘幾次。

想像你在填一張 $n \times n$ 的座位表：外層迴圈是『第幾排』，內層是『第幾個座位』。要填滿整張表，得做 $n \times n = n^2$ 次。每多巢狀一層，就像多了一個維度，次數再乘一個 n。

flowchart TD
    A[單層迴圈 跑 n 次] --> B[貢獻 n]
    C[雙層巢狀 跑 n 乘 n 次] --> D[貢獻 n平方]
    E[三層巢狀 跑 n 乘 n 乘 n 次] --> F[貢獻 n立方]

• 沒在迴圈裡的指派：只算 1 次（常數）。
• 在單層迴圈裡：乘 $n$。
• 在雙層巢狀迴圈裡：乘 $n^2$。

所以看到雙層巢狀就先警覺：這裡很可能藏著 $n^2$。

實用超能力

看指數最高項決定 Big-O

從 T(n) 收斂到 Big-O

有了 $T(n) = 3n^2 + 2n + 4$，套用前面學的規則：看指數最高的項。

• 最高次是 $n^2$，它會主導；其餘 $2n$ 與常數 4 丟掉，係數 3 也丟掉。

$$T(n) = 3n^2 + 2n + 4 ;\Rightarrow; O(n^2)$$

實戰演練——快速判讀幾個常見片段：

# 片段一：雙層巢狀 → O(n^2)
for i in range(n):
    for j in range(n):
        test = test + i * j

# 片段二：兩個各自獨立的單層迴圈 → n + n = 2n → O(n)
for i in range(n):
    test = test + 1
for j in range(n):
    test = test - 1

# 片段三：每次 i 砍半 → O(log n)
i = n
while i > 0:
    k = 2 + 2
    i = i // 2

心法：先看迴圈巢狀層數抓出最高次項（並注意『砍半』型迴圈是對數），兩個並排的迴圈是相加不是相乘，最後丟掉常數與係數就得到 Big-O。

深度探秘

什麼是變位詞？解法一：逐一勾消

變位詞偵測問題

如果一個字串是另一個字串重新排列而成，它們就是變位詞 (anagram)。例如 heart 和 earth、python 和 typhon。假設兩字串等長、都由 26 個小寫英文字母組成，目標是寫一個函式判斷它們是不是變位詞。

解法一：逐一勾消 (checking off) —— 檢查 s1 的每個字元是否都出現在 s2 中，找到就把它『勾消』（換成 None）。

def anagram_solution1(s1, s2):
    a_list = list(s2)
    pos1 = 0
    still_ok = True
    while pos1 < len(s1) and still_ok:
        pos2 = 0
        found = False
        while pos2 < len(a_list) and not found:
            if s1[pos1] == a_list[pos2]:
                found = True
            else:
                pos2 = pos2 + 1
        if found:
            a_list[pos2] = None
        else:
            still_ok = False
        pos1 = pos1 + 1
    return still_ok

注意這是雙層迴圈：外層掃 s1 的每個字元，內層在 s2 的清單裡找它。

生活妙喻

為什麼勾消法是 O(n^2)？

數一數總共要看幾次

s1 有 $n$ 個字元，每個字元都可能要掃過 s2 清單裡最多 $n$ 個位置。最壞情況下，造訪次數是 1 到 n 的總和：

$$\sum_{i=1}^{n} i = \frac{n(n+1)}{2} = \frac{1}{2}n^2 + \frac{1}{2}n$$

n 變大時 $n^2$ 項主導，$\frac{1}{2}$ 係數可丟，所以是 $O(n^2)$。

像在一疊 n 張名片裡幫每個人找配對：第一個人翻整疊、第二個人翻剩下的……每個人都得翻一輪，加起來大約是 $n^2$ 的工作量。

flowchart TD
    A[外層 取 s1 的每個字元 共 n 個] --> B[內層 在 s2 清單裡逐一尋找 最多 n 次]
    B --> C[總造訪次數 約 n 乘 n 的一半]
    C --> D[數量級 O n平方]

實用超能力

解法二：排序後比對，但別被表象騙了

排序比對法

解法二：先排序再比對 (sort and compare) —— 兩個變位詞排序後一定變成完全相同的字串，所以把兩字串各自排序，再逐位比對：

def anagram_solution2(s1, s2):
    a_list1 = list(s1)
    a_list2 = list(s2)
    a_list1.sort()
    a_list2.sort()
    pos = 0
    matches = True
    while pos < len(s1) and matches:
        if a_list1[pos] == a_list2[pos]:
            pos = pos + 1
        else:
            matches = False
    return matches

陷阱來了：乍看最後只有一個單層迴圈比對 n 個字元，好像是 $O(n)$？

別忘了那兩次 sort() 不是免費的！排序通常是 $O(n^2)$ 或 $O(n \log n)$（後面章節會學）。排序的成本主導了後面的單層比對。

心法：分析整體 Big-O 時，要看最貴的那一步。這裡最貴的是排序，所以整體 Big-O 等於排序的數量級，而不是那個誤導人的單層迴圈。

深度探秘

解法三：暴力法 O(n!) 的恐怖

暴力法：把所有可能都試一遍

暴力法 (brute force) 的精神是「窮舉所有可能性」。對變位詞問題來說，就是用 s1 的字母產生所有可能的排列字串，再看 s2 有沒有出現在裡面。

問題在於排列的數量：第一個位置有 $n$ 種選擇、第二個有 $n-1$ 種、第三個有 $n-2$ 種……一路下去，總數是

$$n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 = n!$$

而 $n!$（階乘）成長得比指數 $2^n$ 還快。

若 s1 長 20 個字元，就有 $20! = 2{,}432{,}902{,}008{,}176{,}640{,}000$ 種候選字串。就算一秒處理一個，也要約 771 億年才跑得完！

flowchart TD
    A[暴力法 產生 s1 的所有排列] --> B[排列數為 n 階乘]
    B --> C[n 階乘 成長比 2 的 n 次方 還快]
    C --> D[20 個字元就要 771 億年]
    D --> E[結論 完全不可行]

生活妙喻

解法四：計數比對，聰明的線性解

用 26 個計數器數字母

解法四：計數比對 (count and compare) —— 兩個變位詞，每個字母出現的次數一定一樣（一樣多的 a、一樣多的 b……）。於是用 26 個計數器，分別數兩字串中各字母出現幾次，最後比兩排計數器是否完全相同。

def anagram_solution4(s1, s2):
    c1 = [0] * 26
    c2 = [0] * 26
    for i in range(len(s1)):
        pos = ord(s1[i]) - ord('a')
        c1[pos] = c1[pos] + 1
    for i in range(len(s2)):
        pos = ord(s2[i]) - ord('a')
        c2[pos] = c2[pos] + 1
    j = 0
    still_ok = True
    while j < 26 and still_ok:
        if c1[j] == c2[j]:
            j = j + 1
        else:
            still_ok = False
    return still_ok

就像兩家超商各自盤點 26 種商品的庫存表，最後把兩張表並排對一對——只要逐項清點，不必把商品兩兩配對。

關鍵：這裡的迴圈都沒有巢狀！前兩個數字母的迴圈各跑 n 次，第三個比對迴圈固定跑 26 次。

實用超能力

O(n) 的代價：用空間換時間

算一下計數比對法的 Big-O

把步數加起來：兩個數字母迴圈各 $n$ 次，比對迴圈固定 $26$ 次：

$$T(n) = 2n + 26$$

丟掉常數 26 與係數 2，得到 $O(n)$——線性！這是四種解法裡最好的。

但天下沒有白吃的午餐：解法四為了跑出線性時間，多用了兩個長度 26 的計數陣列——它犧牲空間換取時間。

心法：演算法設計常要在時間與空間之間取捨 (time-space trade-off)。這裡多用一點空間很划算；但若字母表有數百萬種字元，額外空間就值得擔心了。身為設計者，要依問題情境決定怎麼用運算資源最划算。

深度探秘

哪些 list 操作快、哪些慢

Python list 各操作的 Big-O

Python 設計者在實作 list 時做了取捨：讓最常用的操作盡量快，少數較不常用的操作就犧牲一些。結果如下表：

重點先記住：索引、index 指派、append、尾端 pop() 都是 $O(1)$（超快、與長度無關）；而 insert、pop(0)、in、del 等需要搬動或掃描元素的，是 $O(n)$。

生活妙喻

append vs 串接：建一條 list 的四種方法

建立 0 到 n 的清單，哪種寫法快？

書中比較四種建清單的方法：

def test1():           # 用串接 +
    l = []
    for i in range(1000):
        l = l + [i]

def test2():           # 用 append
    l = []
    for i in range(1000):
        l.append(i)

def test3():           # list comprehension
    l = [i for i in range(1000)]

def test4():           # list(range(...))
    l = list(range(1000))

用 timeit 跑 1000 次的結果（毫秒）：

串接 l = l + [i] 像每加一本書就整箱書搬到新箱子重排一次（$O(k)$）；append 則像直接把書塞進現有箱子的空位（$O(1)$）。難怪 append 快了 20 倍，而 list comprehension 又比 append 快約一倍。

實用超能力

為什麼 pop(0) 比 pop() 慢這麼多

pop() 與 pop(0) 的天壤之別

pop()（拿尾端）是 $O(1)$，但 pop(0)（拿開頭）是 $O(n)$。原因藏在 Python 的實作：從開頭拿走一個元素時，後面所有元素都要往前挪一格。

flowchart TD
    A[pop 從尾端拿] --> B[直接移除最後一個 其他不動] --> C[O 1]
    D[pop 0 從開頭拿] --> E[後面每個元素都往前挪一格] --> F[O n]

這是設計者刻意的取捨——正因如此，索引 x[i] 才能維持 $O(1)$。

用 timeit 在兩百萬元素的 list 上實測：pop() 約 0.0003 毫秒，pop(0) 約 4.82 毫秒，差了約 16,000 倍！而且在不同長度的 list 上重複測量會看到：pop() 耗時幾乎不變（平的線），pop(0) 耗時隨長度線性上升——正好印證 $O(1)$ 與 $O(n)$。

實戰心法：需要反覆從開頭刪元素時，別用 list 的 pop(0)；想清楚操作落在 $O(1)$ 還是 $O(n)$，在對的場合選對的工具，效能差距可能上萬倍。

深度探秘

字典用鍵存取，多數操作是 O(1)

Python dictionary 各操作的 Big-O

字典 (dictionary) 和 list 最大的不同：你用鍵 (key) 而不是位置來存取資料。它的操作效率如下：

重點：取值、設值、刪除、用 in 檢查某個鍵在不在，平均都是 $O(1)$——不論字典裡有多少筆資料都一樣快。

一個重要的小註腳：表中的效率是平均情況 (average case)。在某些罕見情形下，contains、get item、set item 可能退化成 $O(n)$；至於為什麼，要等後面講字典的實作方式時才會揭曉。

生活妙喻

list 的 in vs 字典的 in

找東西：翻箱倒櫃 vs 直接定位

同樣是檢查「某個值在不在容器裡」，list 和 dict 差很多：

• list 的 in 是 $O(n)$：得從頭一個一個比對，最壞要翻完整個 list。
• 字典的 in 是 $O(1)$：透過鍵直接定位，不管字典多大都一樣快。

list 找東西像在沒有索引的倉庫裡翻箱倒櫃，東西越多翻越久；字典找東西像查有頁碼的字典/電話簿，直接翻到那一頁，跟整本多厚無關。

flowchart TD
    A[檢查某值是否在容器中] --> B[用 list 的 in]
    A --> C[用字典的 in]
    B --> D[逐一比對 最壞翻完整個 list O n]
    C --> E[用鍵直接定位 O 1]

書中的對照實驗顯示：當容器有 10,000 筆時字典比 list 快約 89 倍；到了 990,000 筆時，竟快了約 11,603 倍！

實用超能力

用 timeit 做可靠的對照實驗

如何公平地比較 list 與 dict

書中用一段實驗驗證上述差異——對同樣的值，分別在 list 與 dict 上做 number in container：

import timeit
import random

for i in range(10000, 1000001, 20000):
    t = timeit.Timer("random.randrange(%d) in x" % i,
                     "from __main__ import random, x")
    x = list(range(i))            # x 是 list
    lst_time = t.timeit(number=1000)
    x = {j: None for j in range(i)}  # x 改成 dict
    d_time = t.timeit(number=1000)
    print("%d,%10.3f,%10.3f" % (i, lst_time, d_time))

結果：list 的 in 耗時隨規模線性上升（印證 $O(n)$）；dict 的 in 耗時幾乎恆定不變（印證 $O(1)$）——10,000 筆與 990,000 筆都約 0.004 毫秒。

為什麼用 timeit 而不是手動 time？

• 它在乾淨、隔離的命名空間裡跑（from __main__ import ... 把要測的東西匯入），避免你隨手建的變數干擾結果。
• 它重複執行多次（這裡每項 1000 次），用統計平均把『電腦剛好在忙』之類的雜訊抹平，量測更可靠。

實戰心法：當你要頻繁查詢「某個東西在不在」，且資料量大，優先選字典（或集合）而非 list——這是把 $O(n)$ 換成 $O(1)$ 的關鍵決策。