Welcome — what's an algorithm anyway? · 欢迎 —— 什么是算法？
An algorithm is just a step-by-step recipe for getting a job done with a computer. The recipe for making instant noodles is an algorithm. So is the way Google sorts a billion search results in 0.4 seconds, the way Google Maps picks a route, and the way Spotify decides what to play next. Different jobs need different recipes — and some recipes are way faster than others.
This page walks through sixteen of the most useful recipes. Ten of them come from a friendly book called Grokking Algorithms; the other six show up so often in real software that you'll keep meeting them anyway. For each one you get:
- A one-paragraph idea in plain English.
- A picture showing what's happening.
- Short, runnable Python you can paste into a shell.
- A worked example with real numbers — follow along with your finger.
- A "Going deeper" section explaining why the algorithm works and where it can trip you up.
- A speed badge and one or two places this algorithm gets used in real life.
Five words to know before you start
算法就是一份让计算机按部就班完成任务的食谱。煮泡面的步骤是算法。Google 在 0.4 秒里把十亿条搜索结果排好序、Google 地图算路线、Spotify 决定下一首歌的方式都是算法。不同的任务需要不同的食谱 —— 而且有些食谱比另一些快得多。
本页带你走过 16 个最有用的食谱。其中 10 个出自一本平易近人的书《算法图解》；另外 6 个在真实软件里出现得太频繁，绕不开。每个食谱都给你：
- 一段简明的想法（白话英文/中文）。
- 一张展示运行过程的图。
- 可以直接粘到 Python 终端运行的短代码。
- 用真实数字走一遍的示例 —— 拿手指跟着走。
- 解释为什么算法有效、什么地方容易踩坑的"深入了解"。
- 一个速度徽章和一两个真实使用场景。
开始前要知道的五个词
1. Foundations — how we talk about speed · 1. 基础 —— 怎么谈论速度
Two ideas come up in almost every algorithm: Big-O notation, which tells us how a recipe slows down as the input grows, and recursion, where a function solves a problem by calling a smaller version of itself.
1.1 Big-O notation · 1.1 大 O 记号
🎬 中文白板讲解 · Chinese whiteboard explainer (~2 min)
Idea
Big-O describes the shape of how slow an algorithm gets when you give it more stuff to chew on. It doesn't measure seconds — it measures how the number of steps grows. If doubling the input doubles the work, that's O(n). If doubling the input adds just one more step, that's O(log n) — incredibly fast. If doubling the input quadruples the work, that's O(n²) — painful.
The picture — same input, very different growth
The growth-rate ladder
| Notation | Name | Steps for 1,000,000 items | You see it in… |
|---|---|---|---|
O(1) | Constant | 1 | Reading arr[5] from a list |
O(log n) | Logarithmic | ~20 | Binary search, finding a word in a dictionary |
O(n) | Linear | 1,000,000 | Scanning every item in a list once |
O(n log n) | n times log n | ~20,000,000 | Most fast sorting (merge sort, quicksort) |
O(n²) | Quadratic | 1,000,000,000,000 | Slow sorts (selection sort, bubble sort) |
O(2ⁿ) | Exponential | more than atoms in the universe | Brute-force search for hard problems |
Worked example
Picture searching a sorted list of one million names. Linear search checks them one by one — up to a million tries. Binary search chops the list in half, checks the middle, chops the right half in half again, and so on — only about twenty tries. On ten items the difference is nothing. On a million items the difference is the difference between "instant" and "go get a snack".
Going deeper
Why we drop constants. If algorithm A takes 5n + 100 steps and algorithm B takes n steps, both are O(n). The constant 5 and the +100 disappear because Big-O is about asymptotic behaviour — what happens as n grows large. At n=10 the constants matter a lot (algorithm A takes 150 steps, B takes 10 — a 15× difference!). At n=1,000,000 they barely matter (5,000,100 vs 1,000,000 — only 5× different, and both algorithms scale identically). Big-O answers "which will win as data grows?" — not "which is faster on my laptop today?"
The opposite trap: small data. An "O(1)" hash table lookup has real overhead — hashing the key, walking a chain. For a list of 5 items, a simple O(n) linear scan often beats it. Real engineers profile actual code on realistic inputs, then reach for Big-O to understand how things will scale. Big-O doesn't replace measurement; it explains it.
Worst, average, and amortized. Big-O usually quotes the worst case. Hash table lookup is "O(1) average, O(n) worst" — meaning on typical inputs you'll never see the worst, but a malicious attacker who crafts inputs to all collide on the same slot can make it slow. "Amortized" means averaged over many operations — appending to a Python list is O(1) amortized, even though an individual append occasionally triggers an O(n) resize.
核心想法
大 O 记号描述当输入变多时，算法所需的步数如何增长。它不衡量秒数 —— 它描述增长的形状。如果输入翻倍、步数也翻倍，那就是 O(n)。如果输入翻倍、只增加一步，那就是 O(log n) —— 快得离谱。如果输入翻倍、步数变成四倍，那就是 O(n²) —— 痛苦。常数和增长更慢的项会被舍掉：O(3n + 50) 简化为 O(n)。
图解 —— 同样的输入，截然不同的增长
请参见上方英文版的同一张增长率对比图。横轴是输入大小 n，纵轴是步数：O(1) 平直、O(log n) 几乎不动、O(n) 是直线、O(n²) 急速向上。同样的输入，五种算法的差距随 n 增大被拉得越来越开。
增长率天梯
| 记号 | 名称 | n = 1,000,000 时的步数 | 出现在…… |
|---|---|---|---|
O(1) | 常数 | 1 | 读取 arr[5] |
O(log n) | 对数 | 约 20 | 二分查找、查字典 |
O(n) | 线性 | 1,000,000 | 遍历一遍列表 |
O(n log n) | n 乘 log n | 约 20,000,000 | 大多数快速排序算法（归并、快速排序） |
O(n²) | 平方 | 1,000,000,000,000 | 慢速排序（选择、冒泡） |
O(2ⁿ) | 指数 | 难以想象 | 困难问题的暴力搜索 |
示例演算
设想在一百万个名字组成的有序列表里查找。线性扫描一个一个看 —— 最坏要看一百万次。二分查找把范围对半切，对半切，再对半切 —— 最多约 20 次。十个元素时两者差不多；一百万个元素时差距就是"瞬间完成"和"走开吃顿点心"的区别。
深入了解
为什么要舍掉常数。如果算法 A 用 5n + 100 步，算法 B 用 n 步，两者都是 O(n)。常数 5 和 +100 会消失，因为大 O 描述的是渐近行为 —— 当 n 变大时会发生什么。在 n = 10 时常数很重要（150 vs 10，15 倍差距！）；在 n = 1,000,000 时几乎无所谓（5,000,100 vs 1,000,000，只差 5 倍，而且两者都是线性增长）。大 O 回答的是"数据变大时谁会胜出？" —— 不是"今天在我的笔记本上谁更快？"
反过来的陷阱：小数据。"O(1)" 的哈希表查找有真实的开销 —— 算哈希、走链表。对一个只有 5 个元素的列表，简单的 O(n) 线性扫描往往更快。真实的工程师会先在真实数据上测速，再用大 O 去理解它会怎么扩展。大 O 不能取代测量；它解释测量。
最坏、平均、摊还。大 O 通常指最坏情况。哈希表查找是"平均 O(1)，最坏 O(n)" —— 在常见输入上你永远见不到最坏，但精心构造让所有键碰撞到同一槽的恶意输入可以让它变慢。"摊还"意味着多次操作平均下来 —— 给 Python 列表 append 是 O(1) 摊还，即便偶尔一次会触发 O(n) 的扩容。
1.2 Recursion · 1.2 递归
🎬 中文白板讲解 · Chinese whiteboard explainer (~2 min)
Idea
A recursive function is one that calls itself on a smaller piece of the same problem. It needs two parts: a base case — the easiest version that it can answer right away — and a recursive case — where it reduces the problem and calls itself again. Without a base case the function would call itself forever.
Think of opening a stack of Russian nesting dolls. You open one (recursive case), find another inside, open that one… until you reach the tiny solid one in the middle (base case). Then you put them all back together going outward.
What's a factorial?
Before we write the code, let's nail down what we're computing. The factorial of a positive whole number — written with an exclamation mark, like 4! ("four factorial") — is what you get by multiplying every whole number from 1 up to that number:
Factorials count the number of ways to arrange n different things in a row. Three people in a queue can stand in 3! = 6 different orders. A shuffled deck of 52 cards has 52! ≈ 8 × 10⁶⁷ possible arrangements — more than the number of atoms in our galaxy. They grow ridiculously fast, which is why factorials are a classic first example of why algorithm speed matters.
Why recursion is the natural way to write this: notice the pattern 4! = 4 × 3!. And 3! = 3 × 2!. And 2! = 2 × 1!. Each factorial is defined in terms of a smaller factorial — exactly the shape recursion is good at.
Python
def factorial(n):
if n <= 1: # base case — stops the recursion
return 1
return n * factorial(n - 1) # recursive case — smaller problem
print(factorial(4)) # 24
Reading the code line by line
def factorial(n):— declares a function calledfactorialthat takes one input,n. After this line, Python knows whatfactorialmeans but hasn't actually run anything yet.if n <= 1:— the base case check. Ifnis 0 or 1, the answer is just 1 and no more work is needed.return 1— hand back 1 and stop. This is what eventually halts the recursion. Without it, the function would call itself forever.return n * factorial(n - 1)— the recursive case. To computen!, multiplynby the factorial ofn - 1. Python pauses on this line, calls itself with the smaller input, waits for the answer to come back, then does the multiplication.print(factorial(4))— actually calls the function withn = 4and prints whatever it returns. This is the line that kicks the whole chain of recursive calls into motion.
Five lines of real code do something that, in a language without recursion, would take a loop, a running total, and careful index handling. Recursion lets you describe the idea directly — "n! is n times (n−1)!" — and the computer figures out the bookkeeping.
What happens when you call factorial(4)
Going deeper
What's actually happening in memory. When a function calls another function, your computer allocates a small chunk of memory called a stack frame. It holds the function's local variables and the address to return to when the function finishes. Calls pile up: factorial(4)'s frame sits at the bottom, factorial(3)'s frame sits on top, then factorial(2), then factorial(1). When factorial(1) returns its answer, its frame is popped off and factorial(2) resumes. The "call stack" is a literal stack in your computer's RAM.
Why Python sets a recursion limit. Python caps recursion depth at 1000 by default. Without a cap, a runaway recursion would fill memory and crash the whole interpreter. You can raise the limit with sys.setrecursionlimit(10000), but if you need more than a few thousand levels, you should usually rewrite the algorithm as a loop instead. Some languages (Scheme, Haskell, Scala) automatically convert "tail recursive" functions into loops; Python deliberately doesn't, because the language designer felt the loss of stack traces would hurt debugging more than it would help.
When to choose recursion over iteration. Recursion is the natural fit when the data is itself recursive — trees, file systems, nested JSON, HTML documents, family trees. A function that processes a tree by handling the root and then recursively handling each subtree practically writes itself. For plain flat lists, an iterative for loop is usually clearer and avoids the call-stack overhead.
- Save the code above as
factorial.pyand run it. You should see24. - Now change
print(factorial(4))toprint(factorial(10)). What number do you get? - Now delete the two lines starting with
if n <= 1:and run it. Python will eventually crash withRecursionError: maximum recursion depth exceeded— because without a base case, the function never stops calling itself. Every recursive function needs a base case.
核心想法
递归函数针对同一问题的更小版本调用自身。它需要两部分：基础情况 —— 最容易、能直接回答的版本 —— 和递归情况 —— 把问题缩小再调用自身。没有基础情况，函数会永远调用自己。
想象打开一摞俄罗斯套娃。你打开一个（递归情况）找到里面更小的一个，再打开它…… 直到中间那个最小的实心的（基础情况）。然后你按相反方向把它们一层层套回去。
什么是阶乘？
写代码前先搞清楚我们要算的是什么。一个正整数的阶乘（写作 4!，读作"四的阶乘"）就是从 1 一路乘到这个数：
阶乘计算的是 n 个不同物品能排成多少种顺序。三个人排队有 3! = 6 种排法。一副 52 张洗过的扑克有 52! ≈ 8 × 10⁶⁷ 种可能 —— 比我们银河系里的原子还多。它增长得离谱地快，所以阶乘是讲"算法速度为什么重要"的经典开场白。
为什么递归是写这个的自然选择：注意 4! = 4 × 3!。而 3! = 3 × 2!。而 2! = 2 × 1!。每一个阶乘都用一个更小的阶乘来定义 —— 这正是递归擅长的形状。
Python
def factorial(n):
if n <= 1: # 基础情况 —— 停下来
return 1 # 0! 和 1! 都定义为 1
return n * factorial(n - 1) # 递归情况 —— 更小的问题
print(factorial(4)) # 24
逐行读懂代码
def factorial(n):—— 声明一个名为factorial、接收一个参数n的函数。这一行之后 Python 只是知道factorial是什么，还没真正运行任何东西。if n <= 1:—— 基础情况的检查。如果n是 0 或 1，答案就是 1，不用再算了。return 1—— 把 1 交回去并停下来。这就是让递归有终止的那一行。没有它，函数会永远调用自己。return n * factorial(n - 1)—— 递归情况。要算n!，先用n - 1调用自己，等结果回来，再做乘法。print(factorial(4))—— 真正用n = 4调用函数并打印结果。这一行启动整个递归链。
五行真代码做的事情，如果没有递归就需要循环、累加变量和小心的下标处理。递归让你直接表达想法 —— "n! 就是 n 乘以 (n−1)!" —— 簿记的事交给计算机。
调用 factorial(4) 时发生了什么
深入了解
内存中实际发生了什么。当一个函数调用另一个函数时，计算机分配一小块内存称为栈帧。它保存这个函数的局部变量和函数结束后要返回的地址。调用层层堆叠：factorial(4) 的栈帧在最底下，factorial(3) 的栈帧在它上面，然后是 factorial(2)、factorial(1)。当 factorial(1) 返回答案时，它的栈帧被弹掉，factorial(2) 继续运行。"调用栈"是计算机 RAM 里真实存在的一摞东西。
为什么 Python 设递归深度上限。Python 默认把递归深度限制在 1000。没有上限的话，失控的递归会撑爆内存、把整个解释器搞崩。可以用 sys.setrecursionlimit(10000) 调高，但如果你真需要几千层递归，通常应该改写成循环。某些语言（Scheme、Haskell、Scala）自动把"尾递归"函数编译成循环；Python 故意不这么做，因为语言设计者认为损失栈跟踪信息对调试的伤害大于优化的好处。
什么时候选递归而不是迭代。当数据本身是递归结构时 —— 树、文件系统、嵌套 JSON、HTML 文档、家谱 —— 递归是自然选择。一个函数处理树的方式是"处理根，然后递归处理每个子树"，几乎写出来就是对的。对于扁平列表，迭代的 for 循环通常更清晰、也避免调用栈开销。
- 把上面的代码保存为
factorial.py然后运行。应该看到24。 - 把
print(factorial(4))改成print(factorial(10))。结果是几？ - 现在删掉
if n <= 1:那两行再运行。Python 最终会以RecursionError: maximum recursion depth exceeded崩溃 —— 因为没有基础情况，函数永远不停。每个递归函数都需要基础情况。
2. Searching — Binary Search · 2. 查找 —— 二分查找
🎬 中文白板讲解 · Chinese whiteboard explainer (~2 min)
Idea
Binary search is the "guess a number between 1 and 100" game. The trick: every guess should cut what's left in half. Look at the middle of a sorted list — if your target is smaller, throw the right half away; if bigger, throw the left half away; otherwise you found it. One thousand items? At most ten guesses. One billion items? At most thirty.
The picture — guessing a number between 1 and 100
Python
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid # found it!
if arr[mid] < target:
lo = mid + 1 # target is in the upper half
else:
hi = mid - 1 # target is in the lower half
return None # not found
print(binary_search([1, 3, 5, 7, 9, 11, 13, 15], 7)) # 3
print(binary_search([1, 3, 5, 7, 9, 11, 13, 15], 10)) # None
Going deeper
Why it's famously easy to mess up. Binary search is one of the oldest algorithms in computing — the first version was published in 1946 — but the first published version that was actually bug-free didn't appear until sixteen years later. The dangers live in the boundaries: should the loop condition be lo < hi or lo <= hi? Should you update hi = mid or hi = mid - 1? Choosing wrong creates infinite loops or missed elements. Test your boundary cases carefully: empty list, one element, target at first position, target at last position, target absent.
The hidden overflow bug. The line mid = (lo + hi) // 2 looks innocent but is a famous source of bugs in other languages. In Java or C, if lo + hi exceeds the maximum integer value (~2 billion), it silently wraps to a negative number, and your binary search reads memory it shouldn't. The safer formula is mid = lo + (hi - lo) // 2 — mathematically equivalent but doesn't overflow. Python handles big integers natively so this bug doesn't bite, but the discipline is worth knowing.
Binary search beyond sorted lists. The deeper pattern is "binary search on a monotone condition" — anywhere you can ask "is the answer at most X?" and get a reliable yes/no, you can binary search. Find a square root by binary-searching on "is X*X > n?". Find the smallest server count that handles the traffic by binary-searching on "does N servers keep latency below 100ms?". Find the commit that introduced a bug by binary-searching on "did this commit pass the test?" (that's exactly what git bisect does).
13 in the first call — what index do you get back? Now try a number that isn't in the list, like 4. The function returns None because it ran out of places to look.
When to use
- Looking up a record in any sorted index (databases do this all day).
- Finding a word in a dictionary. Browsers find which CSS rule applies. Git finds which commit broke a test (
git bisect). - Python has it built in:
bisect.bisect_left(). Never re-implement it in production code.
核心想法
二分查找就是"猜 1 到 100 之间的数"游戏。每一次猜都把剩下的范围对半切。看排好序列表的中间元素：目标更小？扔掉右半。目标更大？扔掉左半。否则就找到了。每一步把搜索空间砍掉一半，所以 1000 项最多猜 10 次，十亿项最多 30 次。
图解 —— 猜 1 到 100 之间的数
Python
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid # 找到了！
if arr[mid] < target:
lo = mid + 1 # 目标在上半段
else:
hi = mid - 1 # 目标在下半段
return None # 范围耗尽 —— 不在列表里
print(binary_search([1, 3, 5, 7, 9, 11, 13, 15], 7)) # 3
print(binary_search([1, 3, 5, 7, 9, 11, 13, 15], 10)) # None
示例演算 —— 在 [20, 30, 40, 50, 80] 里找 40
深入了解
为什么它出了名地容易写错。二分查找是最古老的算法之一 —— 第一个版本 1946 年发表 —— 但第一个真正没 bug 的版本要到 16 年后才出现。陷阱藏在边界里：循环条件应该是 lo < hi 还是 lo <= hi？应该更新 hi = mid 还是 hi = mid - 1？选错就会出现死循环或漏掉元素。多测几种边界情况：空列表、单元素、目标在第一个位置、目标在最后一个位置、目标不存在。
隐藏的溢出 bug。mid = (lo + hi) // 2 这行看起来天真无邪，但在其他语言里是著名的 bug 来源。Java 或 C 里，如果 lo + hi 超出整数最大值（约 20 亿），它会静默回绕成负数，二分查找就会读到不该读的内存。更安全的写法是 mid = lo + (hi - lo) // 2 —— 数学上等价，但不会溢出。Python 原生处理大整数所以不会中招，但理解为什么对其他语言有意义。
不限于有序列表。更深一层的模式是"在单调条件上做二分查找" —— 任何你能问"答案至多是 X 吗？"并得到可靠是/否的地方，你都能做二分查找。在"X * X > n？"上二分能算平方根。在"N 台服务器能让延迟低于 100 毫秒吗？"上二分能找最少服务器数。在"这次提交测试还通过吗？"上二分能找出引入 bug 的那次提交（这就是 git bisect 的原理）。
13 —— 返回什么下标？再试一个不在列表里的数，比如 4。函数返回 None，因为范围被找空了。
适用场景
- 在任何有序索引里查记录（数据库整天在干这件事）。
- 查字典里的词。浏览器找该应用哪条 CSS 规则。Git 用二分定位破坏测试的那次提交（
git bisect）。 - Python 内置了：
bisect.bisect_left()。生产代码里别自己实现。
3. Sorting — three algorithms, three lessons · 3. 排序 —— 三个算法、三个教训
Three sorts give you the whole story: selection sort shows why naive is slow, merge sort shows what splitting the problem buys you, and quicksort shows how to be fast in practice.
3.1 Selection sort · 3.1 选择排序
🎬 中文白板讲解 · Chinese whiteboard explainer (~2 min)
Idea
Walk through the list, find the smallest number, swap it with the first slot. Then walk through what's left, find the next smallest, swap it into the second slot. Keep going. Simple to picture, easy to code, but always slow — for a list of 1,000 items you do about a million comparisons.
The picture — sorting [5, 2, 8, 1, 4]
Python
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
print(selection_sort([5, 2, 8, 1, 4])) # [1, 2, 4, 5, 8]
Going deeper
How bad does O(n²) actually get? Let's put numbers on it. On 100 items, selection sort does about 10,000 comparisons — instant. On 1,000 items, about a million comparisons — still under a millisecond. On 100,000 items, 10 billion comparisons — about ten seconds. On 1 million items, a trillion comparisons — you've left to make tea before it finishes. This is why nobody uses selection sort in production: the curve goes from "fine" to "terrible" with no warning as your data grows.
Why "in place" matters. Selection sort never allocates a second list — it just swaps elements within the original. For sorting a billion records that barely fit in RAM, an in-place algorithm is the only option; an algorithm that needs an extra copy would run out of memory. Quicksort is in-place. Merge sort isn't (it needs O(n) extra room). Sometimes the simpler algorithm wins on memory even when it loses on speed.
Cousins worth knowing. Selection sort always does O(n²) work regardless of input. Two close cousins are smarter: bubble sort can detect "no swaps happened this pass, so we're done" and stop early — O(n) on already-sorted input. Insertion sort does the same kind of early exit and is the fastest sort for very small lists (under ~20 items) — which is why Python's actual built-in sort (Timsort) uses insertion sort on its small chunks.
核心想法
遍历列表、找到最小值、跟最前面交换。然后对位置 1、2、3…… 重复同样的事。容易理解，永远很慢 —— 对 1000 个元素的列表大约要做一百万次比较。
图解 —— 排序 [5, 2, 8, 1, 4]
Python
def selection_sort(arr):
n = len(arr)
for i in range(n - 1): # i 是下一个要填的位置
min_idx = i # 先假设当前位置就是最小
for j in range(i + 1, n): # 扫描未排序的后半段
if arr[j] < arr[min_idx]:
min_idx = j # 找到了更小的
arr[i], arr[min_idx] = arr[min_idx], arr[i] # 交换到位
return arr
print(selection_sort([5, 2, 8, 1, 4])) # [1, 2, 4, 5, 8]
深入了解
O(n²) 到底有多糟？算具体数字。100 个元素时，选择排序约一万次比较 —— 瞬间。1000 个元素时，约一百万次 —— 还是不到一毫秒。100,000 个时，100 亿次 —— 大约 10 秒。100 万时，一万亿次 —— 你已经走开泡茶去了。这就是为什么生产代码不用选择排序：数据变大时曲线从"可以"瞬间变成"恐怖"，毫无预警。
"原地"的意义。选择排序不分配第二个列表 —— 它只是在原列表里交换。对内存里勉强装下的十亿条记录排序时，原地算法是唯一选择；需要额外副本的算法会内存爆炸。快速排序是原地的。归并排序不是（需要 O(n) 额外空间）。有时简单算法在内存上胜出，即便在速度上输了。
值得认识的近亲。选择排序不管输入是什么都做 O(n²) 次比较。两个更聪明的近亲：冒泡排序能检测到"这轮没发生交换"就提前停止 —— 已排好序的输入下是 O(n)。插入排序同样能提前退出，而且对很短的列表（约 20 个元素以下）比快速排序还快 —— 这就是 Python 内置 Timsort 在它的小段上用插入排序的原因。
3.2 Merge sort · 3.2 归并排序
🎬 中文白板讲解 · Chinese whiteboard explainer (~2 min)
Idea
Cut the list in half, sort each half, then merge the two sorted halves by repeatedly taking the smaller of the two fronts. The split is trivial, the merge is fast, and the recursion is only log n levels deep. Total work: n × log n — drastically faster than selection sort for big lists.
Merge sort is also stable: if two items have the same key, they keep their original order. Why care? Imagine sorting students by grade. With a stable sort, two students with the same grade stay in their original alphabetical order. With an unstable sort they might shuffle around.
The picture — split, then merge back up
Python
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= keeps it stable
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]
Going deeper
Why "divide and conquer" is a power pattern. Merge sort isn't just one algorithm — it's an instance of a general strategy you'll meet over and over. The pattern: break a problem into smaller pieces of the same shape, solve each piece, combine the results. Binary search uses it. Quicksort uses it. The Fast Fourier Transform (audio and image processing) uses it. Strassen's matrix multiplication uses it. Once you spot the pattern, half your algorithm-design work is done.
The invariant that makes it work. At every level of recursion, merge sort maintains one promise: "I am returning a sorted list". The base case (a list of 0 or 1 elements) is trivially sorted. The merge step combines two sorted lists into a sorted list — that's the only "real" work in the algorithm. If you trust the merge step, induction does the rest. This is a useful style of correctness reasoning: identify the one invariant that has to hold, prove the building block preserves it, and everything else follows.
The external sort story. In the 1940s and 50s, "computer memory" meant tape drives. You couldn't load a database into RAM because there wasn't any. Merge sort was chosen for sorting tape data specifically because the merge step reads sequentially from one tape and writes sequentially to another — no random seeks, which were painfully slow. Modern databases still use external merge sort for queries that produce more data than fits in memory. The 1945 algorithm is still the right answer for terabyte sorts in 2026.
When to use
- Datasets too big for memory. Sort chunks in RAM, write them to disk, merge them back. This is how databases sort terabytes.
- When you need a guarantee. Merge sort is
O(n log n)every single time — quicksort can sometimes be slower.
核心想法
把列表对半切，递归排好每一半，然后通过反复取两段最前的较小元素把它们合并起来。切分简单、合并线性、递归深度只有 log n。总工作量：n × log n —— 对大列表比选择排序快得多。
归并排序还是稳定的：相同键的元素保持原顺序。为什么在意？想象给学生按成绩排序。稳定排序下，同分的两个学生保持原先的字母顺序。不稳定排序可能把他们打乱。
图解 —— 切下去，再合上来
Python
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # 递归排左半
right = merge_sort(arr[mid:]) # 递归排右半
return merge(left, right) # 合并两段已排序
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= 保证稳定
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]
深入了解
为什么"分而治之"是个很强的模式。归并排序不只是一个算法 —— 它是你会反复见到的通用策略。模式是：把问题切成同样形状的小块、分别解决、再合并答案。二分查找用它。快速排序用它。快速傅里叶变换（音频和图像处理）用它。施特拉森矩阵乘法用它。一旦识别出这种模式，算法设计的一半工作就完成了。
让它成立的不变量。归并排序在每一层递归都遵守一个承诺："我返回一个已排序的列表。"基础情况（0 或 1 个元素的列表）自然是有序的。合并步骤把两个有序列表合成一个有序列表 —— 这是算法里唯一的"真活"。如果你信任合并步骤，数学归纳法搞定其余部分。识别一个必须成立的不变量，证明基本构件保持它，其余就水到渠成。
外部排序的故事。1940-60 年代，"计算机内存"等于磁带。你没法把数据库装进 RAM —— 因为没有 RAM。归并排序之所以被选为磁带数据排序，正是因为合并步骤顺序地从一卷磁带读、顺序地写到另一卷 —— 不需要昂贵的随机寻道。现代数据库到今天还在用外部归并排序处理超过内存的查询。1945 年的算法仍然是 2026 年 TB 级排序的正解。
适用场景
- 装不下内存的数据集。在 RAM 里排好若干小块，写到磁盘，再合并回来。数据库就是这样排 TB 级数据的。
- 需要保证时。归并排序永远是
O(n log n)—— 没有最坏情况意外（而快速排序偶尔会更慢）。
3.3 Quicksort · 3.3 快速排序
🎬 中文白板讲解 · Chinese whiteboard explainer (~2 min)
Idea
Pick any item from the list — call it the pivot. Split everything else into "smaller than pivot" and "bigger than pivot". The pivot is now in its final sorted spot. Recursively quicksort the two smaller piles. On a good day each pivot splits the list in half and you get O(n log n). On a bad day (already-sorted list, bad pivot choice) you get the same O(n²) as selection sort.
The picture — sorting [3, 6, 1, 8, 2, 4]
Python
def quicksort(arr):
if len(arr) < 2:
return arr # 0 or 1 element is already sorted
pivot = arr[0]
less = [x for x in arr[1:] if x <= pivot] # smaller pile
greater = [x for x in arr[1:] if x > pivot] # bigger pile
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([3, 6, 1, 8, 2, 4])) # [1, 2, 3, 4, 6, 8]
Going deeper
Why pivot choice is the whole game. Try quicksorting [1, 2, 3, 4, 5, 6, 7, 8] with the leftmost element as pivot. Pivot 1 splits the list into [] and [2,3,4,5,6,7,8] — almost no progress. Pivot 2 splits that into [] and [3,4,5,6,7,8] — same problem. You end up doing n levels of recursion instead of log n, hitting the dreaded O(n²) worst case. Production quicksort implementations dodge this two ways: randomized pivot (pick a random element each time — adversarial inputs become astronomically unlikely) or median-of-three (sample the first, middle, and last elements and pivot on the median).
Why it's the default in real systems. Even though merge sort has a better worst case, quicksort wins in practice on plain arrays. Two reasons: it sorts in place (no O(n) extra memory), and it has excellent cache behaviour — partitioning touches contiguous chunks of memory, which is exactly what CPU caches love. The standard sort in C++ (std::sort) and Java's Arrays.sort for primitives both use quicksort variants for these reasons.
QuickSelect: the bonus algorithm. A neat trick — quicksort's cousin can find the kth smallest element of a list in O(n) average time WITHOUT fully sorting the list. The idea: after partitioning, you know which pile contains the kth element, so recurse only into that one pile (not both). Used to find medians of huge datasets in linear time.
return inside quicksort: print(f"pivot={pivot} less={less} greater={greater}"). Now run it. You'll see exactly how the list gets carved up at each level of recursion.
核心想法
从列表里挑任意一个元素 —— 称作基准值（pivot）。把其余元素分成"比基准小"和"比基准大"两堆。基准值本身现在就在它最终的有序位置上。对两堆各自递归地快速排序。运气好时每次基准把列表对半切，得到 O(n log n)。运气坏时（已排好序的列表 + 坏的基准选择），就得到跟选择排序一样的 O(n²)。
图解 —— 排序 [3, 6, 1, 8, 2, 4]
Python
def quicksort(arr):
if len(arr) < 2:
return arr # 0 或 1 个元素已经有序
pivot = arr[0] # 选第一个元素作基准
less = [x for x in arr[1:] if x <= pivot] # 不大于 pivot 的元素
greater = [x for x in arr[1:] if x > pivot] # 大于 pivot 的元素
return quicksort(less) + [pivot] + quicksort(greater) # 两边各排好，pivot 夹中间
print(quicksort([3, 6, 1, 8, 2, 4])) # [1, 2, 3, 4, 6, 8]
深入了解
为什么基准的选择就是一切。试着用最左元素作基准排序 [1, 2, 3, 4, 5, 6, 7, 8]。基准 1 把列表切成 [] 和 [2,3,4,5,6,7,8] —— 几乎没进步。基准 2 切成 [] 和 [3,4,5,6,7,8] —— 同样的问题。你做了 n 层递归而不是 log n 层，撞上了可怕的 O(n²) 最坏情况。生产级快速排序通过两种方式避开：随机基准（每次选随机元素 —— 恶意输入变得天文般罕见）或三数取中（采样第一、中间、最后三个元素，取中位数）。
为什么它是真实系统的默认选择。虽然归并排序最坏情况更好，快速排序在真实数组上胜出。两个原因：它原地排序（不需要 O(n) 额外内存），并且具有极佳的缓存行为 —— 分区操作触及连续的内存块，正是 CPU 缓存喜欢的。C++ 的标准排序（std::sort）和 Java 基本类型的 Arrays.sort 都使用快速排序变种。
QuickSelect：附赠算法。一个漂亮的小技巧 —— 快速排序的近亲可以在不完整排序的情况下，平均 O(n) 时间找到列表的第 k 小元素。思路：分区之后你知道第 k 个位置在哪一堆，所以只往那一堆里递归（而不是两堆都递归）。这是怎么不排序找到一个巨大数据集的中位数。
quicksort 函数 return 那行之前加上：print(f"pivot={pivot} less={less} greater={greater}")。再运行。你会清楚地看到每一层递归列表如何被切开。
4. Data structures — the four you'll use most · 4. 数据结构 —— 最常用的四个
An algorithm's speed often depends more on its data structure than on its code. These four — hash table, heap, binary search tree, and union-find — quietly power most of the algorithms further down this page.
4.1 Hash tables · 4.1 哈希表
🎬 中文白板讲解 · Chinese whiteboard explainer (~2 min)
Idea
A hash table is a magic phone book: give it a name, get a phone number back instantly. The "magic" is a hash function — a formula that turns any string into a slot number in a small array. Look up the same name → same slot → same answer. In Python, every dictionary ({}) is a hash table.
What if two names hash to the same slot? That's called a collision, and one common fix is "separate chaining": each slot holds a tiny list of (key, value) pairs.
The picture — three names, one collision
Python — the built-in dict
phone_book = {}
phone_book["alice"] = "081-234-5678"
phone_book["bob"] = "082-987-6543"
print(phone_book["alice"]) # "081-234-5678"
print("bob" in phone_book) # True
Python — building one from scratch
class HashMap:
def __init__(self, size=8):
self.size = size
self.buckets = [[] for _ in range(size)]
def put(self, key, value):
idx = hash(key) % self.size
bucket = self.buckets[idx]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value) # update existing
return
bucket.append((key, value)) # collision-tolerant insert
def get(self, key):
idx = hash(key) % self.size
for k, v in self.buckets[idx]:
if k == key:
return v
return None
Going deeper
What makes a hash function good? Three properties matter. First, deterministic: the same key must always hash to the same slot, every run, every machine. Second, uniform: keys should spread evenly across slots — if every key landed in slot 0, your hash table would degrade to a linked list. Third, fast: computing the hash has to be cheap, or the "O(1) lookup" stops being O(1) in practice. Cryptographic hash functions like SHA-256 are perfectly uniform but way too slow for hash tables — they're designed for security, not speed. Python uses its own fast hash internally.
Load factor and resizing. The load factor is the ratio of items to slots. As you add more items, collisions become more likely and lookups slow down. Most hash table implementations watch the load factor; when it crosses some threshold (~0.75 for Python dicts), they allocate a bigger array (usually double the size) and rehash every item into the new slots. That one resize is O(n), but it happens rarely enough that the per-insert cost averages to O(1) — a beautiful example of amortized analysis.
Two ways to handle collisions. Separate chaining (what we showed) keeps a small list at each slot. Open addressing puts colliding items into the next empty slot — no extra allocation, better cache behaviour, but trickier deletion and resizing. Python dicts use open addressing with a clever probing scheme. The choice doesn't matter for correctness, only performance.
phone_book = {}phone_book["you"] = "your number"phone_book["mum"] = "your mum's number"print(phone_book)— see your phone bookprint(phone_book["you"])— instant lookup
When to use
- Caches — remember the answer to a slow calculation so you don't redo it.
- Counting things —
collections.Counteris a hash table that tallies items. - Deduplication — "have I seen this before?" in O(1).
- DNS, web routers, environment variables — any "what's the value for this name?" question.
核心想法
哈希表是一个有魔法的电话本：给它一个名字，立刻得到一个号码。"魔法"是哈希函数 —— 一个把任何字符串变成小数组里某个槽位号的公式。查同一个名字 → 同一个槽位 → 同一个答案。在 Python 里，每个字典（{}）都是哈希表。
如果两个名字哈希到同一个槽位怎么办？这叫冲突，常见的解决办法是"分离链接"：每个槽位保存一个 (key, value) 对的小列表。
图解 —— 三个名字，一次冲突
Python —— 内置 dict
phone_book = {}
phone_book["alice"] = "081-234-5678"
phone_book["bob"] = "082-987-6543"
print(phone_book["alice"]) # "081-234-5678"
print("bob" in phone_book) # True
Python —— 从零写一个
class HashMap:
def __init__(self, size=8):
self.size = size
self.buckets = [[] for _ in range(size)]
def put(self, key, value):
idx = hash(key) % self.size
bucket = self.buckets[idx]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value) # 更新已有项
return
bucket.append((key, value)) # 容忍冲突的插入
def get(self, key):
idx = hash(key) % self.size
for k, v in self.buckets[idx]:
if k == key:
return v
return None
深入了解
什么样的哈希函数算好？三条性质很重要。首先，确定性：同样的键必须永远哈希到同一个槽位，每次、每台机器都一样。其次，均匀：键应该均匀分散到各个槽位 —— 如果所有键都落在槽位 0，哈希表会退化成链表。第三，快：算哈希必须便宜，否则"O(1) 查找"在实践中就不再是 O(1)。SHA-256 这样的密码学哈希函数完全均匀但对哈希表来说太慢 —— 它们是为安全设计的，不是为速度。Python 内部用自己的快速哈希。
负载因子与扩容。负载因子是元素数对槽位数的比。元素越多，冲突越可能、查找越慢。大多数哈希表实现会监视负载因子；超过某个阈值（Python dict 约 0.75）时，分配更大的数组（通常翻倍），把每一项重新哈希到新槽位。那一次扩容是 O(n)，但发生得足够稀疏，每次插入的成本均摊到 O(1) —— "摊还分析"的漂亮例子。
两种处理冲突的方法。分离链接（我们展示的方法）每个槽位保存一个小列表。开放寻址在槽位满时尝试下一个槽位 —— 不需要额外分配、缓存行为更好，但删除和扩容更复杂。Python dict 用的是开放寻址加上一种聪明的探测方案。选择不影响正确性，只影响性能。
phone_book = {}phone_book["you"] = "你的号码"phone_book["mum"] = "妈妈的号码"print(phone_book)—— 看看你的电话本print(phone_book["you"])—— 瞬间查找
适用场景
- 缓存 —— 记住慢函数的输出避免重复计算。
- 计数 ——
collections.Counter就是用哈希表统计项目。 - 去重 —— O(1) 内"我以前见过这个吗？"
- DNS、Web 路由器、环境变量 —— 任何"这个名字对应的值是什么？"
4.2 Heaps and priority queues · 4.2 堆与优先队列
🎬 中文白板讲解 · Chinese whiteboard explainer (~2 min)
Idea
A heap is a tree shaped like a tournament bracket where the smallest player always wins. The minimum is always at the top, so you can grab it instantly. Both inserting a new number and popping the smallest take only O(log n) — because the tree is always balanced. This is the perfect structure for a priority queue: "give me the next most urgent task".
The picture — the heap as a tree and as an array
Python
import heapq
heap = []
for x in [7, 3, 9, 1, 5]:
heapq.heappush(heap, x) # O(log n) per push
print(heapq.heappop(heap)) # 1 ← smallest first
print(heapq.heappop(heap)) # 3
print(heapq.heappop(heap)) # 5
# Heap-sort: push everything then pop everything
def heap_sort(items):
h = list(items)
heapq.heapify(h) # O(n) — build heap in place
return [heapq.heappop(h) for _ in range(len(h))]
print(heap_sort([7, 3, 9, 1, 5])) # [1, 3, 5, 7, 9]
Going deeper
The array-as-tree trick. A heap looks like a tree, but it's stored as a flat array — no pointers, no per-node allocation. The math: for the element at index i, its parent is at (i-1)//2, its left child at 2i+1, its right child at 2i+2. So [1, 3, 9, 7, 5] represents a tree where 1 is the root, 3 and 9 are its children, and 7 and 5 are 3's children. Because the whole tree lives in a contiguous chunk of memory, heaps are CPU-cache-friendly — fast in practice as well as in theory.
Sift-up and sift-down. Two small operations keep the heap rule alive. When you insert, you tack the new element onto the end of the array and sift up: swap it with its parent while the parent is bigger. When you pop the minimum, you replace the root with the last element and sift down: swap with the smaller child while it's smaller. Both take O(log n) because the tree's height is log n.
The O(n) heapify surprise. Building a heap from a random list looks like it should be O(n log n) — n inserts, each O(log n). But there's a smarter trick: pretend the array is already a heap, then sift down starting from the last non-leaf and working up. This is O(n), not O(n log n). The math works because most nodes are near the bottom of the tree, and bottom nodes barely sift at all. This is why heapify is faster than pushing items one at a time.
When to use
- Inside Dijkstra's algorithm (next section) — repeatedly grab the unvisited node with smallest distance.
- Top-K queries — keep a heap of size K, push every item, pop when it overflows.
- Task schedulers — operating system run queues, event loops, expiry timers.
核心想法
堆是一棵长得像锦标赛对战表的树，但最小的选手永远赢。最小值始终在顶上，所以你能瞬间拿到它。插入新数字和弹出最小都只要 O(log n) —— 因为树始终平衡。这是优先队列的完美数据结构："给我下一个最紧急的任务"。
图解 —— 堆作为树和作为数组
Python
import heapq
heap = []
for x in [7, 3, 9, 1, 5]:
heapq.heappush(heap, x) # 每次 push 是 O(log n)
print(heapq.heappop(heap)) # 1 ← 最小先出
print(heapq.heappop(heap)) # 3
print(heapq.heappop(heap)) # 5
# 堆排序 = push 全部，再 pop 全部
def heap_sort(items):
h = list(items)
heapq.heapify(h) # O(n) —— 原地建堆
return [heapq.heappop(h) for _ in range(len(h))]
print(heap_sort([7, 3, 9, 1, 5])) # [1, 3, 5, 7, 9]
深入了解
数组当树用的小把戏。堆看起来像一棵树，但实际上以扁平数组存储 —— 没有指针、每个节点也不需要分配。数学是这样：对于索引 i 处的元素，它的父节点在 (i-1)//2，左子节点在 2i+1，右子节点在 2i+2。所以 [1, 3, 9, 7, 5] 表示一棵 1 为根、3 和 9 是它的孩子、7 和 5 是 3 的孩子的树。因为整棵树躺在一块连续的内存里，堆对 CPU 缓存很友好 —— 实践中和理论上一样快。
上浮与下沉。两个小操作维护堆规则。插入时，把新元素挂到数组末尾然后上浮：只要父节点更大就跟父节点交换。弹出最小时，把根换成最后一个元素然后下沉：只要某个子节点更小就跟那个子节点交换。两者都是 O(log n)，因为树的高度是 log n。
O(n) heapify 的惊喜。从一个随机列表建堆看起来应该是 O(n log n) —— n 次插入、每次 O(log n)。但有个更聪明的办法：假装数组已经是堆，从最后一个非叶节点开始下沉、往上走。这是 O(n)，不是 O(n log n)。数学上成立的原因是：大部分节点都靠近树底，底部节点几乎不下沉。所以 heapify 比一个一个 push 进去快。
适用场景
- 在迪杰斯特拉算法内部（下一节）—— 反复取出距离最小的未访问节点。
- Top-K 查询 —— 保持大小为 K 的堆，每来一项就 push，超过就 pop。
- 任务调度 —— 操作系统运行队列、事件循环、过期定时器。
4.3 Binary search trees · 4.3 二叉搜索树
🎬 中文白板讲解 · Chinese whiteboard explainer (~2 min)
Idea
A binary search tree (BST) is a tree where every node follows one rule: everything in the left branch is smaller, everything in the right branch is bigger. Search, insert, and delete follow one path down the tree — on a balanced tree that's O(log n). The catch: if you insert already-sorted data into a plain BST it turns into a stick (linked list) and operations become O(n). Real software uses self-balancing variants — AVL trees, red-black trees — that rotate after each insert to keep the tree short.
The picture — building a BST from [8, 3, 10, 1, 6, 14]
Python
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root
def search(root, key):
if root is None or root.key == key:
return root
if key < root.key:
return search(root.left, key)
return search(root.right, key)
root = None
for k in [8, 3, 10, 1, 6, 14]:
root = insert(root, k)
print(search(root, 6) is not None) # True
Going deeper
The degenerate-stick problem. Insert 1, 2, 3, 4, 5, 6 into a plain BST in order. Every new number is bigger than every node already there, so it always goes to the right. Your "tree" is actually just a long stick — a linked list pretending to be a tree. Searching for 6 takes six hops, not log₂(6) ≈ 3. The BST didn't fail you; you gave it adversarial input. This is exactly the kind of pitfall that motivates self-balancing variants.
Self-balancing with rotations. AVL trees (1962, the first self-balancing BST) and red-black trees (1972, slightly looser balance but cheaper to maintain) detect imbalance after each insert and fix it with a rotation: a local rearrangement that swaps a parent and child without breaking the BST rule. Rotations are O(1), and a single insert needs at most a handful of them. The result: tree height stays in O(log n) no matter what order you insert in. Most language standard libraries' "sorted map" or "tree map" types use red-black trees underneath.
BSTs versus hash tables. When should you pick a BST instead of a hash table for fast lookup? Three cases. (1) When you need ordered iteration — a BST lets you walk through keys in sorted order; a hash table can't. (2) When you need range queries ("give me all keys between 100 and 200") — easy on a BST, hard on a hash table. (3) When you need predictable performance — hash tables are O(1) average but O(n) worst; balanced BSTs are O(log n) every time. Databases store indices in B-trees (a wide-fanout BST cousin) precisely because they need ordered iteration for SQL ORDER BY and range queries for SQL BETWEEN.
When to use
- Anywhere you need fast lookup AND ordered traversal. A hash table gives lookup but no order.
- Database indices use B-trees (wide-fanout BSTs). Filesystems, time-series buckets, in-memory range queries — all live on tree structures.
核心想法
二叉搜索树（BST）是一种每个节点遵守同一条规则的树：左子树里的一切都比它小，右子树里的一切都比它大。查找、插入、删除都沿着树往下走一条路径 —— 树平衡时是 O(log n)。陷阱是：把已排好序的数据插入到普通 BST，它会退化成棍子（链表），操作变成 O(n)。生产系统用自平衡变种 —— AVL 树、红黑树 —— 在每次插入后旋转以保持树短。
图解 —— 从 [8, 3, 10, 1, 6, 14] 构建 BST
Python
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root
def search(root, key):
if root is None or root.key == key:
return root
if key < root.key:
return search(root.left, key)
return search(root.right, key)
root = None
for k in [8, 3, 10, 1, 6, 14]:
root = insert(root, k)
print(search(root, 6) is not None) # True
深入了解
退化成棍子的问题。按顺序把 1, 2, 3, 4, 5, 6 插入到普通 BST。每个新数字都比树里已有的所有节点大，所以总是向右。你的"树"实际上就是一根长棍子 —— 一个伪装成树的链表。查找 6 要 6 跳，不是 log₂(6) ≈ 3 跳。BST 没有让你失望；你给了它对抗性输入。这正是自平衡变种存在的动机。
通过旋转自平衡。AVL 树（1962 年，第一个自平衡 BST）和红黑树（1972 年，平衡稍松但维护成本更低）在每次插入后检测不平衡，用旋转修复：旋转是局部重新排列父子节点而不破坏 BST 规则。旋转是 O(1)，一次插入最多需要几次。结果：无论你按什么顺序插入，树高都保持在 O(log n)。大多数语言标准库的"有序映射"或"树映射"类型底层就是红黑树。
BST 对比哈希表。什么时候选 BST 而不是哈希表？三种情况。(1) 需要有序遍历时 —— BST 让你按排序顺序走遍所有键；哈希表做不到。(2) 需要范围查询时（"给我 100 到 200 之间所有的键"）—— BST 容易，哈希表难。(3) 需要可预测性能时 —— 哈希表平均 O(1) 但最坏 O(n)；平衡 BST 每次都是 O(log n)。数据库索引用 B 树（宽分支因子的 BST 近亲）正是因为它们需要 SQL ORDER BY 的有序遍历和 SQL BETWEEN 的范围查询。
适用场景
- 任何需要快速查找加有序遍历的地方。哈希表能查找但没顺序。
- 数据库索引用 B 树（宽分支的 BST 近亲）。文件系统、时间序列分桶、内存范围查询 —— 都靠树结构。
4.4 Union-Find (disjoint set) · 4.4 并查集
🎬 中文白板讲解 · Chinese whiteboard explainer (~2 min)
Idea
Union-Find tracks groups and answers two questions: find(x) says "what group is x in?" and union(x, y) says "merge x's group with y's group". Useful whenever you're tracking connections that grow over time. With two optimizations (path compression and union-by-rank) every operation is essentially O(1) in practice.
The picture — five people joining and merging groups
Python
class UnionFind:
def __init__(self, n):
self.parent = list(range(n)) # each element is its own root
self.rank = [0] * n # tree height upper bound
def find(self, x):
# path compression: flatten the tree on every find
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False # already connected
# union by rank: attach the shorter tree under the taller
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
return True
uf = UnionFind(5)
uf.union(0, 1); uf.union(2, 3); uf.union(1, 2)
print(uf.find(0) == uf.find(3)) # True — 0,1,2,3 all connected
print(uf.find(4) == uf.find(0)) # False
Going deeper
Why the optimizations matter so much. Without path compression and union-by-rank, find can degrade to O(n) — imagine 1,000 union calls that build a long chain like 0 → 1 → 2 → ... → 999. find(999) would walk all 1,000 nodes. Union-by-rank alone keeps the worst-case tree depth at O(log n). Path compression alone is almost as good. The combination — both at once — is what produces the famous nearly-constant α(n) bound. The two optimizations together cost almost nothing in code complexity and turn a slow structure into one of the fastest data structures in computer science.
What α(n) actually means. The α in the running time is the inverse of the Ackermann function — a function so mind-bendingly fast-growing that even Ackermann(4, 2) is a number with more digits than there are atoms in the universe. So its inverse grows mind-bendingly slowly: α(n) ≤ 4 for any n you could possibly store in any computer ever built. In practice, treat union and find as constant-time. The technical bound is α(n), but for any realistic input it's just "very fast".
Why it took decades to prove. The data structure was simple to implement but hard to analyze. Robert Tarjan finally proved the α(n) bound in 1975, and it's remained one of the prettier results in algorithm analysis ever since — partly because the bound is so unintuitive (an inverse Ackermann shouldn't show up in something this practical) and partly because the proof techniques opened the door to a whole subfield of "amortized analysis" that we use today to analyze hash table resizing, splay trees, and more.
When to use
- Kruskal's algorithm for minimum spanning trees — "would adding this edge create a cycle?" is just
find(a) == find(b). - Connected components in a graph — friend-circles, reachability in a maze, percolation problems.
核心想法
并查集（Union-Find）跟踪一堆分组，回答两个问题：find(x) 告诉你 x 在哪一组；union(x, y) 把 x 的组和 y 的组合并。任何"随时间增长的连通关系"场景都会用到它。加上路径压缩和按秩合并两个优化，每个操作在实践中基本就是 O(1)。
图解 —— 5 个人加入并合并组
Python
class UnionFind:
def __init__(self, n):
self.parent = list(range(n)) # 一开始每个元素都是自己的根
self.rank = [0] * n # 树高的上界
def find(self, x):
# 路径压缩：每次 find 都把路径上的节点直接连到根
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False # 已经在同一组
# 按秩合并：把矮树接到高树下
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
return True
uf = UnionFind(5)
uf.union(0, 1); uf.union(2, 3); uf.union(1, 2)
print(uf.find(0) == uf.find(3)) # True —— 0,1,2,3 都连通
print(uf.find(4) == uf.find(0)) # False
深入了解
为什么这两个优化这么重要。没有路径压缩，find 在长链上可能退化到 O(n) —— 想象 1000 次 union 构造出长链 0 → 1 → 2 → ... → 999。find(999) 会走完所有 1000 个节点。只用按秩合并能把最坏树深限制在 O(log n)。只用路径压缩几乎一样好。两者一起 —— 才得到著名的近乎常数 α(n) 界。两个优化加起来在代码上几乎不增加复杂度，却把一个慢结构变成了计算机科学里最快的数据结构之一。
α(n) 到底是什么意思。运行时间里的 α 是 Ackermann 函数的逆。Ackermann 函数增长得令人发指地快 —— 即便 Ackermann(4, 2) 也是一个数字位数多于宇宙中原子数的数。所以它的逆增长得令人发指地慢：α(n) ≤ 4 对你能在任何计算机上存储的任何 n 都成立。实际上，把 union 和 find 当成常数时间。理论界是 α(n)，对任何实际输入就是"非常快"。
为什么花了几十年才证明出来。这个数据结构实现起来简单，但分析起来难。Robert Tarjan 在 1975 年终于证明了 α(n) 界，至今它仍是算法分析里最漂亮的结果之一 —— 部分原因是这个界非常反直觉（逆 Ackermann 不该出现在这么实用的东西里），部分原因是证明技术开启了一整个"摊还分析"子领域，我们今天用它分析哈希表扩容、伸展树等等。
适用场景
- Kruskal 算法构造最小生成树 —— "加入这条边会不会形成环？"就是
find(a) == find(b)。 - 图的连通分量 —— 朋友圈、迷宫连通性、渗流问题。
5. Graph algorithms — finding paths · 5. 图算法 —— 寻找路径
A graph is a bunch of dots (nodes) connected by lines (edges). A social network is a graph: people are nodes, friendships are edges. The web is a graph: pages are nodes, links are edges. A road map is a weighted graph: intersections are nodes, road segments are edges with travel-time weights. Three pathfinding algorithms handle three increasingly real-world versions of "shortest path from A to B?".
5.1 Breadth-first search (BFS) · 5.1 广度优先搜索（BFS）
🎬 中文白板讲解 · Chinese whiteboard explainer (~2 min)
Idea
BFS explores a graph in layers, like ripples in a pond. Start at one node, visit every direct neighbour, then every neighbour-of-a-neighbour, then every neighbour-of-neighbour-of-neighbour. A queue (first-in, first-out — like a line at the bus stop) drives the order. On a graph where every edge counts the same, BFS finds the path with the fewest hops between two nodes.
The picture — finding a mango seller in your friend network
Python
from collections import deque
graph = {
"you": ["alice", "bob", "claire"],
"alice": ["dave"],
"bob": ["eve"],
"claire": ["frank"],
"dave": [], "eve": [], "frank": [],
}
def bfs(start, target):
queue = deque([start])
seen = {start}
while queue:
node = queue.popleft() # pull from FRONT — that's what makes it BFS
if node == target:
return True
for neighbour in graph[node]:
if neighbour not in seen:
seen.add(neighbour)
queue.append(neighbour)
return False
print(bfs("you", "frank")) # True
Going deeper
One algorithm, two flavours. The data structure literally dictates the search order. Swap the queue (FIFO) for a stack (LIFO — pile of plates, take from the top) and BFS becomes depth-first search (DFS): dive down one path before backtracking. The visit order is completely different — BFS explores all friends before any friend-of-friend; DFS sprints down one chain to its end before exploring siblings. Both are O(V + E), but they have different strengths.
BFS guarantees shortest paths. DFS doesn't. Because BFS explores layer by layer, the first time it reaches any node, it does so via the fewest possible hops. DFS will find some path but rarely the shortest one. If you need the shortest path on an unweighted graph, BFS is the only correct choice. (For weighted graphs, you need Dijkstra — next section.)
Memory tradeoff. BFS keeps the entire "frontier" of one layer in memory at once. On a wide graph that fans out a lot (millions of friends-of-friends), this can be expensive. DFS only keeps the current path on the call stack — much less memory on wide graphs, but it can fall into deep recursion on long chains. The choice between them is often "do I have a wide-but-shallow graph or a narrow-but-deep one?"
The "seen" set is non-negotiable. Without tracking visited nodes, BFS would loop forever on graphs with cycles. The set is what turns "visit every reachable node" into a finite computation. The set is also why BFS is O(V + E) and not infinite: every node is processed at most once.
queue.popleft() to queue.pop() — you've just turned BFS into DFS, and the order things get visited completely changes.
When to use
- Shortest path in an unweighted graph — fewest hops in a social network, fewest moves to win a puzzle.
- Web crawlers — explore links layer by layer to avoid getting stuck deep in one site.
- Any "find the closest match where all steps cost the same".
核心想法
BFS 按层探索图，像池塘里的涟漪。从一个起点出发，先访问每一个直接邻居，再访问邻居的邻居，再访问邻居的邻居的邻居。队列（先进先出 —— 像公交站排队的人）决定顺序。在每条边花费相同的图上，BFS 找到两个节点间跳数最少的路径。
图解 —— 在朋友网络里找芒果卖家
Python
from collections import deque
graph = { # 邻接表：名字 → 朋友列表
"you": ["alice", "bob", "claire"],
"alice": ["dave"],
"bob": ["eve"],
"claire": ["frank"],
"dave": [], "eve": [], "frank": [],
}
def bfs(start, target):
queue = deque([start]) # 起点入队
seen = {start} # 已入队的节点
while queue: # 只要还有节点要访问
node = queue.popleft() # 从**前面**取 —— 这就是 BFS
if node == target:
return True
for neighbour in graph[node]:
if neighbour not in seen:
seen.add(neighbour)
queue.append(neighbour) # 加到**后面**
return False
print(bfs("you", "frank")) # True
深入了解
一个算法，两种风味。数据结构直接决定搜索顺序。把队列（FIFO）换成栈（LIFO —— 一摞盘子，从顶上拿），BFS 就变成了深度优先搜索（DFS）：一条路走到底再回溯。访问顺序完全不一样 —— BFS 先访问所有朋友再访问朋友的朋友；DFS 顺着一条链冲到底再回去查兄弟。两者都是 O(V + E)，但各有所长。
BFS 保证最短路径，DFS 不保证。因为 BFS 一层一层探索，它第一次到达任何节点时走的都是边数最少的路径。DFS 会找到某条路径，但很少是最短的。在无权图上需要最短路径时，BFS 是唯一正确选择。（带权图就要用迪杰斯特拉 —— 下一节。）
内存权衡。BFS 把"边界"整层都放在内存里。在很宽的图（几百万个朋友的朋友）上这开销很大。DFS 只在调用栈上保留当前路径 —— 在宽图上省得多，但在长链上可能陷入很深的递归。两者之间的选择常常是"我有宽而浅的图，还是窄而深的图？"
"seen" 集合不可省。不跟踪已访问节点的话，BFS 在带环的图上会永远循环。这个集合把"访问每个可达节点"变成有限计算。它也是 BFS 之所以是 O(V + E) 而非无穷的原因：每个节点最多处理一次。
queue.popleft() 改成 queue.pop() —— 你刚把 BFS 变成了 DFS，访问顺序完全变了。
适用场景
- 无权图上的最短路径 —— 社交网络里最少跳数、解谜题的最少步数。
- 网页爬虫 —— 一层一层探索链接，避免陷在一个站点的深层。
- 任何"每一步花费相同时找最近匹配"。
5.2 Dijkstra's algorithm · 5.2 迪杰斯特拉算法
🎬 中文白板讲解 · Chinese whiteboard explainer (~2 min)
Idea
When edges have weights (a road has a length, a flight has a price), BFS no longer gives the cheapest path. Dijkstra fixes this by replacing the BFS queue with a priority queue ordered by total cost so far. At each step, expand the unvisited node with the smallest known distance, then "relax" each neighbour: if going through this node makes the neighbour cheaper, update it. Greedy and provably correct — but only with non-negative weights.
The picture — cheapest path from Start to End
Python
import heapq
def dijkstra(graph, source):
distances = {node: float("inf") for node in graph}
distances[source] = 0
pq = [(0, source)] # (distance, node)
while pq:
d, u = heapq.heappop(pq)
if d > distances[u]:
continue # stale entry — skip
for v, weight in graph[u].items():
alt = d + weight
if alt < distances[v]:
distances[v] = alt
heapq.heappush(pq, (alt, v))
return distances
graph = {
"start": {"a": 6, "b": 2},
"a": {"end": 1},
"b": {"a": 3, "end": 5},
"end": {},
}
print(dijkstra(graph, "start"))
# {'start': 0, 'a': 5, 'b': 2, 'end': 6}
Going deeper
Why greedy actually works here. The proof is short and worth understanding. Suppose Dijkstra finalizes node u with distance d, but secretly there's a cheaper path through some other node v. That cheaper path has to reach v first — and at that point, v's distance in the priority queue would be smaller than d. So we'd have popped v before u, not after. Contradiction. The greedy choice is always safe. This kind of "if there were a counter-example, we'd have caught it earlier" proof shows up all over greedy algorithms.
Why negative weights break it. The whole argument above assumes that once you finalize a node, no future path can be cheaper. A negative-weight edge violates that assumption: a path that initially looks expensive could later get cheaper by taking a negative edge, retroactively making a "finalized" node not actually optimal. Dijkstra would have already moved on and reported the wrong answer. For negative weights you need Bellman-Ford — slower at O(V·E), but it re-relaxes edges until everything settles, and it can detect impossible-to-resolve negative cycles.
The relaxation operation. Most of Dijkstra's work happens in one line: if alt < distances[v]: distances[v] = alt. This is called "relaxation": you have a tentative answer for v, and you check if going through your current node makes it better. The algorithm is essentially "repeatedly relax all edges in a smart order until everything's settled". Many graph algorithms can be described that way — the differences are in the order of relaxation and what gets remembered.
核心想法
当边有权重时（路有长度、航班有价钱），BFS 不再给出最便宜的路径。迪杰斯特拉用按总代价排序的优先队列替换 BFS 的队列。每一步取出距离已知最小的未访问节点，然后对它的每个邻居做"松弛"：如果走这里能让邻居更便宜，就更新。贪心、可证明正确 —— 但只对非负权重成立。
图解 —— 从 start 到 end 的最低代价路径
Python
import heapq
def dijkstra(graph, source):
distances = {node: float("inf") for node in graph}
distances[source] = 0
pq = [(0, source)] # (距离, 节点)
while pq:
d, u = heapq.heappop(pq)
if d > distances[u]:
continue # 过期项 —— 已找到更短，跳过
for v, weight in graph[u].items():
alt = d + weight
if alt < distances[v]:
distances[v] = alt
heapq.heappush(pq, (alt, v))
return distances
graph = {
"start": {"a": 6, "b": 2},
"a": {"end": 1},
"b": {"a": 3, "end": 5},
"end": {},
}
print(dijkstra(graph, "start"))
# {'start': 0, 'a': 5, 'b': 2, 'end': 6}
深入了解
为什么贪心在这里有效。证明很短，值得理解。假设迪杰斯特拉把节点 u 用距离 d 定下来，但暗地里有一条经过另一个节点 v 的更便宜路径。那条更便宜路径必须先到达 v —— 而那时优先队列里 v 的距离会小于 d。所以我们会先弹出 v，而不是后弹。矛盾。贪心选择始终安全。这种"如果有反例，我们早就发现了"的证明在贪心算法里随处可见。
为什么负权重会破坏它。上面的论证依赖一个关键事实：节点一旦从优先队列弹出，它的距离就不会再变短。这只在非负权重下成立。负边权违反了这个假设：一条最初看起来贵的路径之后可能因为走了一条负边而变便宜，反过来证明一个"已定"节点实际上不是最优。迪杰斯特拉早就走开报错答案了。对于负权要用 Bellman-Ford —— 慢一些（O(V·E)），但它反复松弛所有边直到稳定，还能检测不可解的负环。
松弛操作。迪杰斯特拉大部分工作都在一行里：if alt < distances[v]: distances[v] = alt。这叫"松弛"：你对 v 有一个临时答案，检查走当前节点能不能更短。整个算法本质上是"按聪明的顺序反复松弛所有边直到一切稳定"。许多图算法都可以这样描述 —— 差别在松弛的顺序和记录什么。
5.3 A* search · 5.3 A* 搜索
🎬 中文白板讲解 · Chinese whiteboard explainer (~2 min)
Idea
A* (pronounced "A-star") improves on Dijkstra by adding a heuristic — a quick estimate of how far each node is from the goal. Where Dijkstra picks the next node based on cost-so-far, A* picks based on cost-so-far + estimated-remaining. That estimate biases the search toward the goal, so A* visits far fewer nodes than Dijkstra. On a 2D grid, the "Manhattan distance" (how many up/down/left/right moves you'd need with no walls) is a classic heuristic.
The picture — pathfinding on a 3×3 grid with a wall
Python
import heapq
def manhattan(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def a_star(start, goal, walkable):
open_set = [(manhattan(start, goal), 0, start)] # (f, g, node)
best_g = {start: 0}
while open_set:
_, g, current = heapq.heappop(open_set)
if current == goal:
return g
for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
nxt = (current[0] + dx, current[1] + dy)
if nxt not in walkable:
continue
tentative = g + 1
if tentative < best_g.get(nxt, float("inf")):
best_g[nxt] = tentative
f = tentative + manhattan(nxt, goal)
heapq.heappush(open_set, (f, tentative, nxt))
return None # no path
# 3x3 grid with a wall at (0, 1)
walkable = {(0,0), (1,0), (1,1), (1,2), (0,2)}
print(a_star((0,0), (0,2), walkable)) # 4
Going deeper
The heuristic's two rules. For A* to be guaranteed to find the cheapest path, the heuristic h(n) must be admissible: it must never overestimate the true remaining cost to the goal. Underestimating is fine (the worst that happens is A* explores more than it had to). Overestimating is fatal — A* might decide a node is "too expensive" and skip the actual best path. Straight-line distance is always admissible for any movement that respects the triangle inequality (you can never get there faster than a straight line); Manhattan distance is admissible on grid movement that allows only horizontal and vertical steps.
A* as a generalization. A* contains both Dijkstra and BFS as special cases. If you set the heuristic to h(n) = 0 everywhere — "I have no estimate, every node looks equally far from the goal" — A* becomes Dijkstra. If you also make every edge cost 1, A* becomes BFS. So A* isn't really a different algorithm from Dijkstra; it's Dijkstra plus extra information about where the goal is. The better your heuristic, the closer A*'s behaviour gets to "draw a straight line from start to goal" — vastly faster than Dijkstra's "expand in every direction equally" behaviour.
The speed-quality tradeoff. "Weighted A*" multiplies the heuristic by a constant greater than 1, deliberately overestimating. The result is no longer guaranteed to be the shortest path, but it can be many times faster. Video games often use weighted A* — players notice "the path is bad" only if the NPC walks straight into a wall, not if it takes a path that's 5% longer. Trading a tiny bit of optimality for a lot of speed is often worth it in real-time systems.
When to use
- Game AI — NPCs finding paths around obstacles on a tile grid.
- Robot motion planning — find a route through a known floor map.
- Any search where you have a cheap, never-too-high estimate of remaining cost.
核心想法
A*（读作"A 星")在迪杰斯特拉的基础上加了一个启发函数 —— 一个对每个节点到目标剩余代价的快速估计。迪杰斯特拉按 g(n)（已走代价）选下一个节点，A* 按 f(n) = g(n) + h(n)（已走 + 估计剩余）选。这个估计让搜索倾向目标，所以 A* 访问的节点远少于迪杰斯特拉。在 2D 网格上，"曼哈顿距离"（没有墙时所需的上下左右步数）是经典启发函数。
图解 —— 3×3 网格、中间有墙的寻路
Python
import heapq
def manhattan(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def a_star(start, goal, walkable):
open_set = [(manhattan(start, goal), 0, start)] # (f, g, 节点)
best_g = {start: 0}
while open_set:
_, g, current = heapq.heappop(open_set)
if current == goal:
return g
for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
nxt = (current[0] + dx, current[1] + dy)
if nxt not in walkable:
continue
tentative = g + 1
if tentative < best_g.get(nxt, float("inf")):
best_g[nxt] = tentative
f = tentative + manhattan(nxt, goal)
heapq.heappush(open_set, (f, tentative, nxt))
return None # 无路径
# 3×3 网格，(0, 1) 有墙
walkable = {(0,0), (1,0), (1,1), (1,2), (0,2)}
print("Path cost:", a_star((0,0), (0,2), walkable)) # 4
深入了解
启发函数的两条规则。A* 要保证找到最低代价路径，启发函数 h(n) 必须可允许：永远不能高估到目标的真实剩余代价。低估没关系（最坏只是 A* 多探索一些）。高估是致命的 —— A* 可能认定某个节点"太贵"而跳过实际最优路径。直线距离对任何满足三角不等式的运动总是可允许的；曼哈顿距离对只允许上下左右移动的网格是可允许的。
A* 作为推广。A* 把迪杰斯特拉和 BFS 都包含为特例。如果你把启发函数设为对所有节点 h(n) = 0（"我没有任何估计，每个节点离目标都一样远"），A* 就变成了迪杰斯特拉。如果再把每条边代价设为 1，A* 就变成了 BFS。所以 A* 实际上和迪杰斯特拉不是不同的算法；它是迪杰斯特拉加上对"目标在哪儿"的额外信息。启发函数越好，A* 的行为越接近"从起点向目标画一条直线" —— 比迪杰斯特拉"向各个方向均匀扩展"快得多。
速度-质量权衡。"加权 A*"把启发函数乘以一个大于 1 的常数，故意高估。结果不再保证是最短路径，但可以快几倍。游戏经常用加权 A* —— 玩家只有在 NPC 撞墙时才注意到"这条路糟糕"，而不是路径长了 5%。在实时系统里用一点点最优性换很多速度通常值得。
适用场景
- 游戏 AI —— NPC 在格子地图上绕开障碍找路。
- 机器人运动规划 —— 在已知楼层地图上找路线。
- 任何有"便宜、永不过高的剩余代价估计"的搜索。
6. Algorithm paradigms — greedy and dynamic · 6. 算法范式 —— 贪心与动态规划
Beyond specific algorithms there are paradigms — general strategies you adapt to new problems. Two come up over and over: greedy choice and dynamic programming.
6.1 Greedy algorithms · 6.1 贪心算法
🎬 中文白板讲解 · Chinese whiteboard explainer (~2 min)
Idea
A greedy algorithm grabs the locally best option at every step and never looks back. Sometimes the local choices add up to the globally best answer (Dijkstra is greedy and provably right on non-negative weights). Often they don't — but greedy answers are so close to optimal, and so fast to compute, that they're the right tool anyway.
The classic example is set cover: pick the fewest radio stations to cover every state. Finding the truly optimal answer takes exponential time (this problem is "NP-complete" — practically unsolvable for large inputs). Greedy gives an excellent approximation in seconds.
The picture — covering 8 states with a few stations
Python
states_needed = {"mt", "wa", "or", "id", "nv", "ut", "ca", "az"}
stations = {
"kone": {"id", "nv", "ut"},
"ktwo": {"wa", "id", "mt"},
"kthree": {"or", "nv", "ca"},
"kfour": {"nv", "ut"},
"kfive": {"ca", "az"},
}
chosen = set()
while states_needed:
best_station = None
best_covered = set()
for station, covers in stations.items():
covered = states_needed & covers # overlap = set intersection
if len(covered) > len(best_covered):
best_station = station
best_covered = covered
states_needed -= best_covered # remove the states we just covered
chosen.add(best_station)
print(chosen) # {'kone', 'ktwo', 'kthree', 'kfive'}
Going deeper
When greedy fails — the coin-change example. Suppose you need to make 6 cents using coins of denominations 1¢, 3¢, and 4¢. Greedy says: "take the biggest coin that fits". So you take 4, then 1, then 1 — three coins. But the optimal answer is two coins: 3 + 3. Greedy got the wrong answer because the locally best choice (take the 4) blocked the globally best choice (use two 3s). With "normal" coin systems like US currency, greedy happens to work; with arbitrary denominations, it can fail by a lot.
The "greedy choice property". A problem is solvable by greedy if and only if it has the greedy choice property: at every step, there exists some optimal solution that includes the locally best choice. Proving this for a specific problem is the hard part — and there's no general technique, you have to think carefully about each new problem. For Dijkstra: the proof in the previous section. For Kruskal's MST: a similar contradiction argument. For set cover: it doesn't hold exactly, but you can prove that greedy stays within a factor of ln(n) of optimal — and remarkably, no polynomial-time algorithm can do better. That's the best you can hope for unless P = NP.
Why greedy is the workhorse anyway. Even when greedy isn't provably optimal, it's often "good enough" while being dramatically faster than algorithms that find true optima. For NP-hard problems (set cover, traveling salesperson, knapsack), the difference between "polynomial-time greedy approximation" and "exact exponential algorithm" can be the difference between an answer in milliseconds and an answer never. In practice, greedy is one of the first things engineers reach for when faced with a new optimization problem.
When to use
- Approximating hard problems — when an exact answer would take centuries, a good-enough greedy answer in milliseconds beats no answer.
- Scheduling — interval scheduling, Huffman codes, activity selection are all greedy.
- Minimum spanning trees (Kruskal, Prim) — greedy and provably optimal.
核心想法
贪心算法每一步都拿当下最好的选项，从不回头。有时局部选择加起来就是全局最优答案（迪杰斯特拉是贪心的，对非负权重可证最优）。多数时候并非如此 —— 但贪心答案如此接近最优、又这么快，往往就是该用的工具。
经典例子是集合覆盖：用最少的广播电台覆盖每个州。找真正最优答案需要指数时间（这个问题是 "NP 完全的" —— 对大输入实际上不可解）。贪心在秒级内给出极佳的近似。
图解 —— 用几个电台覆盖 8 个州
Python
states_needed = {"mt", "wa", "or", "id", "nv", "ut", "ca", "az"}
stations = {
"kone": {"id", "nv", "ut"},
"ktwo": {"wa", "id", "mt"},
"kthree": {"or", "nv", "ca"},
"kfour": {"nv", "ut"},
"kfive": {"ca", "az"},
}
chosen = set()
while states_needed:
best_station = None
best_covered = set()
for station, covers in stations.items():
covered = states_needed & covers # 重叠（集合交集）
if len(covered) > len(best_covered):
best_station = station
best_covered = covered
states_needed -= best_covered # 删掉刚覆盖的州
chosen.add(best_station)
print(chosen) # {'kone', 'ktwo', 'kthree', 'kfive'}
深入了解
贪心失败的时候 —— 找零钱的例子。假设你要用 1 分、3 分、4 分硬币凑 6 分。贪心说："拿能装下的最大硬币"。于是你拿 4，再拿 1，再拿 1 —— 3 枚。但最优答案是 2 枚：3 + 3。贪心给了错答案，因为局部最优选择（拿 4）阻挡了全局最优选择（用两个 3）。美元这样的"正常"币制贪心刚好成立；任意币制可能差很多。
"贪心选择性质"。当且仅当问题具有贪心选择性质时，贪心算法能解决它：每一步都存在某个最优解包含局部最优选择。对特定问题证明这一点是难点 —— 没有通用技术，每个新问题都要仔细思考。迪杰斯特拉：上一节的证明。Kruskal 最小生成树：类似的反证。集合覆盖：精确不成立，但你可以证明贪心保持在最优的 ln(n) 倍内 —— 而且令人惊讶地，没有多项式时间算法能做得更好。这是除非 P = NP 否则你能期望的最好结果。
为什么贪心仍是主力。即使贪心不可证最优，它通常"够好"，而且比寻找真正最优解的算法快得多。对 NP-hard 问题（集合覆盖、旅行商、背包），"多项式时间贪心近似"和"指数级精确算法"的差别可能是"毫秒得答案"和"永远没答案"。实践中，工程师面对新优化问题时贪心是最先尝试的工具之一。
适用场景
- 近似困难问题 —— 精确答案要花几个世纪时，毫秒内的够用贪心答案胜过没有答案。
- 调度 —— 区间调度、Huffman 编码、活动选择都是贪心的。
- 最小生成树（Kruskal、Prim） —— 既贪心又可证最优。
6.2 Dynamic programming · 6.2 动态规划
🎬 中文白板讲解 · Chinese whiteboard explainer (~2 min)
Idea
Dynamic programming (DP) applies when a problem has overlapping subproblems — the same smaller question pops up again and again. The fix: remember the answer the first time you compute it, then look it up forever after. That trick is called memoization ("memo" like a sticky note).
The classic example is Fibonacci. Plain recursive Fibonacci is appallingly slow (O(2ⁿ)) because it recomputes the same numbers an exponential number of times. Memoized Fibonacci is O(n) — instant.
The picture — why memoization is magic
Python
def fib(n, memo=None):
if memo is None:
memo = {}
if n < 2:
return n
if n in memo:
return memo[n] # already computed — instant!
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
print(fib(50)) # 12586269025 — instant, vs. minutes without memo
Going deeper
Top-down vs bottom-up. Two ways to implement DP. The version above is top-down (also called memoization): write the natural recursive solution and add a cache. Intuitive but uses the call stack. The alternative is bottom-up (also called tabulation): figure out the base cases, then iteratively fill in a table from smallest subproblem to largest. For Fibonacci, bottom-up would be a simple for loop filling table[i] = table[i-1] + table[i-2]. Bottom-up is usually more memory-efficient (no recursion) but harder to derive — you need to know exactly which subproblems you need.
The hard part is finding "state". Once you know what defines a subproblem — what variables you'd need to ask "given these inputs, what's the answer?" — DP writes itself. For Fibonacci, state is just n. For longest common subsequence, state is two indices (one into each string). For knapsack, state is "items considered so far + remaining capacity". Choosing the right state is 90% of solving a DP problem. The other 10% is the recurrence: how does a bigger state's answer depend on smaller states' answers?
DP shows up under other names. Many "famous" algorithms are DP in disguise. Bellman-Ford (shortest paths with negative weights) is DP. Floyd-Warshall (shortest paths between every pair of nodes) is DP. The CKY algorithm that parses sentences in linguistics is DP. The Viterbi algorithm that decodes hidden Markov models in speech recognition is DP. Edit distance — how Microsoft Word does spell-check suggestions — is DP. Once you recognize the pattern, you start seeing it everywhere.
@functools.cache and Python handles the memo for you. The recursion stays readable and you don't manage the dictionary yourself.
from functools import cache
@cache
def fib(n):
if n < 2: return n
return fib(n - 1) + fib(n - 2)
print(fib(100)) # 354224848179261915075 — instantWhen to use
- Longest common subsequence — diff tools, bioinformatics sequence alignment.
- Knapsack — "best value to fit in a fixed-size bag" comes up everywhere from logistics to ad bidding.
- Shortest paths inside Bellman-Ford and Floyd-Warshall graph algorithms.
- Any "minimum cost over a sequence of choices" problem where choices overlap.
核心想法
动态规划（DP）适用于具有重叠子问题的场景 —— 同样的小问题反复出现。解决办法：第一次算出来时记住答案，以后查表。这个技巧叫记忆化（"memo" 就像便签）。
经典例子是斐波那契。朴素递归斐波那契是 O(2ⁿ)，因为它把同样的数字以指数级次数重新计算。记忆化斐波那契是 O(n) —— 瞬间。
图解 —— 为什么记忆化是魔法
Python
def fib(n, memo=None):
if memo is None:
memo = {}
if n < 2:
return n
if n in memo:
return memo[n] # 算过了 —— 瞬间！
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
print(fib(50)) # 12586269025 —— 瞬间，朴素版要几分钟
深入了解
自顶向下 vs 自底向上。两种实现风格。上面是自顶向下（也叫记忆化）：写自然的递归解，加缓存。容易推导但用调用栈。另一种是自底向上（也叫制表）：先确定基础情况，再从最小子问题往大答案迭代填表。对斐波那契，自底向上就是一个简单的 for 循环填 table[i] = table[i-1] + table[i-2]。自底向上通常更省内存（没有递归），但更难推导 —— 你要确切知道需要哪些子问题。
难的是找"状态"。一旦你知道什么定义了一个子问题 —— 你需要问"给这些输入答案是什么？"时要的变量 —— DP 自己就写出来了。对斐波那契，状态就是 n。对最长公共子序列，状态是两个下标（每个串一个）。对背包，状态是"考虑过的物品 + 剩余容量"。选对状态是解 DP 问题 90% 的工作。其余 10% 是递推公式：大状态的答案如何依赖小状态的答案？
DP 常以其他名字出现。很多"著名"算法其实是伪装的 DP。Bellman-Ford（带负权的最短路径）是 DP。Floyd-Warshall（所有节点对之间的最短路径）是 DP。语言学中解析句子的 CKY 算法是 DP。语音识别中解码隐马尔可夫模型的 Viterbi 算法是 DP。编辑距离 —— Microsoft Word 拼写建议的原理 —— 是 DP。一旦认出这个模式，你到处都会看见它。
@functools.cache 装饰任何函数，Python 帮你做记忆化。递归保持可读，你不用管字典。
from functools import cache
@cache
def fib(n):
if n < 2: return n
return fib(n - 1) + fib(n - 2)
print(fib(100)) # 354224848179261915075 —— 瞬间适用场景
- 最长公共子序列 —— diff 工具、生物信息学序列比对。
- 背包 —— "固定容量装最大价值"在物流到广告竞价里到处出现。
- Bellman-Ford 和 Floyd-Warshall 图算法内部的最短路径。
- 任何选择重叠的"序列选择的最小代价"问题。
7. A first machine-learning algorithm — k-Nearest Neighbours · 7. 第一个机器学习算法 —— k-近邻
🎬 中文白板讲解 · Chinese whiteboard explainer (~2 min)
Idea
k-Nearest Neighbours (k-NN) is a classifier you can write in fifteen lines. To label a new point, find the k closest already-labelled points and let them vote. There's no training step — the algorithm just memorizes the training set and does all the work at prediction time. "Closest" needs a distance metric; Euclidean distance (the straight-line distance you learned in geometry) is the default.
Despite its simplicity, k-NN was the workhorse of recommender systems for years ("users who liked this also liked…") and still shows up as a baseline in many ML pipelines.
The picture — classifying a mystery fruit
Python (no scikit-learn needed)
import math
from collections import Counter
def knn_predict(train, new_point, k=3):
# train is a list of (features, label) pairs
distances = []
for features, label in train:
d = math.sqrt(sum((a - b) ** 2 for a, b in zip(features, new_point)))
distances.append((d, label))
distances.sort(key=lambda x: x[0]) # sort by distance
k_labels = [label for _, label in distances[:k]]
return Counter(k_labels).most_common(1)[0][0] # winning vote
# weight in grams, diameter in cm
train = [
((150, 8), "apple"),
((170, 9), "apple"),
((140, 7), "orange"),
((130, 6), "orange"),
]
print(knn_predict(train, (145, 7.5), k=3)) # "orange"
Going deeper
Feature scaling matters — a lot. Euclidean distance treats every feature as equally important. If one feature is "weight in grams" (ranging 100 to 1000) and another is "diameter in metres" (ranging 0.05 to 0.10), the weight differences will totally dominate the distance calculation — the diameter feature will essentially be ignored. Standard practice: normalize every feature to mean 0 and standard deviation 1 (called "z-score" or "standardization") before applying k-NN. Forgetting to scale is one of the most common bugs in real ML pipelines, and the error mode is silent — your model "works" but performs badly.
The curse of dimensionality. In low dimensions (2 or 3 features), "nearest neighbour" is intuitive — the closest point really does look most similar. In high dimensions (hundreds or thousands of features, like image embeddings), something weird happens: all points become roughly equidistant from each other. The very concept of "near" loses meaning. This is the curse of dimensionality, and it's why pure k-NN doesn't work for modern AI tasks where embeddings can have 768 or more dimensions. The fix is approximate nearest neighbour structures like FAISS or HNSW, which use clever tricks (often involving randomization) to find "approximately nearest" neighbours in time that's much less than O(n) per query.
Choosing k. The "k" in k-NN matters. With k=1, your prediction depends entirely on the single closest point — very flexible but very vulnerable to outliers and noise (a single weird labelled point ruins predictions in its neighbourhood). With k=100, predictions are smoothed out by the vote of 100 points — robust to noise but might miss subtle patterns. The right k depends on the dataset; common practice is to try several values and pick the one that performs best on a held-out validation set. This is the bias-variance tradeoff in a nutshell.
Lazy vs eager learning. k-NN is the canonical example of "lazy learning" — it does no work at training time. Compare to "eager learning" like neural networks, which spend hours training to extract a model, then predict in microseconds. Lazy learning is great when you rarely query but your data changes constantly. Eager learning wins when you query billions of times against a stable model.
k=3 to k=1. Now the prediction depends only on the single closest point. With k=1 the answer for our mystery fruit is whichever of A1 or O1 came first (they're tied at distance 5.02). Bigger k = smoother, more democratic vote. Smaller k = sharper, but more easily fooled by one weird point.
When to use
- Recommender systems — "users similar to this user also bought…".
- Baseline classifier when you don't know yet whether a fancier model is worth the effort.
- Image similarity — k-NN over feature embeddings (face recognition, near-duplicate detection).
核心想法
k-近邻（k-NN）是一个你用 15 行就能实现的分类器。给一个新点贴标签的方法：找到 k 个最近的已知标签点，让它们投票。没有训练阶段 —— 算法就是记住训练集，所有工作在预测时完成。"最近"需要一个距离度量；欧氏距离（你几何课学过的直线距离）是默认。
尽管简单，k-NN 多年来是推荐系统的主力（"喜欢这个的用户还喜欢……"），今天在许多 ML 流水线里仍然作为基线出现。
图解 —— 分类一个神秘水果
Python（不需要 scikit-learn）
import math
from collections import Counter
def knn_predict(train, new_point, k=3):
# train 是 (特征, 标签) 对的列表
distances = []
for features, label in train:
d = math.sqrt(sum((a - b) ** 2 for a, b in zip(features, new_point)))
distances.append((d, label))
distances.sort(key=lambda x: x[0]) # 按距离（第一个元素）排序
k_labels = [label for _, label in distances[:k]] # 最近 k 个的标签
return Counter(k_labels).most_common(1)[0][0] # 多数投票
# 特征：(重量克, 直径厘米)
train = [
((150, 8), "apple"),
((170, 9), "apple"),
((140, 7), "orange"),
((130, 6), "orange"),
]
print(knn_predict(train, (145, 7.5), k=3)) # "orange"
深入了解
特征缩放非常重要。欧氏距离把每个特征同等看待。如果一个特征是"重量（克）"（范围 100 到 1000），另一个是"直径（米）"（范围 0.05 到 0.10），重量的差距会完全主导距离计算 —— 直径特征几乎被忽略。标准做法：在用 k-NN 之前把每个特征归一化到均值 0、标准差 1（叫"z 分数"或"标准化"）。忘记缩放是真实 ML 流水线里最常见的 bug 之一，错误模式还是静默的 —— 你的模型"能跑"但表现不佳。
维度灾难。在低维（2 或 3 个特征）下，"最近邻"很直观 —— 最近的点确实看起来最相似。在高维（几百或几千个特征，比如图像嵌入）下，奇怪的事情发生了：所有点之间的距离变得大致相等。"近"这个概念失去意义。这就是维度灾难，也是纯 k-NN 不适用于现代 AI 任务的原因 —— 现代嵌入可能有 768 或更多维度。解法是 FAISS 或 HNSW 这样的近似最近邻结构，它们用聪明的技巧（常涉及随机化）以远小于 O(n) 的每查询时间找到"近似最近"的邻居。
选 k。k-NN 里的"k"很重要。k=1 时你的预测完全取决于最近的那一个点 —— 非常灵活但对异常值和噪声极敏感（一个奇怪的标签点会毁掉它周围的预测）。k=100 时预测被 100 个点的投票平滑 —— 抗噪但可能错过细微模式。正确的 k 取决于数据集；常见做法是试几个值，选在留出验证集上表现最好的。这就是偏差-方差权衡的精髓。
懒惰 vs 主动学习。k-NN 是"懒惰学习"的经典例子 —— 训练时不做任何工作。对比"主动学习"如神经网络，训练要几小时但预测在微秒内。懒惰学习适合查询稀少但数据不断变化的场景。主动学习在你要对稳定模型查询数十亿次时胜出。
适用场景
- 推荐系统 —— "和这个用户相似的用户还买了……"
- 基线分类器 —— 当你还不知道更复杂的模型值不值得时。
- 图像相似度 —— 在特征嵌入上做 k-NN（人脸识别、近似重复检测）。
8. Where to go next · 8. 下一步
This page covers sixteen algorithms. A handful more come up often enough to deserve a name:
- Bellman-Ford — Dijkstra's slower, weight-tolerant cousin (handles negative edges, detects negative cycles).
- Floyd-Warshall — finds shortest paths between every pair of nodes in
O(V³); just three nested loops. - Topological sort — order tasks in a DAG so dependencies come first (build systems, course prerequisites).
- Tries — prefix trees for autocomplete, IP routing tables, spell-checkers.
- Bloom filters — probabilistic "have I seen this?" in tiny space. Used in Chrome's malicious-URL check and many databases.
- HyperLogLog — count distinct items in a stream with kilobytes of memory regardless of stream size.
- MapReduce — the paradigm behind every distributed batch processor; conceptually "map every record, then reduce by key".
- SHA / cryptographic hashing — what hash functions look like when you optimize them for security rather than for hash-table buckets.
The matching Jupyter notebooks linked at the top of this page (when they're added) will let you load a real dataset, run any of the sixteen algorithms above against it, and watch what happens. Until then, the snippets here are intentionally short enough to paste straight into a Python shell.
Further reading
- Grokking Algorithms by Aditya Bhargava — the friendliest introduction to chapters 1–10 above. Highly recommended.
- grokking_algorithms on GitHub — the book's official Python source, free to clone and play with.
- Big-O Cheat Sheet — a single page with the complexity of every algorithm and data structure on this page.
- VisuAlgo — gorgeous interactive animations of nearly every algorithm here. Watch sorting, BFS, Dijkstra play out in real time.
- Wikipedia's list of algorithms — the bigger catalogue when something on this page sparks a follow-up question.
本页讲了 16 个算法。还有几个出现得足够频繁、值得记住名字：
- Bellman-Ford —— 迪杰斯特拉更慢、容忍权重的近亲（处理负边，能检测负环）。
- Floyd-Warshall ——
O(V³)找出所有节点对之间的最短路径；就是三层嵌套循环。 - 拓扑排序 —— 给 DAG 里的任务排序，让依赖先于被依赖（构建系统、课程先修关系）。
- 字典树（Trie） —— 前缀树，用于自动补全、IP 路由表、拼写检查。
- 布隆过滤器 —— 用极少内存做概率性的"我见过它吗？"，假阳率可调。Chrome 的恶意 URL 检测和许多数据库都在用。
- HyperLogLog —— 用 KB 级内存统计数据流里不重复项的数量，与流的大小无关。
- MapReduce —— 每个分布式批处理引擎背后的范式；概念上就是"对每条记录 map，再按键 reduce"。
- SHA / 密码学哈希 —— 当哈希函数为安全性而不是为哈希表桶位优化时长什么样。
页顶链接的对应 Jupyter 笔记本（加进来之后）会让你加载真实数据集、把上面任意一个算法跑在它上面看效果。在此之前，这里的代码片段都短到可以直接粘进 Python 终端。
延伸阅读
- Grokking Algorithms（算法图解）by Aditya Bhargava —— 1-10 章最平易近人的入门书。强烈推荐。
- grokking_algorithms on GitHub —— 书附带的官方 Python 源码，可自由克隆把玩。
- Big-O Cheat Sheet —— 一页纸上本页每个算法和数据结构的复杂度。
- VisuAlgo —— 几乎所有本页算法的精美交互动画。实时看排序、BFS、迪杰斯特拉运行。
- Wikipedia 的算法列表 —— 本页某处激发你的好奇时的更大目录。