从习题解答看数据结构与算法分析：复杂度推导与实现避坑

简介这份PDF是Mark Allen Weiss《Data Structures and Algorithm Analysis in C》第二版的配套习题解答手册面向正在学习数据结构与算法分析课程、需要对照课后练习查漏补缺的高校学生与自学者。内容覆盖算法复杂度分析、表栈队列、树、哈希、优先队列堆、排序、不相交集合、图算法、算法设计技巧、摊还分析及高级数据结构等章节解答以伪C代码和思路说明为主部分题目仅给出要点或留给读者补充。资源包共1个PDF文件大小约233KB轻量便于在电脑或平板上查阅已有143人学习。它可用于核对习题结论、理解大O分析与经典结构实现思路并借助章节编排定位薄弱环节适合作为教材精读和考前复习的辅助材料。1. 习题解答手册为什么答案比正文更接近算法分析的真相很多人把这份 C 语言版数据结构与算法分析教材的第二版习题解答手册当成对答案的工具这其实低估了它。教材正文给出的是干净结论解答手册给出的是结论成立的条件时间复杂度怎么推、空间复杂度怎么估、大 O 表示法在什么边界上会骗人。比如增长率排序里N log N 和 N log(N²) 被放在同一档N^1.5 却排在 N log² N 后面这些顺序不是背出来的而是由极限、归纳和反例一步步压出来的。读这份手册的乐趣在于看见“数据结构为什么这样组织、算法分析为什么能 work”的中间层而不是只拿到一个最终答案。2. 算法分析增长率排序为什么不能只看大O符号2.1 从 2/N、37、√N 到 2^N 的排序看渐近比较的边界手册第 2 章开篇就给了一串函数排序2/N、37、√N、N、N log log N、N log N、N log(N²)、N log² N、N^1.5、N²、N² log N、N³、2^(N/2)、2^N。这个顺序背后不是“谁看起来复杂谁就大”而是每一对函数做极限比较的结果。2/N 随 N 增大趋于 0所以它排在最前37 是常数增长率是 0√N 小于 NN log log N 小于 N log N因为 log log N 增长极慢N log(N²) 化简后是 2N log N和 N log N 只差常数因子所以手册明确说两者同速。真正容易翻车的是 N log² N 与 N^1.5 的比较。两边同时除以 N变成比较 log² N 与 √N。对数多项式增长慢于任何正幂次所以 N^1.5 在 N 足够大时反超。这个“足够大”是渐近分析的关键限定词在小规模输入上37 可能比 2/N 大得多N² 算法也可能比 N log N 算法跑得快。大 O 描述的是上界不是紧界Θ 才表示同阶。血泪经验是排序算法在小数组上切回插入排序不是因为插入排序的渐近界更好而是因为它的常数和分支预测更友好。手册里还特意把 2^(N/2) 和 2^N 分开。两者都是指数级但底数不同差距在 N 增大时会被迅速拉开。读这种排序题时我一般会先把每个函数化简到最简形式再两两做比值极限最后才看手册的最终顺序。直接背顺序没有意义因为换一组函数就会露馅。2.2 反例与归纳证明解答手册如何拆掉“想当然”手册第 2 章有一组判断真假的题专门打“想当然”的脸。比如“若 T1(N)O(f(N)) 且 T2(N)O(f(N))则 T1(N)T2(N)O(f(N))”是真的因为两个上界相加还是上界。但“若 T1(N)O(f(N)) 且 T2(N)O(f(N))则 T1(N)/T2(N)O(1)”是假的反例取 T1(N)2N、T2(N)N、f(N)N比值是 2确实有界可如果取 T1(N)N²、T2(N)N、f(N)N²比值是 N没有常数上界。手册用这种最小反例说明大 O 只约束单个函数的增长不约束两个函数之间的商。更微妙的是乘法题。“若 T1(N)O(f(N)) 且 T2(N)O(f(N))则 T1(N)×T2(N)O(f(N))”同样不成立反例还是 N² 和 N乘积 N³ 已经超过 N² 的上界。这里的关键是 O 的传递方向T1 和 T2 各自被 f 压住不代表它们的乘积还被同一个 f 压住。手册的答案没有停在“假”字上而是把反例写全让读者看到假在哪里。还有一道题用振荡函数说明商没有渐近上界f(N) 在 N 为偶数时取 1、奇数时取 Ng(N) 在 N 为奇数时取 1、偶数时取 N。f/g 在 0 和无穷之间来回跳既不是 O(1)也没有稳定的增长阶。这个反例的价值在于提醒渐近分析默认函数有单调趋势遇到振荡、周期性、分段定义时先检查定义域和极限是否存在。手册里这类题不多但每一道都在训练“先找边界再谈结论”的习惯。归纳证明也是同一套思路。手册第 1 章证明 log X X 时先验证 0X≤1 和 1X≤2 的基例再假设 pX≤2p 成立推到 2pY≤4p。每一步不等式都写出来不跳步。斐波那契那一组题则用 φ1φ² 把递推式压成闭式。读这些证明时重点不是记住不等式而是看作者怎样选基例、怎样设归纳假设、怎样把目标规模折半。自己先推一遍再对照比直接看答案有效得多。2.3 幂运算与递归式从 O(log N) 乘法次数看“降规模”的代价手册第 2 章后面有一组幂运算题要求计算 X^62并统计乘法次数。最直接的做法是连乘 61 次时间复杂度 O(N)。但把指数拆成二进制后可以用平方链把规模压到 O(log N)。下面这段迭代快速幂把“降规模”的代价摊开每次循环只做一次平方遇到二进制位为 1 时再做一次乘法。/* 迭代快速幂把指数拆成二进制位避免递归栈和重复子问题 */ long long fast_pow(long long base, unsigned int exp) { long long result 1; while (exp 0) { if (exp 1u) { /* 当前最低位为 1累乘进结果 */ result * base; } base * base; /* 平方为下一位准备 */ exp 1; /* 指数右移一位 */ } return result; }这段代码的参数很直白base 是底数exp 是无符号指数result 累积当前结果。循环每轮把 exp 右移一位所以最多执行 ⌊log₂ exp⌋1 次平方操作每轮一次置位乘法只在二进制位为 1 时发生。若把 result 初始化为 1 的那次赋值不算乘法总乘法次数约为 ⌊log₂ N⌋ popcount(N) - 1和手册第 2 章给出的计数公式对得上。空间复杂度是 O(1)没有递归栈。对比递归写法 X^N X^(N/2) × X^(N/2)如果真写成两次递归调用复杂度会退化成 O(N)因为同一个子问题被算了两遍。正确做法是把 X^(N/2) 存进临时变量再平方。这个细节是很多人的翻车点看起来是分治实际上没有消除重复子问题。手册用幂运算这个小题把“分治不等于自动降复杂度”讲得很清楚也顺带引出了递归式求解和摊还分析的入口。3. 线性结构PrintLots 的 O(LP) 为什么不是 O(L×P)3.1 双指针同步推进的时序手册第 3 章有一道 PrintLots 题给定链表 L 和位置链表 P按 P 中指定的位置打印 L 中对应元素。朴素写法是对 P 中每个位置 p从头遍历 L 到第 p 个节点复杂度 O(L×P)。手册给出的答案用两个指针同步推进把复杂度压到 O(LP)。代码骨架如下void PrintLots(List L, List P) { int Counter 1; Position Lpos First(L); Position Ppos First(P); while (Lpos ! NULL Ppos ! NULL) { if (Ppos-Element Counter) { printf(%? , Lpos-Element); /* 命中位置打印 L 当前元素 */ Ppos Next(Ppos, P); /* P 推进到下一个待打印位置 */ } Lpos Next(Lpos, L); /* L 每轮都推进 */ } }参数和变量需要说清楚L 是被扫描的链表P 是位置链表Counter 记录 L 当前节点的位置编号从 1 开始Lpos 和 Ppos 分别是两个链表的游标。循环每轮先比较 Ppos 的位置和 Counter命中就打印并推进 Ppos无论是否命中Lpos 都前进一格Counter 自增。这样 L 只走一遍P 也只走一遍总代价 O(LP)。这个复杂度成立有两个前提P 中的位置按升序排列且 Next 操作是 O(1)。如果 P 乱序比如先要第 5 个再要第 2 个Lpos 已经走过第 2 个节点单指针无法回头算法会漏打。手册没有把这两个前提藏起来读答案时要自己补上。链表的位置抽象也让这件事变复杂Position 可能是节点指针也可能是数组下标如果是数组随机访问第 p 个元素是 O(1)根本不需要双指针。手册用伪 C 写答案保留了抽象性也留下了“具体实现取决于 Position 语义”的讨论空间。3.2 链表游标与位置语义抽象层级的取舍手册第 3 章反复提到“抽象性用了多少”的问题。链表、栈、队列都是抽象数据类型答案里可以用数组实现也可以用链式实现复杂度一样但常数和边界不同。以链表为例Position 如果是指针Next 是 O(1)FindKth 是 O(N)如果 Position 是数组下标FindKth 是 O(1)但插入删除要搬元素。PrintLots 之所以能用双指针是因为它只顺序扫描不需要随机访问一旦题目改成“按 P 中位置随机打印”链表就得反复从头找复杂度立刻上去。栈和队列的抽象更隐蔽。栈只暴露 push 和 pop用数组实现时push 可能触发扩容单次 O(N)但均摊 O(1)用链式实现时每次 push 都要分配节点单次 O(1)但分配器有成本。队列用循环数组时front 和 rear 的语义必须约定清楚rear 指向下一个空位还是当前尾元素直接决定判空判满条件。手册里的答案通常不会把每种实现都写全而是选一种最贴近题意的剩下的留给读者。这种“不完整”不是偷懒而是训练读者自己补边界。我一般会这么理解抽象数据类型定义“能做什么”数据结构实现决定“做得多快、边界多容易错”。PrintLots 的双指针解法之所以优雅是因为它利用了链表顺序访问的天然顺序而不是硬把链表当数组用。读手册第 3 章时先把每个操作的复杂度写在纸上再看答案用了哪种实现能少踩很多下标和空指针的坑。3.3 栈与队列的隐藏成本数组实现 vs 链式实现把栈和队列的实现放在一起对比隐藏成本会更清楚。下面这张表只列关键差异不追求穷尽操作/结构数组栈链式栈循环数组队列链式队列push/enqueue均摊 O(1)扩容 O(N)O(1)均摊 O(1)扩容 O(N)O(1)pop/dequeueO(1)O(1)O(1)O(1)空间开销连续内存可能预留每节点一个指针连续内存需空槽或计数每节点一个指针缓存局部性好差好差数组栈的扩容成本可以用均摊分析摊平容量从 1 开始翻倍124…N 2N所以 N 次 push 的总搬迁代价是 O(N)均摊到每次是 O(1)。但单次扩容仍然是 O(N)对延迟敏感的场合要提前 reserve。循环数组队列的判满条件是最容易翻车的地方如果只维护 front 和 rear不维护 size通常要牺牲一个槽用 (rear1)%capfront 判满frontrear 判空一旦 rear 的语义改成“当前尾元素”条件全变。链式队列没有扩容问题但每次 enqueue 都要分配节点dequeue 要释放节点分配器的开销和内存碎片会吃掉一部分性能优势。手册第 3 章的答案更关注抽象操作的正确性工程实现里的这些成本要自己补。一个实用的习惯是先确定队列的最大容量能预估就用循环数组不能预估且对延迟不敏感再用链式队列。不要因为“链表插入 O(1)”就无脑选链式缓存局部性在真实机器上经常是隐形的胜负手。4. 树与哈希平衡、堆序和散列冲突背后的不变量4.1 平衡二叉搜索树旋转不是目的高度差才是约束平衡二叉搜索树的核心不变量有两个左子树所有键小于根右子树所有键大于根每个节点左右子树高度差不超过 1。插入和删除可能破坏第二个不变量于是从修改点向上回溯找到第一个失衡节点按 LL、RR、LR、RL 四种形态做旋转。旋转本身是 O(1)回溯路径长度是 O(log N)所以单次插入删除是 O(log N)。旋转不是目的它只是把高度差压回去的手段真正要维护的是“整棵树高度保持在 O(log N)”。下面这个节点结构把高度记账显式写出来空树高度约定为 -1叶子为 0typedef struct AvlNode { int Element; struct AvlNode *Left; struct AvlNode *Right; int Height; /* 空树高度约定为 -1叶子为 0 */ } *AvlTree;参数说明Element 是键值Left/Right 是左右孩子Height 是当前节点高度。旋转后要先更新低位节点的高度再更新高位节点顺序反了高位节点会拿到旧高度后续平衡判断全错。常见翻车还有空指针高度计算高度前先判空空返回 -1不要返回 0 又混用叶子高度。删除比插入麻烦因为删掉一个节点可能让整条回溯路径上的节点都失衡最坏要一路旋转到根。红黑树用颜色约束代替严格高度差换取更少的旋转次数伸展树不存高度靠访问局部性把摊还代价压到 O(log N)。这些结构在手册第 4 章和第 12 章都有对应题目答案通常只给关键步骤旋转的指针改法要自己画图。我一般会先画三节点的小树把四种失衡形态各转一遍再写代码直接在纸上推指针比调试器里看地址清楚得多。4.2 哈希表负载因子、探测序列与再散列阈值哈希表的核心问题是把大键空间映射到小桶数组冲突不可避免。分离链接法给每个桶挂一条链表负载因子 λN/M 表示平均链长查找代价 O(1λ)。开放定址法把冲突元素放进表内其他空槽线性探测容易形成一次聚集平方探测能打散但可能探测不到全表双散列用第二个哈希函数决定步长要求步长与表大小互素。无论哪种方法删除都不能简单置空开放定址法里置空会截断后续元素的探测序列必须用墓碑标记查找遇到墓碑继续走插入可以复用墓碑。字符串哈希是另一个容易踩坑的地方。直接把字符 ASCII 码累加冲突率高得离谱用多项式滚动哈希乘数取一个小素数分布会好很多。下面这段代码用 31 作为乘数利用无符号整数溢出自动模 2³²最后对桶数取模/* 经典多项式滚动哈希h h * 31 c31 是经验选的小素数 */ unsigned int string_hash(const char *s, unsigned int table_size) { unsigned int h 0; while (*s ! \0) { h h * 31u (unsigned char)*s; s; } return h % table_size; /* table_size 取素数减少聚集 */ }参数s 是待哈希字符串table_size 是桶数。循环逐字符更新 h时间复杂度 O(len)空间 O(1)。31 不是唯一选择但它小、是奇数、乘法可以移位优化所以常见。table_size 取素数能让取模分布更均匀如果表大小是 2 的幂可以用位掩码代替取模但要求哈希函数低位足够随机。安全场景不能只用固定乘数攻击者可以构造大量同余字符串制造冲突需要加随机种子。再散列是哈希表保持性能的关键。负载因子超过阈值分离链接常用 1开放定址常用 0.5 到 0.75时把桶数扩到约两倍的下一个素数重新插入所有元素。单次再散列 O(N)但摊还到每次插入仍是 O(1)。手册第 5 章的答案会讨论不同冲突解决方法的期望代价读的时候注意区分“平均情况”和“最坏情况”哈希表的最坏情况可以退化到 O(N)这不是实现错误而是哈希冲突的固有风险。4.3 优先队列二叉堆的数组下标映射与 buildHeap 线性时间二叉堆是一棵完全二叉树用数组存储不需要指针。最小堆满足父节点不大于子节点堆顶就是最小值。0 基数组的下标映射是父节点 (i-1)/2左孩子 2i1右孩子 2i21 基数组则是父 i/2左 2i右 2i1。插入时把新元素放末尾再上滤删除堆顶时把末尾元素移到根再下滤两者都是 O(log N)。下面这段是 0 基最小堆的下滤/* 0 基最小堆的下滤把 hole 位置的元素下沉到合适位置 */ void percolate_down(int heap[], int n, int hole) { int child; int tmp heap[hole]; for (; hole * 2 1 n; hole child) { child hole * 2 1; /* 左孩子 */ if (child 1 n heap[child 1] heap[child]) { child; /* 选较小的孩子 */ } if (heap[child] tmp) { heap[hole] heap[child]; /* 孩子上移 */ } else { break; } } heap[hole] tmp; /* 放到最终空位 */ }参数heap 是堆数组n 是元素个数hole 是起始空位。循环条件是左孩子存在先选左右孩子中较小的一个再和 tmp 比较小就上移否则停止。最后把 tmp 放回最终空位。buildHeap 从最后一个非叶节点 n/2-1 开始倒序对每个节点下滤。总代价不是 O(N log N)而是 O(N)高度为 h 的节点最多有 N/2^(h1) 个每个下滤代价 O(h)求和 ∑ h/2^h 收敛到常数。常见翻车点有三个0 基和 1 基混用导致下标差一buildHeap 从最后一个元素开始而不是最后一个非叶节点比较符号写反最小堆变成最大堆。左式堆和斜堆用合并操作代替上滤下滤合并代价 O(log N) 或摊还 O(log N)适合需要频繁合并的优先队列。二项队列用一组堆序树支持合并和插入最坏 O(log N)插入摊还 O(1)。手册第 6 章和第 12 章把这些结构排在一起读的时候先抓住“堆序”这个不变量再看每种结构用什么手段恢复它。5. 避坑与排查习题解答里最容易翻车的五个细节5.1 复杂度推导类踩坑上界、紧界与定义域现象看到 O(N log N) 就认为一定比 O(N²) 快忽略小 N 和常数因子。原因大 O 只描述上界且渐近性质在 N 趋于无穷时才成立Θ 才是紧界。解决先明确问题规模范围保留低阶项和常数小 N 用实测或插入排序兜底证明同阶时用极限定义不要只看符号。手册第 2 章的增长率排序和真假判断题练的就是这个边界感。现象把 N log N 和 N log(N²) 当成不同增长率。原因log(N²)2logN只差常数因子渐近上同阶。解决比较前先化简对数幂、底数变化都只影响常数手册明确说两者同速不要被括号里的平方骗了。5.2 实现细节类踩坑下标、哨兵与边界现象二分查找写成 mid(lowhigh)/2在 low1、high2 时 mid1递归调用不前进死循环。原因下取整让 mid 可能等于 low区间更新又写成 lowmid 而不是 mid1。解决midlow(high-low)/2缩小范围时用 mid1 或 mid-1循环不变量写清楚。手册第 2 章专门有一道题点这个答案很短但坑很真实。现象循环队列判满用 frontrear结果队空队满不分。原因front 和 rear 的语义没有约定循环数组的“满”和“空”在模运算下可能同余。解决维护 size 计数或者牺牲一个槽判满 (rear1)%capfront判空 frontrear入队出队后更新顺序保持一致。手册第 3 章的抽象实现里这种边界反复出现读答案时别只看主循环。5.3 图与并查集类踩坑前提条件被忽略现象非负权单源最短路算法遇到负权边结果错得离谱。原因贪心前提是“已确定的最短距离不会再被更短路径更新”负权边破坏了这个单调性。解决先检查边权范围负权图改用可处理负边的松弛算法或者先做势能变换读手册第 9 章的答案时先看它声明了什么前提。现象开放定址哈希表删除元素时直接置空后续查找断链。原因置空截断了探测序列后面的元素明明存在却找不到。解决用墓碑标记删除查找遇到墓碑继续探测插入可以复用墓碑负载因子计算要把墓碑算进去墓碑过多时触发再散列。这个坑在手册第 5 章的冲突解决题里埋得很深自己写一遍删除操作就会记住。6. 设计取舍从答案手册反推教材作者省略了什么这份解答手册在序言里说得很清楚省略了可能的编程作业以及章节末尾引用所指的题目答案的完整度不一细节留给读者程序是伪 C不是完全正确的代码。这些“不完整”不是缺陷而是教学取舍。编程作业要自己设计测试、处理输入输出、调边界答案给不了引用题指向外部文献答案给了反而截断探索伪 C 省掉头文件和错误处理把注意力压在数据结构和算法本身。读手册时如果拿它当“标准代码库”一定会踩坑拿它当“推导过程记录”价值才出来。我后来养成了一个习惯每看一道答案前先自己写三行——前提是什么、复杂度紧不紧、反例可能在哪。比如 PrintLots 的前提是 P 升序且链表只能顺序访问二叉堆 buildHeap 的紧界是 O(N) 而不是 O(N log N)哈希删除的反例是探测序列被截断。三行写完再对照手册如果答案和我的前提冲突优先检查前提而不是怀疑答案。这个习惯比背结论有用因为它逼着我把“为什么能 work”说清楚。这份 PDF 按章分节第 2 章的增长率排序和第 8 章的并查集摊还分析最适合先推一遍第 3 章的 PrintLots 适合手写代码验证边界。从那以后我每次读这类解答手册都强制自己先关掉答案把例题推一遍再打开对照错的地方才是真正学到的地方。希望帮到你。本文还有配套的精品资源点击获取