什么是计算机科学与算法

欢迎来到《从零开始学算法》。在正式动手之前，我想先和你聊清楚三件事：计算机科学到底是什么，算法为什么是它的核心，以及这门课打算怎么带你从零走到能独立分析陌生问题的地步。

1.什么是计算机科学，什么是算法

很多人对计算机科学有个误会，觉得它就是"写代码的学问"。代码只是手段，计算机科学真正研究的是计算本身——什么样的信息处理任务是可以被机械地完成的，完成它需要多少步骤、占多少空间，以及一个任务到底"难"在哪里。

把这个落脚点再缩小一点，就到了算法。算法是什么？说穿了，就是解决某类问题的一串明确的、有限的操作步骤。你想想，做菜有菜谱——第一步切菜、第二步热油、第三步翻炒——菜谱就是一道"做这道菜"的算法。只不过计算机的算法，步骤要精确到机器能一丝不差地照着执行，连"少许""适量"这种模糊话都不能有。

那么，同样一个排序问题，为什么会有插入排序、归并排序、堆排序这么多种算法？因为它们各有各的脾性：有的在数据几乎有序时飞快、有的在任何情况下都稳、有的特别省内存、有的天生适合并行。学算法，学的不是背下那一串步骤，而是学会在一堆候选方案里，根据"这个问题长什么样、数据量有多大、我更在乎时间还是内存"，挑出最合适的那个。 这就引出了衡量算法好坏的那把尺子——复杂度，第一卷 1.8 节会专门讲它。

2.学习算法有什么用

我猜你心里多少有个疑问：现在都 2026 年了，排序调用一个 sort() 函数不就完了，最短路、网络流也都有现成库，何必从头学一遍？这个问题问得实在，值得认真回答。

第一，算法是面试和深造的硬通货。 不管你去大厂、考研还是出国，算法都是绕不开的考查项。但它值得学，不只是因为"要考"。面试官真正想看的，是你面对一个没见过的题目时，能不能把它拆解、找到结构、设计出正确且高效的解法——这个能力，恰恰是算法训练反复打磨的东西。

第二，算法训练改变你思考问题的方式。 学到后面你会发现，贪心、动态规划、分治、归约、对偶，这些与其说是"算法"，不如说是思考问题的几种基本姿态。一个复杂问题摆在面前，你会下意识地问：它能不能拆成更小的同类子问题？它有没有最优子结构？它能不能归约成我已经会的问题？这种结构化思维，写代码、做系统设计、甚至看论文都用得上。

第三，理解算法让你看得懂现代系统的底层。 你用的搜索引擎（PageRank、倒排索引）、数据库（B树、一致性哈希）、压缩工具（LZ77）、甚至区块链（RSA、哈希），底下全是算法。不学算法，这些系统对你就是个黑箱；学了，你就知道它为什么这样设计、瓶颈在哪、能怎么改进。第十卷会专门把这些落地展示出来。

3.这门课的一条主线

和深度学习那门课一样，我给这门课也设了一条主线。算法学习最容易掉进的坑，是把算法当成知识点来背——今天背个快排，明天背个 Dijkstra，后天背个背包，彼此孤立，遇到新题就抓瞎。

这门课从头到尾咬住一条主线：

先会实现，再会分析，然后会设计，最后会迁移。

什么意思？碰到任何一个算法，我们要依次回答四个问题：

1. 它是什么、怎么实现？（实现）
2. 它为什么对、为什么这么快？（分析：正确性证明 + 复杂度分析）
3. 它是怎么被想出来的、背后是什么设计思想？（设计：分治/贪心/动态规划/归约/对偶……）
4. 这套思想能迁移到别的问题上吗？（迁移）

越往后，越是从"记住一个算法"走向"掌握一种设计工具"。整门课十一卷，就是按这条主线铺开的。

4.十一卷分别讲什么

我把全部十一卷挨个说清楚，每卷在主线里扮演什么角色。

第一卷·算法基础与分析语言（1.1–1.9）。这是地基。从最朴素的插入排序、归并排序入手，让你先建立起"算法长什么样、怎么分析它的快慢"的直觉。再到二分查找、堆排序、哈希、广度/深度优先搜索这些最基础的工具。最后两节专门讲渐近复杂度分析和循环不变量——前者是衡量快慢的语言（大 O 记号那一套），后者是证明算法正确的标准武器。这两节是后面反复要用的"分析语言"，务必吃透。

第二卷·分治与计算加速（2.1–2.7）。这一卷的核心，是让你发现一件很震撼的事：排序、选择、几何、矩阵运算、多项式乘法，这些看起来八竿子打不着的问题，居然共享同一种设计结构——分治。 快速排序、线性时间选择、最近点对、凸包、Strassen 矩阵乘法、快速傅里叶变换，统统是"把大问题切成小问题、分别解决、再合并"的套路。学到 FFT 你会特别有感觉：原来多项式乘法可以从 $O(n^2)$ 降到 $O(n\log n)$，靠的就是分治。

第三卷·最优化问题的两条主线（3.1–3.9）。区间调度、Huffman 编码、Kruskal、Dijkstra、背包、最长公共子序列、旅行商……这一卷用同一批最优化问题，建立起贪心算法和动态规划之间的边界。什么时候贪心就够了（能用交换论证证明），什么时候非得动态规划（有最优子结构但贪心会出错），你会分得清清楚楚。

第四卷·算法证明与性能分析（4.1–4.9）。前三卷你一直在用算法，这一卷开始系统回答三个为什么：为什么算法一定正确、为什么算法具有给定的复杂度、为什么某些问题无法设计出更快的同类算法。递归树、主定理、摊还分析、概率分析、交换论证、剪切粘贴、势能法、对手论证、决策树下界——这些都是"把直觉变成严格证明"的工具。这一卷是算法训练从"会用"到"懂"的分水岭。

第五卷·图算法与组合优化（5.1–5.8）。拓扑排序、Bellman-Ford、Floyd-Warshall、最大流最小割、二分图匹配、最小费用流、稳定匹配、PageRank。这一卷不继续罗列大量图算法，而是重点讲五个核心概念：松弛、增广、割、匹配、图模型转换。你会发现，最短路、最大流、匹配，本质上都在反复用这几个操作。

第六卷·摊还、随机化与数据结构（6.1–6.8）。动态数组扩容、并查集、B树、跳表、通用哈希、布隆过滤器、Freivalds 矩阵验证、Karger 最小割。这一卷让你理解两件事：单次操作很慢，不代表整体很慢（摊还分析）；随机算法也能给出严格的正确率和复杂度保证（随机化）。数据结构在这里不是孤立的容器，而是和摊还、随机化思想紧密结合的工程利器。

第七卷·线性规划与对偶思想（7.1–7.8）。单纯形法、线性规划对偶、原始对偶算法、匈牙利算法、整数规划、随机舍入、拉格朗日松弛、优化问题归约。这一卷把算法设计从离散的"规则"推进到"约束、可行域、松弛、对偶"。很多看起来完全不同的问题，会在这一卷里呈现出相同的数学结构——对偶思想会反复出现。

第八卷·计算复杂性与NP完全性（8.1–8.7）。P、NP、NP完全，多项式归约，SAT 与 Cook-Levin 定理，各种归约（3SAT→顶点覆盖、哈密顿回路→旅行商），子集和与伪多项式，NP完全性证明。这一卷要让你真正理解四件事：NP 代表"解可以在多项式时间内验证"；NP 完全问题之间能通过归约建立联系；新问题的困难程度可以用已知困难问题来证明；指数时间算法有时具有理论上的必要性（不是你菜，是问题本身就这么难）。

第九卷·NP难问题的求解方法（9.1–9.9）。上一卷告诉你"很多问题没有多项式解法"，这一卷负责解决**"发现是 NP 难之后该怎么办"**。顶点覆盖近似、集合覆盖近似、Christofides 旅行商、背包 PTAS、参数化算法、核化、分支定界、局部搜索、模拟退火。你会学到近似、参数化、剪枝、松弛、启发式搜索这几条退路，而不是停留在"无解"的结论上。

第十卷·现实系统中的算法（10.1–10.9）。LZ77 压缩、RSA、Diffie-Hellman、Count-Min Sketch、HyperLogLog、滑雪租赁、缓存无关排序、分布式 Bellman-Ford、一致性哈希。这一卷展示算法理论在压缩、密码、数据库、流式计算、缓存、网络和分布式系统里的实际作用。你会看到前面学的那些"抽象方法"，是怎么撑起了每天在用的那些系统的。

第十一卷·算法设计的统一视角（11.1–11.12）。不变量法、分解法、状态设计法、交换法、松弛法、增广法、归约法、对偶法、随机化法、近似法、下界证明法、竞争分析法。这一卷不再增加新的算法家族，而是回看前十卷，把具体算法提炼成可以迁移的设计工具。读完这一卷，你面对一个陌生问题时，应该能依次判断：有没有不变量可维持？能不能分治？当前选择经不经得起交换论证？有没有最优子结构？能不能转化成图、流、匹配或线性规划？精确求解受不受 NP 难限制？该不该用近似、参数化或随机？当前复杂度离理论下界还有多远？

5.五个学习阶段

十一卷对应五个学习阶段，每个阶段都有明确的能力目标。

第一阶段·理解算法（第一、二卷）。 目标：你能实现这些算法，并用复杂度语言描述它们的性能。这是"会用"的层次。排序、查找、分治——这些是最基本的工具箱，先把它们的手感练出来。

第二阶段·设计算法（第三、四、五卷）。 目标：你能识别出分治、贪心、动态规划、松弛、增广这些结构。给你一个问题，你不只是会硬想，而是能归类"它属于哪一类设计范式"，然后套用对应的套路。第四卷的证明工具，让你不光设计出来，还能说服自己和别人"它是对的"。

第三阶段·理解算法背后的数学结构（第六、七卷）。 目标：你能使用摊还分析、随机化、线性规划和对偶思想。到这一层，算法不再只是"步骤"，而是数学结构上的操作。你会开始欣赏不同问题之间的统一性。

第四阶段·理解计算能力的边界（第八、九卷）。 目标：你能分析 NP 完全性，并为 NP 难问题选择合理的求解方式。这一层回答的是"问题本身到底有多难"——有些困难是问题固有的，你得学会用近似、参数化去绕，而不是死磕精确解。

第五阶段·迁移算法思想（第十、十一卷）。 目标：你能把算法理论迁移到真实系统，并形成独立分析陌生问题的能力。这是这门课的终点——不是让你记住 100 个算法，而是让你拥有一套可以迁移的思维工具箱。

6.怎么读效果最好

最后给你三条学习建议。

第一，算法一定要自己动手实现一遍。 光看懂和真写出来是两个层次。尤其是排序、二分、并查集、Dijkstra 这些，别满足于"我看懂了思路"，拿你最熟的语言从零敲一遍。你会在实现的细节里（比如二分的边界、Dijkstra 的堆更新）遇到光看思路遇不到的坑，这些坑才是真功夫。

第二，证明要自己推，别只看结论。 第四卷开始会大量出现证明。每个证明我都给了完整推导，但你看十遍不如自己拿笔推一遍。循环不变量、主定理、交换论证这些，亲手推过一次，理解层次完全不同。

第三，卡住的时候回来看主线。 学到中间容易钻进某个算法的细节出不来。定期回来对照一下那条主线（实现→分析→设计→迁移），确认自己当前站在哪一层，就不会迷路。

准备好了，就从 1.1 插入排序开始吧。