先把 Part I 的地基打穩

課本把 22 章分成三塊：第 1–4 章是背景（Java 複習、效能分析、漸進符號、實際量測），第 5–17 章是各種資料結構，第 18–22 章是演算法設計方法。 Part I 不教任何資料結構，但它是後面每一章的評分標準 —— 之後每個結構都要回答「這個操作要多少時間、多少空間」。

Part I 的四個問題

第 1 章：Java 的物件、介面、泛型方法怎麼寫？遞迴怎麼拆成 base + recursive component？
第 2 章：怎麼數出一個程式的時間與空間？（operation count、best/worst/average）
第 3 章：怎麼把數出來的式子化簡成 O、Ω、Θ？
第 4 章：為什麼理論相同的兩份程式，實際跑起來差好幾倍？（快取）

課本前提投影片第 1 章用的是 Java（Sahni 的 Java 版），不是 C++。本頁所有程式碼都照課本用 Java。

三種讀法

趕時間：只讀每章開頭的「先記這 3 件事」，四章加起來 12 條，五分鐘。
正常讀：讀完標必考和觀念的段落，補充可以跳過。折疊起來的「詳細推導」要看再點開。
考前：直接去練習題，做錯的題目會告訴你該回去看哪一章。

CH 01

Java 基礎與遞迴

Java Review & Recursion

55 頁讀懂了

先記這 3 件事

int x; 立刻有實體，預設 0。String s; 只有參考，預設 null。 new T[n] 給的是 n 個 null，物件還得一個個 new。
Object.equals 比的是記憶體位址 —— 想比內容就一定要覆寫。
遞迴＝ base component（不再遞迴）＋ recursive component（參數必須變小）。

primitive 與 nonprimitive 型別必考

這是整章最容易考、也最容易錯的一頁。差別在於 宣告的那一刻，到底有沒有產生實體（instance）。

互動實驗

宣告一行，記憶體長什麼樣？

點下一步逐行執行

0 / 4

執行到的位置

Stack（變數本身）

Heap（new 出來的物件）

位址只是示意值。重點是：int 的格子裡直接放 0， String 的格子裡放的是位址，宣告時是 null。

易錯點 String theString; 沒有建立任何 String 實體，只建立一個「可以指向 String 的參考」，預設值是 null。必須 theString = new String("Welcome"); 才真的有東西。對照 int theINT; —— 它立刻就有一個實體，預設值 0。

參數傳遞：Java 只有 call by value觀念

Formal parameter（形式參數）＝方法定義裡的 a, b, c； actual parameter（實際參數）＝呼叫時寫的 z = abc(2, x, y) 裡的 2, x, y。
Java 一律 call by value：把值複製一份給形式參數。
但如果參數是參考型別，複製的是位址。方法內改動該物件的內容 → 呼叫端看得到；方法內把參數重新指向別的物件 → 呼叫端看不到。這就是課本第 1.13 節說泛型方法「call by reference」的意思。

自己的資料型別：class Currency補充

課本用 Currency（資料成員 sign、dollars、cents）示範怎麼定義一個型別。真正要記的只有下面那個 new T[10] 的陷阱；兩張對照表要用時再查。

想看 class／instance 成員與存取修飾子對照表

對照	Class data member（`static`）	Instance data member
誰持有	整個類別共用一份	每個實體各有一份
宣告	static long dollars;	long dollars;
取用	Currency.PLUS	g.dollars
常見用途	常數（`static final`）、計數器	物件自己的狀態

Access modifier	同類別內	同 package	子類別	任何地方
`private`	✓	—	—	—
（不寫，package 預設）	✓	✓	—	—
`protected`	✓	✓	✓	—
`public`	✓	✓	✓	✓

建立實體的四種寫法

1.8.5 Creating instancesJava

Currency g, h, i, j;              // 只有參考，全是 null
g = new Currency();             // 預設建構子
h = new Currency(PLUS, 3L, (byte) 50);
i = new Currency(-2.50);

Currency[] balance = new Currency[10];   // 10 個 null 參考！
for (int m = 0; m < 10; m++)
    balance[m] = new Currency();          // 還得一個個 new

易錯點 new Currency[10] 只配置 10 個參考（全是 null），不會幫你建立 10 個 Currency 物件。少了那個 for 迴圈就是 NullPointerException。

繼承與覆寫：equals 的陷阱必考

沒寫 extends 的類別，預設 extends Object。 Object 給了兩個方法：equals 和 toString。
currA.equals(currB) 用 Object 的版本時，比的是記憶體位址，不是 sign / dollars / cents 的內容 → 必須自己覆寫 Currency.equals。
final、static、private 的方法不能被覆寫； final class 則完全不能被繼承。

泛型方法與三個介面觀念

Java 的 interface ＝一串常數（static final）＋一串沒有實作的方法標頭。課本靠介面讓同一個方法能吃各種型別 —— 這是後面所有資料結構都會用到的手法。

Computable：定義 add、multiply 等算術運算 → 泛型方法才能做加減乘除。
java.lang.Comparable：定義 compareTo → 泛型方法才能比大小。 x.compareTo(y) 回傳負數（x<y）、0（x=y）、正數（x>y）。
Operable：同時要求 Computable 和 Comparable 兩邊的方法。

記法要算 → Computable；要比 → Comparable；兩者都要 → Operable。泛型參數可以是 Object 的任何子類別，但不能是 primitive 型別 （所以才需要 Integer、Double 這些 wrapper 類別）。

遞迴必考

Direct recursion：方法 f 裡面直接呼叫 f。 Indirect recursion：f 呼叫 g，g 又呼叫 f。每個遞迴定義都必須有兩個部分：

Base component：直接給答案、不再遞迴。例如 n ≤ 1 → f(n) = 1。
Recursive component：右邊那個 f 的參數必須比 n 小，否則永遠停不下來。例如 f(n) = n · f(n−1)。

f(n) = 1 若 n ≤ 1 | f(n) = n · f(n−1) 若 n > 1 → f(−3) = f(0) = f(1) = 1，f(2) = 2，f(3) = 6

注意 f(−3) 也等於 1 —— 因為 base component 的條件寫的是 n ≤ 1，負數一樣落在 base。這是投影片故意設計的考點。

互動實驗

遞迴追蹤器：看堆疊長高再縮回去

投影片 p.45–47 的 (L2, n) 就是這個

函式

n

4

Call stack（往上長）

執行紀錄

步驟0 / 0

總呼叫次數0

最大堆疊深度0

傳回值—

把 fib 的 n 調到 6 以上，看「總呼叫次數」爆掉的速度 —— fib 的呼叫次數是 指數成長，因為同一個子問題被重算很多次。這正是第 3 章要量的東西，也是之後動態規劃要解決的問題。

連到第 2 章堆疊每長一層就要存一組 (a 的參考 4 + n 4 + return address 4) = 12 bytes。深度 n+1 層 → S_rSum(n) = 12(n+1) bytes。遞迴的空間成本就是這樣算出來的。

遞迴產生排列（permutation）

課本最後一個遞迴例子。想法是：從 E = {e₁, …, eₙ} 每次挑一個元素當開頭，剩下的 Eᵢ 再遞迴做排列，把開頭接上去。

perm({a,b,c}) = a·perm({b,c}) , b·perm({a,c}) , c·perm({a,b}) → 3! = 6 種

實作上不真的搬集合，而是在同一個陣列 list[0:n−1] 上用 prefix ＋ suffix：list[0:k−1] 是已固定的前綴， list[k:m] 是還要排列的後綴。 k = m 時只剩一種排列 → 直接輸出； k < m 時把 list[i]（i 從 k 到 m）換到位置 k，遞迴，再換回來。

互動實驗

排列遞迴樹：swap → 遞迴 → swap 回來

縮排代表遞迴深度 k

輸入元素

0 / 0

已輸出排列0

應有總數 n!6

輸出—

最多 4 個元素（4! = 24）。注意每個節點回傳前都會把 swap 還原 —— 少了這一步，陣列會被前一次遞迴弄亂，這是寫這題最常見的 bug。

程式結構、編譯與執行補充

點開看 package／javac／JVM／註解

Stand-alone program：有 main 方法，用 java ProgramName 執行。 Applet：有 init 方法，嵌在 HTML 裡由瀏覽器執行。
Package 就是放程式的目錄：java.awt（圖形）、java.io（輸入輸出）、 java.lang（wrapper 類別，自動 import）、java.util（工具）。
import java.io.*; 匯入整個 package； import java.io.PrintStream; 只匯入一個類別。
編譯與執行：.java 原始碼 → javac → .class bytecode → 在 JVM 上跑 —— 這就是 write once, run anywhere。JIT 再把 bytecode 譯成機器碼加速。
三種註解：//、/* */、以及給 javadoc 用的 /** */。

第 1 章重點速記

int x; 馬上有實體（預設 0）；String s; 只有參考（預設 null）。
new T[n] 給的是 n 個 null 參考，物件還要自己 new。
Java 只有 call by value；參考型別複製的是位址，所以「改內容」看得到、「改指向」看不到。
Object.equals 比位址 → 想比內容一定要覆寫。final/static/private 不能覆寫。
要算用 Computable、要比用 Comparable、都要用 Operable；泛型不吃 primitive。
遞迴＝ base component（不再遞迴）＋ recursive component（參數必須變小）。
遞迴的空間成本＝每層 frame 大小 × 最大深度，例如 12(n+1)。

CH 02

效能分析

Performance Analysis

20 頁讀懂了

正確性最重要 —— 但一個跑太久的正確程式幾乎沒用。這章就是在學怎麼用紙筆數出一個程式要多少記憶體、多少時間。注意：這章是「數」，第 3 章才是「化簡」。

先記這 3 件事

算空間只算 variable part（隨 n 變化的那部分）。迭代版循序搜尋 S(n) = 0；遞迴版加總 S(n) = 12(n+1)。
Rank 的比較次數是 n(n−1)/2 —— 不是投影片 p.14 寫的 (n+1)/2。
循序搜尋：best 1、worst n、average (n+1)/2；帶機率 p 時是 p(n+1)/2 + (1−p)n。

空間複雜度必考

程式要的記憶體分三塊：

Instruction space（指令空間）：編譯後的機器碼佔的空間。同一個式子 a+b+b*c+(a+b-c)/(a+b)/4 經過編譯器最佳化後，指令數會變少 → 指令空間會變。
Data space（資料空間）：變數與常數。 double[] a = new double[100] → 8 × 100 bytes； int[][] maze = new int[rows][cols] → 4 × rows × cols bytes。
Environment stack space（環境堆疊空間）：每次方法呼叫要存 return address、所有區域變數與形式參數。遞迴就是吃這一塊。

算空間複雜度時只算會隨 n 變化的那部分。所以迭代版的循序搜尋是 S_{sequentialSearch}(n) = 0 —— 不是「不佔空間」，而是「不佔隨 n 變化的空間」。

想看課本的正式寫法 S(p) = c + S_p(instance characteristics)

Fixed part（c）：指令空間、單純變數與常數 —— 和輸入大小無關。
Variable part（S_p）：動態配置的空間、遞迴堆疊 —— 隨輸入大小改變。

「instance characteristics」就是描述這筆輸入規模的參數（通常是 n）。因為 fixed part 是常數，寫複雜度時它會被吸收掉，所以考試只要算 S_p。

互動實驗

空間複雜度計算器

拖動滑桿看 variable part 怎麼變

程式片段

n

10

程式碼Java

Variable part0

公式—

空間複雜度—

Java 的 int 與參考各算 4 bytes、double 算 8 bytes（照課本的算法）。

關鍵對比同樣是「把陣列加總」：迭代版 空間 S(n) = 0， 遞迴版 空間 S(n) = 12(n+1)。時間都是 O(n)，但遞迴多付了線性的堆疊空間。這是「遞迴比較優雅，但不一定比較好」的具體代價。

時間複雜度：Operation count必考

精確算執行時間太難（跟機器、編譯器都有關），所以課本改用 operation count：挑一個或幾個具代表性的運算（加、乘、比較、交換…），數它做了幾次。

循序搜尋挑的是比較：迴圈 for (i = 0; i < n && a[i] != x; i++) 找不到時比了 max{n, 0} 次（寫成 max 是為了處理 n 可能 ≤ 0 的情況）。

Ranking：課本的招牌例子

一個元素的 rank ＝序列中比它小的元素個數 ＋ 在它左邊、和它相等的元素個數。加上後半句是為了讓重複的元素也有不同的 rank。

a = [4, 3, 9, 3, 7] → r = [2, 0, 4, 1, 3] （兩個 3：左邊那個 rank 0，右邊那個 rank 1）

互動實驗

Ranking 逐步計算

一次一個比較

陣列（逗號分隔）

0 / 0

i / j

a

r

i（目前處理的元素） j（拿來比的元素）

—

已做比較0

總比較次數 n(n−1)/210

時間複雜度O(n²)

外層 i = 1 … n−1，內層 j = 0 … i−1，所以比較次數 = 1 + 2 + … + (n−1) = n(n−1)/2。

投影片筆誤第 2 章 p.14 把 rank 的比較次數寫成 1+2+…+n = (n+1)/2 —— 這一行有兩個問題： 1+2+…+n 應該是 n(n+1)/2，而 rank 的實際次數是 n(n−1)/2。 (n+1)/2 其實是 p.16–17 那個循序搜尋的平均比較次數，兩頁混寫了。 考試寫 n(n−1)/2。

最佳、最差、平均必考

同一個程式，不同輸入的 operation count 不一樣，所以要分三種講：

Worst-case count ＝所有輸入中的最大值
Best-case count ＝所有輸入中的最小值
Average count ＝依各輸入出現機率加權的期望值

以循序搜尋為例（陣列長度 n）：

情況	比較次數	說明
Best	1	x 就在 `a[0]`
Worst	n	x 在最後一格，或根本不在陣列裡
Average（一定找得到）	(n+1)/2	(1+2+…+n) × 1/n，假設每格機率相同
Average（機率 p 找得到）	p(n+1)/2 + (1−p)n	找不到的那 (1−p) 要付滿 n 次

互動實驗

循序搜尋：三種 count 一起看

點格子選 x 的位置

陣列長度 n

8

找得到的機率 p

1.00

a

Best1

Worst8

Average4.50

你選的位置—

把 p 拉到 0（一定找不到），平均次數就會等於 worst case 的 n —— 因為每次都得掃完整個陣列。

第 2 章重點速記

空間＝ instruction + data + environment stack；只算 variable part。
S_{sequentialSearch}(n) = 0（迭代）；S_rSum(n) = 12(n+1)（遞迴）。
時間用 operation count：先挑代表運算，再數次數。
Rank ＝比它小的個數＋左邊和它相等的個數；比較次數 n(n−1)/2，即 O(n²)。
循序搜尋：best 1、worst n、average (n+1)/2；帶機率 p 時 p(n+1)/2 + (1−p)n。

CH 03

漸進符號

Asymptotic Notation

13 頁讀懂了

第 2 章數出 2n² + 3n 這種式子後，第 3 章只做一件事： 把不重要的項丟掉。因為 n 大的時候，最大項就決定了一切。

lim_n→∞ (2n² + 3n) / n² = 2，是個常數 —— 所以 2n² + 3n 的成長「就是」 n² 的成長。實務上的意思是：n 加倍，時間變 4 倍。

先記這 3 件事

解題一律先算 lim_n→∞ f(n)/g(n)： 0 → 只有 O；∞ → 只有 Ω；非零常數 → O、Ω、Θ 三個全中。
階梯背熟：1 < log n < n < n log n < n² < n³ < 2ⁿ < n!
寫答案時括號裡要化成單一項、去掉係數： 3n²+2n+6 → Θ(n²)。

為什麼「最大項」就夠了觀念

課本用兩個做同一件事的程式對比： t_A(n) = n² + 3n 和 t_B(n) = 43n。

互動實驗

常數大不代表贏：A 與 B 的交叉點

滑過圖上任一點看數值

t_A = n² + 3n t_B = 43n

n < 40A 比較快

n = 40打平（都是 1720）

n > 40B 比較快，且差距越拉越大

B 的常數（43）比 A 大很多，小 n 時吃虧；但 A 的最大項是 n²、 B 是 n，n 一大就完全逆轉。 漸進分析就是只看這個最大項。

誰比誰大：漸進大小的定義必考

設 p(n)、q(n) 都是非負函數。課本的定義只有一條極限：

p(n) 漸進大於 q(n) ⟺ lim_n→∞ q(n) / p(n) = 0 （同時也就是 q(n) 漸進小於 p(n)）

例：lim (10n+7) / (3n²+2n+6) = 0 → 10n+7 漸進小於 3n²+2n+6。背下這條成長率階梯：

1 < log n < n < n log n < n² < n³ < 2ⁿ < n!

互動實驗

成長率階梯

點下面的函式開關

n 的範圍

32

y 軸刻度

檢視

切到線性刻度看看：2ⁿ 一開就把其他全部壓成貼著底線的平線 —— 這說明為什麼談成長率時只有對數刻度看得出差別。需要確切數字時切到表格。

O、Ω、Θ 三個符號必考

符號	意思	lim f(n)/g(n)	g(n) 的角色
f ∈ O(g)	f 漸進小於或等於 g	0 或常數 c	上界 upper bound
f ∈ Ω(g)	f 漸進大於或等於 g	∞ 或常數 c	下界 lower bound
f ∈ Θ(g)	f 漸進等於 g	常數 c（≠ 0）	上下界都是

關鍵關係 Θ 成立 ⟺ O 和 Ω 同時成立。 所以看到 12n+6 ∈ Θ(6n+2)，就知道 O 和 Ω 也都對。反過來，只有 O 成立（極限 = 0）時，Θ 一定不成立。

點開看課本的 6 個例子（有幾個是刻意不成立的）

式子	成立？	理由
10n+7 ∈ O(3n²+2n+6)	✓	極限 = 0
12n+6 ∈ O(6n+2)	✓	極限 = 2（常數）
3n²+2n+6 ∈ O(10n+7)	✗	極限 = ∞，n² 比 n 大
8n⁴+9n² ∈ O(100n³−3)	✗	極限 = ∞，n⁴ 比 n³ 大
8n⁴+9n² ∈ Θ(n⁴)	✓	極限 = 8
6n^1.5+12 ∈ Θ(n²)	✗	極限 = 0 → 只有 O(n²)，不是 Θ

寫法慣例寫 O / Ω / Θ 時要把括號裡化成單一項、去掉係數： 10n+7 → O(n)，3n²+2n+6 → O(n²)， 8n⁴+9n² → Θ(n⁴)。

互動測驗

O / Ω / Θ 判斷

選出所有成立的，可多選

第 1 / 10 題

答對0

答錯0

已作答0 / 10

解題步驟固定：先算 lim f(n)/g(n) → 0 就是只有 O；∞ 就是只有 Ω；非零常數就是 O、Ω、Θ 三個全中。

第 3 章重點速記

一切都從 lim_n→∞ f(n)/g(n) 出發：0 → O、∞ → Ω、常數 → O+Ω+Θ。
階梯背熟：1 < log n < n < n log n < n² < n³ < 2ⁿ < n!
O 是上界、Ω 是下界、Θ 是兩者兼具；Θ ⟺ O 且 Ω。
括號裡要化成單項無係數：3n²+2n+6 → Θ(n²)。
常數項只在 n 小的時候有意義（n²+3n vs 43n 在 n = 40 交叉）。

CH 04

效能量測與快取

Performance Measurements

14 頁讀懂了

第 3 章說「複雜度一樣就差不多快」。第 4 章打自己的臉：兩份都是 O(n³) 的矩陣乘法，只把三層迴圈的順序從 ijk 換成 ikj，實測可以快好幾倍。原因不在指令數，在快取（cache）。

先記這 3 件事

Java／C 的二維陣列是 row major：同一列的元素位址連續。快取一次搬一整條 line，所以照列走命中、照欄走失誤。
ijk 順序讓 b[k][j] 照欄走 → 失誤多。 ikj 順序讓 a、b、c 全照列走 → 失誤少。
兩者運算次數完全相同、都是 O(n³)，實測時間卻差好幾倍 —— 複雜度看不出快取。

矩陣乘法與 row-major 存放必考

矩陣乘法的定義：

c[i][j] = Σ_k=1..n a[i][k] · b[k][j] ， 1 ≤ i ≤ n，1 ≤ j ≤ n

關鍵是 Java（和 C）用 row major 存二維陣列 —— a[0][0], a[0][1], a[1][0], a[1][1] 依序排在記憶體裡。而快取一次搬進來的不是一個元素，是一整條 cache line（一段連續位址）。

照列（row）走：下一個元素就在旁邊 → 同一條 line 裡 → 命中。
照欄（column）走：每跳一次就跨過一整列 → 落在不同 line → 失誤。

課本 Program 2.2 和 4.4 都用 ijk 順序： a 和 c 照列走（好），但 b[k][j] 的內層是 k 在變 → 照欄走（壞）。改成 ikj 之後，三個矩陣全部照列走，L2 cache 失誤大幅下降。

ijk 順序（課本 Program 2.2）b 照欄走

for (i = 0; i < n; i++)
  for (j = 0; j < n; j++)
    for (k = 0; k < n; k++)
      c[i][j] += a[i][k] * b[k][j];

ikj 順序（課本 Program 4.5）全部照列走

for (i = 0; i < n; i++)
  for (k = 0; k < n; k++)
    for (j = 0; j < n; j++)
      c[i][j] += a[i][k] * b[k][j];

看清楚差別兩段程式算的東西完全一樣，乘法與加法次數完全一樣（都是 n³ 次）。差別只在內層迴圈變數是誰：ijk 的內層是 k，讓 b[k][j] 的列索引在變； ikj 的內層是 j，讓 b[k][j] 和 c[i][j] 的欄索引在變 → 位址連續。

互動實驗

兩種順序同步賽跑：誰的 cache miss 少？

按播放

速度

0 / 64

此列目前在快取中本步存取的元素

簡化模型：4×4 矩陣、快取共 4 條 line、每條 line 剛好裝一整列（4 個元素）、 LRU 汰換。每一步是一次迴圈迭代，依序存取 a[i][k]、b[k][j]、c[i][j]。真實快取的 line 通常是 64 bytes、階層也更多，但「照列走 vs 照欄走」的差異就是這個機制。

結論漸進複雜度告訴你哪個演算法值得寫；快取行為告訴你同一個演算法怎麼寫才快。兩件事都要會，而且第 3 章看不出第 4 章的差別 —— 這就是課本把它們排在一起的理由。

第 4 章重點速記

Java / C 的二維陣列是 row major：同一列的元素位址連續。
快取一次搬一整條 line；照列走命中、照欄走失誤。
ijk：a、c 照列，b 照欄 → 失誤多。 ikj：a、b、c 全照列 → 失誤少。
兩者運算次數相同、複雜度同為 O(n³)，實測時間卻差很多。

練習

練習題

28 problems · Part I

還沒開始

計算題直接填數字，觀念題四選一。答完會給逐步詳解，答錯的題目下面會告訴你回去看哪一節。

範圍

1 / 28

HW

投影片上的作業

Homework, as listed on the slides

照投影片最後一頁抄下來的，方便對照。頁碼是課本頁碼。

作業	出處	題目	乙班 (B)	甲班 (A)
HW 1	Ch 1 p.55	Exercise 27	10/20	10/23
HW 1	Ch 2 p.75	Exercise 7	10/20	10/21
HW 2	Ch 2 p.100–101	Exercise 9、Exercise 26	10/27	10/28
HW 2	Ch 3 p.115	Exercise 1(a)(b)、2(a)(b)、5(c)(d)	10/27	10/28

注意第 1 章與第 2 章的投影片對甲班 HW 1 寫了不同日期（10/23 與 10/21），兩份投影片本身就不一致 —— 以老師課堂公告或最新版投影片為準。另外三份投影片都寫著抄作業一律期末總分 −5。