Java算法分析习题精解：复杂度估算、递归测度与链表避坑

简介：这份习题答案文档对应《数据结构与算法分析（Java语言描述）》第三版，面向正在学习数据结构、算法分析与Java程序设计的学生及自学者，用于课后练习核对、思路梳理和考前查漏补缺。压缩包仅含1个docx文件，大小约1.52MB，便于直接检索与批注。内容围绕教材开篇及核心章节的习题展开，包含递归处理文件包含关系、整数按位递归求和、数学归纳法证明对数性质、等比数列与差分求和、模运算与指数定律、大O记号及对数估计等解答，并给出相应推导过程，可帮助读者理解递归构造、数学推理、文件I/O与复杂度分析之间的联系。目前已有2435人学习下载，适合需要对照答案验证解法、补强算法分析基础的读者使用。

1. 复杂度不是数循环层数：三重循环为什么只有 O(N⁴)

学 Java 数据结构与算法分析的人，几乎都在复杂度估计这一章栽过跟头：把循环嵌套层数当成复杂度的阶数，一层是 O(N)，三层就是 O(N³)。这个直觉在一道典型习题上会直接判错——三层嵌套的循环体，真实代价是 O(N⁴)，而不是把三层上界相乘得到的 O(N⁵)。差别不在算术，而在于你默认了「每一层都跑满上界」。真正要建立的能力，是判断某段代码在什么条件下才被执行，而不是数括号。这份第三版习题解答值得逐题对着看的地方，就在于它把每个「为什么是这个阶」的判断过程摊开写了，而不是甩一个结论。

2. 递归的合同：从 processFile 的环检测到 ones 的位计数

递归在教材里通常被描述成「函数调用自己」，这个说法几乎不解释任何东西。真正能让人写出正确递归的，是一条更像合同的约束：每一次调用都必须把某个可度量的量严格变小，且本层只做有限量的组装工作。测度选错了，代码看起来完全正确，跑起来就是栈溢出；测度选对了，递归深度和复杂度基本可以口算出来。

2.1 三个必须同时成立的条件

我把递归的正确性拆成三件事，缺一件就会翻车。第一，存在一个从输入映射到非负整数的测度函数，且每次递归调用后测度严格减小——这是终止性的来源；第二，终止条件必须覆盖测度的所有极小取值，漏一个就是无穷递归；第三，本层除了递归调用之外的工作量必须可界定，否则复杂度分析无从下手。

以教材里那道「统计整数 n 的二进制表示中有多少个 1」的题为例，测度是 log₂n，因为每层都在做 n/2。但很多人第一反应会写成 n-1，那样测度是 n，递归深度从 32 层变成 21 亿层。代码只差一个字符，行为差了一个数量级的世界。这就是为什么我坚持在写递归前先写一句「测度是什么」，写不出来就说明还没想清楚。

2.2 processFile：环检测为什么必须记录「未返回的调用」

文件包含处理这道题是整份解答里最能体现设计取舍的一处。需求是：读一个文件，遇到#include SomeFile就递归处理被包含的文件；同时要防止 A 包含 B、B 又包含 A 这种自引用导致的无限递归。

private static final List<String> inProgress = new ArrayList<>(); static void processFile(String fileName) { // 环检测只看「当前调用路径」，不看历史全集 if (inProgress.contains(fileName)) { System.out.println("skip circular include: " + fileName); return; } inProgress.add(fileName); // 进入：记账 try { for (String line : readAllLines(fileName)) { if (line.startsWith("#include")) { String target = line.substring("#include".length()).trim(); processFile(target); // 递归：被测度是「待处理文件数」 } else { handle(line); } } } finally { // 退出：必须与 add 严格后进先出配对，用栈顶删除而不是按名字删 inProgress.remove(inProgress.size() - 1); } }

这里最关键的不是递归本身，而是inProgress这个结构的语义。它必须是一个「调用栈的影子」：进入时追加，退出时弹出，内容随递归深度变化。如果图省事换成一个HashSet记录所有处理过的文件，程序不会死循环，但会静默地漏掉合法场景——同一个公共头文件被两个不同的分支各自 include 一次，第二份就被跳过了。环检测要的是「当前路径上有没有它」，去重要的是「历史上有没有它」，这两个问题长得像，语义完全不同。

finally里用inProgress.remove(inProgress.size() - 1)而不是remove(fileName)，是因为异常路径下按名字删可能删错位置；栈顶删除保证结构在任何退出路径上都和调用栈同构。这个细节在教材答案里往往被省略，但它决定了这段代码能不能放进真实项目。

提示：只要递归里出现了「打开」这类资源获取动作，就必须假设中间任何一行都可能抛异常，配对的释放动作只能放在 finally 里。

2.3 ones(n)：为什么加法让递归可以压平成循环

public static int ones(int n) { if (n < 2) return n; // 0 和 1 直接返回，终止条件同时就是答案 return n % 2 + ones(n / 2); // 最低位 + 剩余位的计数，组合方式是加法 }

这段代码的正确性依赖一个容易被忽略的性质：n % 2是本层剥离出来的一个 bit，ones(n / 2)是剩下的 bit 的计数，两者用加法组合，而加法满足结合律与交换律。正因为组合运算满足结合律，这个递归才能被无损地改写成while (n > 0) { count += n & 1; n >>= 1; }，空间从 O(log N) 降到 O(1)。

反过来想，什么递归压不平？树的前序遍历。因为「先访问根、再访问左子树、再访问右子树」这个顺序不能重新结合，本层的输出必须夹在两次递归中间，你只能自己维护一个显式栈。这也解释了为什么 processFile 那道题没法简单改成一个循环：它是一个嵌套结构的遍历，不是可结合的聚合。

还有一层：ones的递归深度是 O(log N)，即使 n 取到 int 的最大值也只有 32 层，永远不可能栈溢出。这解释了为什么这道题在教材里被用来演示递归而不是演示风险——测度选得越小，递归越安全。

2.4 递归的代价到底花在哪

递归的开销从来不是「函数调用慢」，而是三个具体的东西：栈帧占用的连续内存、每次调用保存的返回地址和局部变量、以及编译器无法内联带来的优化机会损失。深度 O(log N) 的递归，这三点都可以忽略；深度 O(N) 的递归，在 N 到十万级时栈就撑不住了。

实际工程里的判断标准很朴素：深度是对数级、且组合运算满足结合律的递归，随便写；深度是线性甚至指数、或者需要本层做大量临时对象的递归，一律改迭代或手写栈。教材里那些看起来「为了教递归而递归」的题，练的其实是这个判断力。

3. 和式与归纳不是数学装饰：快速幂为什么只要 9 次乘法

算法课里最容易被当成「数学复习」跳过的，就是求和技巧和归纳法证明。但复杂度分析里几乎每一次「这个算法是 O(N log N)」的结论，背后都是一次和式估算；每一次「这个递推 T(N) = T(N/2) + O(N) 的解是 O(N)」的结论，背后都是一次归纳。跳过这部分，后面所有复杂度结论都只能靠背。

3.1 给和式乘公比做差：一个通杀公式

教材那道S = 1/4 + 2/16 + 3/64 + …的题，标准解法是给整个和式乘以公比再做差。设 S = Σ i/4ⁱ：

S = 1/4 + 2/4² + 3/4³ + 4/4⁴ + … 4S = 1 + 2/4 + 3/4² + 4/4³ + … 相减： 3S = 1 + 1/4 + 1/4² + 1/4³ + … = 1 / (1 - 1/4) = 4/3 S = 4/9

机制只有一句话：乘公比让各项的分母对齐，相减时「i 这个线性增长的系数」被差分成常数，于是非线性的求和变成了等比级数。这个手法在算法分析里出现的频率远超想象——哈希表线性探测的期望探测次数、随机快排的期望比较次数、二叉树叶子节点按深度的加权和，拆开都是同一类结构。

二阶版本更值得看：S₂ = Σ i²/4ⁱ乘 4 相减后得到3S₂ = 1 + 3/4 + 5/16 + 7/64 + …，右边又把 i² 降成了 i 的一次式，于是3S₂ = 2S₁ + 4/3 = 20/9，S₂ = 20/27。这里的设计意图很明确：差分一次降一阶，反复差分直到化成等比级数。懂得这个「降阶」的节奏，比记住任何一个具体答案都有用。

写完推导后我习惯用代码对拍一遍，防止符号推错：

static double sumSquareOverPow4(int terms) { double s = 0; double p = 0.25; // p 始终保持 4^-i，逐项递推而不是反复调用 Math.pow for (int i = 1; i <= terms; i++) { s += (double) i * i * p; // 累加 i^2 / 4^i p *= 0.25; // 公比固定为 1/4，每项衰减 4 倍 } return s; }

terms取 30 时结果已经是 0.740740…，与 20/27 完全吻合。为什么收敛这么快？因为公比只有 1/4，截断误差的上界是「下一项 / (1 - q)」，随项数指数衰减。这个误差界的推导方式和差分法是同一套东西。

3.2 归纳法为什么按区间分段而不是按点

证明log X < X（X > 0）那道题，最容易看懵的是它为什么要在 [1, 2]、[2, 4]、[4, 8] 这样的区间上归纳，而不是直接对 X 归纳。原因在于对数运算的性质：log(2Y) = 1 + log Y。当你想证明log Y < Y对 Y ∈ (2p, 4p] 成立时，需要把 Y/2 落回 (p, 2p] 这个上一段的区间，才能用上归纳假设，然后靠1 + Y/2 < Y/2 + Y/2收尾。

这里的技巧是把归纳假设参数化到区间，而不是参数化到具体的点。点的加强版本反而更难证，比如「对所有整数 n 成立」，因为用不上那个除以 2 的结构。

这个思路在工程里对应的是循环不变式。写二分查找时你要说明「答案始终在 [low, high] 内」，这个不变式必须由「每次迭代区间严格缩小」来维持。一旦某条分支没能缩小区间，不变式就退化成永真，循环也就不会终止了——这正好是后面避坑章节要讲的那个 StackOverflowError。

3.3 快速幂：乘法次数为什么是 log N 加一的个数

教材里那道X^62的题，用 8 个中间值（X²、X⁴、X⁸、X¹⁰、X²⁰、X⁴⁰、X⁶⁰、X⁶²）凑出了答案。这个凑法背后有个统一公式：计算 X^N 所需的最少乘法次数是⌊log₂N⌋ + popcount(N) - 1。N = 62 时，log₂62 取整是 5，62 的二进制 111110 有 5 个 1，加起来减一等于 9。

二进制扫描的实现最干净：

static long pow(long x, int n) { long result = 1; long base = x; while (n > 0) { if ((n & 1) == 1) { result *= base; // 当前二进制位是 1，把这一份乘进来 } base *= base; // 平方链：x -> x^2 -> x^4 -> x^8 n >>= 1; // 右移看下一位 } return result; }

关键机制是平方链的复用：算 X⁸ 不需要乘 8 次，只需要在 X⁴ 上再平方一次，而 X⁴ 又来自 X² 的平方。指数每右移一位，base 就自动升一次幂，这就是为什么乘法次数只跟指数的二进制长度和 1 的个数有关，跟 N 的数值大小无关。N 从一百万涨到两百万，乘法次数只加一次。

这也解释了教材为什么强调「B = log N 比 N 更适合度量输入规模」（那道素数测试的题）。算术运算的代价随操作数的位数增长，用数值大小当规模，会把「一次大数乘法约等于多少次小整数乘法」这件事完全掩盖掉。

3.4 模运算：为什么指数可以先缩小

2^100 mod 5那道题的解法是发现2^4 = 16 ≡ 1 (mod 5)，而 100 是 4 的倍数，于是结果直接是 1。这个观察的通用形式是：当 a 与 m 互素时，a^b mod m = a^(b mod φ(m)) mod m，其中 φ 是欧拉函数。哈希、密码学里的模幂运算全靠这一步先把指数降下来，否则指数本身就是一个天文数字。

工程上的直接后果是：永远不要先算a^b再取模。long 在 b 超过 64 时就溢出了，而正确的写法是每乘一次就取一次模。教材里那道题考的是数学性质，但它指向的实现纪律是「取模必须发生在乘法之后、下一次乘法之前」。

4. 指针重连的顺序约束：链表相邻交换错一步就断链

链表题在教材里被归到「基础」,实际写起来是全书最容易出隐蔽 bug 的地方。因为它没有数组那样的下标可以自检，错了不会报错，只会在某个后续操作时莫名其妙地拿到 null 或者陷入环。相邻节点交换那道题，两种链表写法差了整整三个赋值，恰好吃透了「单链表只有一条边、双链表每条边有两个视角」这个区别。

4.1 单链表：三次重连里只有一处顺序是硬的

// beforeP 是要交换的两个相邻节点的前驱；p 与 afterP 均非空 static <AnyType> void swapWithNext(Node<AnyType> beforeP) { Node<AnyType> p = beforeP.next; Node<AnyType> afterP = p.next; p.next = afterP.next; // ① 必须最先：此时读到的还是交换前的后继 beforeP.next = afterP; // ② 前驱跨过 p，直接指向 afterP afterP.next = p; // ③ 最后才把 afterP 接回 p }

三条语句里只有 ① 的位置是硬约束。它读的是afterP.next，也就是原来排在 afterP 后面的那个节点；如果 ③ 先执行，afterP.next已经被改成了 p，① 再把 p 的 next 指向自己，链表当场成环。② 和 ③ 之间没有相互依赖，因为它们写的是不同对象的字段。

另一个容易忽略的是边界：如果待交换的两个节点正好是表尾，afterP.next是 null，① 会把p.next置为 null，这是正确的。但如果 p 本身就是最后一个节点，p.next是 null，那么afterP = p.next直接就是 null，下一行 NPE。教材的答案里写的是「错误检查省略」，实际代码必须补，或者干脆在链表头部放一个哑节点，让「前驱」永远存在。

4.2 双链表：每条边有两个视角，赋值翻倍

// p 与 afterP 是待交换的两个相邻节点 static <AnyType> void swapWithNext(Node<AnyType> p) { Node<AnyType> beforeP = p.prev; Node<AnyType> afterP = p.next; p.next = afterP.next; if (afterP.next != null) { // 尾节点的后继为空，必须判空 afterP.next.prev = p; // 后半段那条边的另一个视角要一起回填 } beforeP.next = afterP; afterP.next = p; p.prev = afterP; // 每改一条 next，就要同步改对方的 prev afterP.prev = beforeP; }

单链表改 3 个引用就够，双链表要改 6 个。多出来的三个不是冗余，而是「每条边被两个节点分别记录一次」的必然代价：x.next.prev必须等于 x，这是整条链表的核心不变量。教材给的答案只写了 4 处赋值，把后半段的prev回填略掉了，直接照抄会在下一次反向遍历时拿到悬空引用。

写双链表代码时我习惯配一个自检函数，改完指针立刻跑一遍：

static <AnyType> boolean checkDList(Node<AnyType> head, Node<AnyType> tail) { for (Node<AnyType> p = head.next; p != tail; p = p.next) { if (p.next.prev != p || p.prev.next != p) { return false; // 任意一条边两端记录不一致，立即判定链表已损坏 } } return true; }

这个函数的价值在于把「隐式不变量」变成「可执行断言」。链表题的调试痛苦，八成来自 bug 发生在第 3 步、异常抛在第 30 步，中间隔着一整段业务逻辑，靠肉眼根本追不回去。

4.3 交集与并集：双迭代器归并的前提被藏起来了

教材里求两个列表的交集和并集，用的是同一套双指针归并骨架：

static <AnyType extends Comparable<? super AnyType>> void intersection(List<AnyType> L1, List<AnyType> L2, List<AnyType> out) { ListIterator<AnyType> it1 = L1.listIterator(); ListIterator<AnyType> it2 = L2.listIterator(); AnyType a = it1.hasNext() ? it1.next() : null; AnyType b = it2.hasNext() ? it2.next() : null; while (a != null && b != null) { int cmp = a.compareTo(b); if (cmp == 0) { out.add(a); a = it1.hasNext() ? it1.next() : null; b = it2.hasNext() ? it2.next() : null; } else if (cmp < 0) { a = it1.hasNext() ? it1.next() : null; // L1 当前元素更小，跳过它 } else { b = it2.hasNext() ? it2.next() : null; // L2 当前元素更小，跳过它 } } }

时间复杂度是 O(|L1| + |L2|)，看起来很漂亮。但这里藏着一个教材没明说的前提：两个列表都必须已经有序。compareTo只告诉你当前这一对的相对大小，能不能安全跳过某个元素，完全取决于「后面的元素只会更大」这个单调性。如果输入无序，这个算法不但结果错，而且错得毫无规律，这就是那种典型的血泪经验——测试用例全过，线上数据一换就集体错位。

还有一个写法上的坑：用a != null当循环条件，隐含了「列表元素不允许为 null」。如果业务上真往里塞了 null，循环会提前结束并静默返回不完整结果。更稳的写法是把「有没有下一个」和「下一个是什么」拆开，用hasNext()做循环条件，元素值单独存。

5. 避坑与排查：洗牌不均、二分死递归与概率 1 的终止

这一章记录的是我在对照这份解答做练习时真正卡住过的五处，每一条都按「现象 → 原因 → 解决」写，不是泛泛的注意事项。

5.1 交换式洗牌：27 不能被 6 整除这件事

现象：用「对每个位置 i，随机取一个 0 到 n-1 的下标与之交换」来洗牌，跑了三十万次统计，某些排列出现次数明显高于其他排列，n = 3 时偏差肉眼可见。

原因：n = 3 时三次交换各自从 3 个下标里独立取值，一共 27 种等可能的随机数组合；而目标排列只有 6 种。27 不能被 6 整除，就不可能把 27 个等概率的路径平均分给 6 个结果。这个论证漂亮的地方在于它根本不需要算每种排列的具体概率，一个整除关系就否掉了均匀性。

解决：改用 Fisher-Yates，第 i 次只跟 [i, n-1] 区间内的位置交换，让第 i 个位置的选择空间正好是 n-i 种，乘积 n! 恰好等于排列总数，一一对应。或者用 Floyd 的抽样式算法，每次从剩余池里随机取出一个放进输出，天然不重复。

5.2 二分查找死递归：low=1、high=2 时 mid 永远等于 1

现象：递归版二分查找在数组只有两个元素、且目标值落在后半段时抛 StackOverflowError，其他输入全部正常。这个 bug 特别阴，因为它要么在极小规模触发，要么在特定边界触发，随机测试经常漏掉。

原因：mid = (low + high) / 2，当 low = 1、high = 2 时 mid = 1，递归调用search(low, mid)的参数和调用前一模一样，区间没有缩小。测度没下降，终止条件永远达不到。

解决：分支必须保证区间严格收缩。写成search(low, mid)的那一侧，mid 必须取(low + high + 1) / 2向上取整；或者干脆改成循环版本，并在循环末尾断言newLow > low || newHigh < high。我现在写二分的习惯是先写死循环条件，再写两个分支的收缩方式，最后回头看区间是否可能不动。

5.3 逐次随机取数去重：N/(N-i) 的期望代价

现象：用「随机取下标，检查是否用过，用过就重取」的方式生成排列，n = 10000 时耗时还可以，n 涨到 100000 时慢了将近十倍，涨幅明显超过线性。

原因：已经用了 i 个数字时，单次随机命中未使用数字的概率是 (N-i)/N，于是重试次数的期望是 N/(N-i)。把 i 从 0 加到 N-1 累加，总期望代价是 N 乘上调和级数，也就是 O(N log N)。这个推导本身不难，难的是它容易被「每次只多试几次」的直觉掩盖过去——越接近尾声，重试越疯狂。

解决：换成部分洗牌或 Floyd 抽样，每个元素只处理一次，代价降到严格 O(N)。判断标准很简单：如果你写的随机算法里出现了「重试直到满足条件」的结构，就要立刻问一句期望重试次数随规模怎么变。

5.4 概率 1 终止不等于有上界

现象：随机化算法做压力测试，绝大多数请求毫秒级返回，极少数出现几十秒的长尾，监控上表现为一个消除不掉的 P99 尖刺。

原因：这类算法不存在「最坏情况运行时间」这个量，因为总存在有限但非零的概率让它一直不终止。它能保证的只是「以概率 1 终止」。教材里明确指出的这一点，在工程上意味着你不能用「最坏耗时」去做容量规划。

解决：给随机过程加一个迭代上限，超限后回退到确定性算法；或者用「首次成功概率 p，则 k 次内成功的概率是 1-(1-p)^k」这类界去做超时设置。把不可界的量变成可界的量，才是能上线的东西。

5.5 同阶函数被当成不同阶

现象：把N log N优化成N log(N²)，本以为降了复杂度，实测毫无变化。

原因：log(N²) = 2 log N，两者只差一个常数因子 2，在大 O 意义下完全同阶。教材在复杂度排序那道题里特意把这两个放一起，就是为了考这一点。类似的还有2^N和2^(N/2)，后者是前者的平方根，差距是指数级的，不能混为一谈。

解决：比较大 O 之前先做代数化简，把对数里的幂提出来、把常数因子丢掉，再看剩下的形式。化简完还是同一个表达式，就老老实实承认这是常数优化，别指望量级收益。

6. 取舍：把答案当结论背，还是当判断依据用

对照答案做完整本习题，我最深的体会是：真正能迁移到工程里的，从来不是某道题的结论，而是得出那个结论时用的判断依据。

最典型的是复杂度与输入规模的换算关系。教材里那几道「时间放大 5 倍，输入规模能放大多少」的题，本质上是在训练一种直觉：不同增长阶对规模增长的容忍度差得有多离谱。

这张表才是那些题真正想让人记住的东西。它直接决定了你面对一个 10 万条数据的需求时，该不该拒绝 O(N²) 的方案；也决定了一个已经上线、数据量每月涨 20% 的服务，还有几个月的安全期。而这些判断，靠背「归并排序是 O(N log N)」是得不出来的。

另一类判断依据是「这份解答里哪些地方省略了检查」。链表交换省略了空指针判断，集合归并省略了有序性前提，随机置换省略了最坏情况不存在这个事实。这些省略在教材语境下是合理的——它想让读者看主干逻辑；但在工程语境下，省略的每一处都是潜在的线上事故。能识别出「这里被省略了什么」，比能默写出代码更值钱。

还有一种更微妙的取舍：什么时候该满足于一个「够好」的界。斐波那契那道题里，教材用归纳法证明了 Fₖ 的上界，而没有去推通项公式，因为在算法分析里你几乎从不需要精确值，只需要知道它是指数增长的。判断「这个精度够不够用」，是分析能力的一部分，而习题答案里很少显式写出来。

从那以后我每做完一道算法题，都强制走一遍三步：写一句这个解法赖以成立的测度或前提是什么，写一句它在什么输入下会退化，再写一个十行以内的对拍程序把结论跑一遍。三步做完，这道题才算真的吃进去了，而不只是「看懂了答案」。这份按章节排好、关键推导都摊开写的解答，正好适合拿来做这套动作——对着题号翻到对应位置，先自己写判断依据，再看它是怎么收的。希望帮到你。

本文还有配套的精品资源，点击获取