第一章 内功总纲：为什么学、复杂度与递归

第一章 · 内功总纲：为什么学、复杂度与递归

本章要回答的三个问题：同样功能的代码为什么快慢悬殊？如何不靠跑分、只靠推理就估出一段代码的效率量级？递归这种"自己调用自己"的写法，威力从哪来、又会在哪里反噬？

为什么会有这一章

初学者判断代码好坏，最常见的办法是跑一遍掐表。掐表的问题在于：换台机器结果就变，数据规模一变结论还可能反转——小数组上插入排序赢过快排并不稀奇。真正稳定的判断依据，是操作次数随输入规模增长的趋势，也就是复杂度分析。它相当于武学里的"内力度量术"：不看你招式花不花哨，只看一分输入要付出几分内力。量级差出来的后果是具体的：同样处理百万级数据，平方级要按万亿次操作记账，对数级连二十次都不到——这不是快慢之争，是能与不能之争。面试官问复杂度，考的也不是背功，而是你能不能现场数出一个结构每一步的代价。

这一章还安置了另一件总纲级工具：递归。归并排序、快速排序、树的遍历、动态规划的原始形态，全都靠递归表达；而递归的代价（调用栈）与陷阱（爆栈、重复计算）也需要在总纲里交代清楚，后面各章才敢放心使用。

读完能解决什么

对照开头的问题，本章交出这些可检验的知识点清单：

• 能复现"同一任务、两种结构、操作次数相差百倍以上"的对照实验，并解释原因；
• 能数出给定代码的基本操作次数，写出大 O、大 Ω、大 Θ 三种刻画，并说清三者的差异与适用场合；
• 掌握复杂度分析的操作规则：顺序相加取最大、嵌套相乘、循环内变量步长的影响；
• 理解均摊分析的含义，能用它解释动态数组尾部追加为何是均摊常数；
• 能画出递归调用的栈帧过程，算出递归深度与总调用次数；
• 能识别并修复两类递归事故：重复子问题（用记忆化）与递归过深（改成迭代或显式栈）；
• 能对"空间复杂度"同样记账：缓存、递归栈、辅助数组各占多少，随输入怎么涨。

各节怎么分工

三节的修习顺序有讲究：1.1 先解决"为什么值得练"的动力问题，1.2 交付全册通用的度量工具，1.3 把工具用在递归这种最容易被误用的写法上。1.2 与 1.3 的产出会被后面每一章直接引用——遇到引用处回不来，就说明总纲还得再过一遍。带着这三节上路，后面六章的每个复杂度结论你都能亲手推出来，而不是背下来。

先决条件

• 会一门编程语言的基本语法：变量、循环、函数、列表；
• 高中数学水平即可，涉及对数与指数的地方会现场补一句直觉解释；
• 不需要任何数据结构前置知识，本章就是地基；
• 手边备一个能跑 Python 的环境：本章的每个数字都欢迎亲手复算，量过的才算懂；
• 每节末尾的要点回顾可以当自测清单用：能逐条复述再翻页。

往下走到哪

本章出口是两把尺子：一把量结构（复杂度），一把量功法（递归栈）。下一章进入第一路根基结构——线性结构，你会看到数组的随机访问、链表的插删、哈希表的秒查，它们的威力全部要用本章的尺子来度量；第五章排序、第六章分治与动态规划，也会反复回引本章的推导规则。学不透总纲，后面每一步都只能背结论。练法建议：每学完后面一章，回头用本章的规则把新结构的操作复杂度自己推一遍，推不出来的地方就是薄弱点。

本章知识结构