文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本文基于 CLRSIntroduction to Algorithms第三版习题解答仓库中的 docs/Chap02/2.1.md完整梳理第 2.1 节四道习题2.1-1 至 2.1-4的解答对数组 $\langle 31, 41, 59, 26, 41, 58 \rangle$ 逐步图解INSERTION-SORT的执行过程、改写为降序排序的伪代码修改、用循环不变量loop invariant严格证明线性搜索的正确性以及两个 $n$ 位二进制整数相加的形式化问题定义与伪代码。读完本篇你将掌握用执行轨迹验证排序算法用循环不变量三要素证明算法正确性这两项算法分析与证明的核心技能。背景标准版 INSERTION-SORT 伪代码第 2.1 节习题均以教材中的INSERTION-SORT过程为讨论对象。为与原文中提到的第 5 行的测试第 6 行的移动第 8 行的放置对应先给出带行号的伪代码这是 CLRS 教材 Section 2.1 的标准形式数组下标从 1 开始INSERTION-SORT(A) for j 2 to A.length key A[j] i j - 1 while i 0 and A[i] key A[i 1] A[i] i i - 1 A[i 1] key该算法维护的核心循环不变量是每次 for 循环迭代开始时子数组 $A[1..j-1]$ 恰好是原始 $A[1..j-1]$ 中元素的非递减排序版本。每一轮从 $A[j]$ 取出key在它左边已排序的前缀中通过while循环不断右移比它大的元素最终把key放到正确位置——这正是下文 2.1-1 图解要展示的过程。本仓库是面向 CLRS 习题的开源解答合集采用 Markdown KaTeX 编写、由 MkDocsMaterial for MkDocs 主题构建为静态网站参见 mkdocs.yml 的导航中2.1 Insertion sort: Chap02/2.1.md一项以及 README.md 对构建方式的说明。下面按原题顺序展开解答并对关键结论补充推导与复杂度依据。2.1-1 图解 INSERTION-SORT 对 $\langle 31, 41, 59, 26, 41, 58 \rangle$ 的执行题目以教材 Figure 2.2 为模型图解INSERTION-SORT在数组 $A \langle 31, 41, 59, 26, 41, 58 \rangle$ 上的执行过程。下图来自仓库中的 docs/img/2.1-1-1.png矩框上方是下标、框内是存储值图中各子图的读法与解答文档一致(a)–(e) 对应第 2 行 for 循环的 5 次迭代即 $j 2, 3, 4, 5, 6$每轮中黑色矩形是取自 $A[i]$即 $A[j]$的key它与左侧灰色阴影矩形中的值进行第 5 行的比较测试虚线箭头表示第 6 行把元素值向右移动一格实线箭头表示第 8 行key最终落到的位置(f)是最终排序完成的数组。逐轮看(a) 取 $A[2] 41$ 为 key左侧仅 $31$无需移动(b) 取 $A[3] 59$仍无需移动(c) 取 $A[4] 26$while循环连续 3 次比较、把 $59, 41, 31$ 依次右移一格key落入 $A[1]$(d) 取第二个 $41$$A[5]$只把 $A[4]$ 处的 $59$ 右移一格(e) 取 $A[6] 58$把 $A[5]$ 处的 $59$ 右移一格(f) 得到 $\langle 26, 31, 41, 41, 58, 59 \rangle$。原文档同时列出了数组 $A$ 在遍历过程中的逐轮变化这里整理为带轮次标注的表格下标均从 1 计迭代key迭代结束后数组状态初始—$A \langle 31, 41, 59, 26, 41, 58 \rangle$$j 2$$41$$A \langle 31, 41, 59, 26, 41, 58 \rangle$不变$j 3$$59$$A \langle 31, 41, 59, 26, 41, 58 \rangle$不变$j 4$$26$$A \langle 26, 31, 41, 59, 41, 58 \rangle$$j 5$$41$$A \langle 26, 31, 41, 41, 59, 58 \rangle$$j 6$$58$$A \langle 26, 31, 41, 41, 58, 59 \rangle$从这份轨迹可以直观看出插入排序的运行时间特征第 $j$ 轮的工作量取决于while循环第 5–7 行右移了多少个元素。输入已经有序时每轮只做一次失败比较总时间为 $\Theta(n)$输入逆序时每轮右移 $j-1$ 个元素总时间为 $\Theta(n^2)$。仓库中 docs/Chap02/Problems/2-4.md 进一步给出了一个漂亮的刻画while循环总共执行的次数恰好等于输入数组的逆序对inversion总数因此插入排序的运行时间与逆序数成正比——本题中 $j4$ 时key26右移了 3 个元素正对应它新引入的 3 个逆序对。2.1-2 改写为按非递增降序排序题目把INSERTION-SORT改写为按非递增序nonincreasing排序。标准版之所以产生升序是因为第 5 行while的条件A[i] key让比 key 大的元素不断右移。要得到降序只需把比较方向反过来——让比 key 小的元素右移INSERTION-SORT(A) for j 2 to A.length key A[j] i j - 1 while i 0 and A[i] key A[i 1] A[i] i i - 1 A[i 1] key唯一改动就是比较运算符由变为。其余结构取 key、回退扫描、右移、落位完全不变因此循环不变量相应改为每次迭代开始时 $A[1..j-1]$ 是原始前缀的非递增排序版本。用同一输入验证对 $A \langle 31, 41, 59, 26, 41, 58 \rangle$ 执行降序版最终得到 $\langle 59, 58, 41, 41, 31, 26 \rangle$。另外值得注意的一个细节条件取严格小于而非 $\le$意味着遇到与key相等的元素时while循环立即停止、不再继续左移因此相同值的元素保持其在输入中的相对顺序——这个降序版本对相等元素是稳定的与升序版本使用严格大于的设计意图一致。2.1-3 线性搜索的伪代码与基于循环不变量的正确性证明题目搜索问题输入$n$ 个数的序列 $A \langle a_1, a_2, \ldots, a_n \rangle$ 和一个值 $v$输出满足 $v A[i]$ 的下标 $i$若 $v$ 不在 $A$ 中则返回特殊值NIL。要求写出扫描序列寻找 $v$ 的**线性搜索linear search**伪代码并用循环不变量证明其正确性且证明须完整覆盖循环不变量的三个必要性质初始化、保持、终止。伪代码解答LINEAR-SEARCH(A, v) for i 1 to A.length if A[i] v return i return NIL循环不变量在 for 循环每次迭代开始时子数组 $A[1..i-1]$ 中的元素都与 $v$ 不相等。下面按三要素展开这是原文档的证明主体完整保留其论证链条初始化Initialization第一次迭代之前 $i 1$子数组 $A[1..0]$ 是空数组所有元素都不等于 $v$这一陈述平凡成立故不变量初始为真。保持Maintenance每次迭代把 $v$ 与 $A[i]$ 比较。若相等立即return i——由于 $A[i]$ 之前的位置在不变量下已知不含 $v$返回的下标就是正确答案若不等本轮结束后已知 $A[1..i]$ 不含 $v$$i$ 自增 1 后新迭代开始时 $A[1..i-1]$即旧的 $A[1..i]$仍满足不变量故不变量得以保持到下一轮。终止Termination循环在 $i A.length n$ 时终止。由于 $i$ 每次恰好加 1终止时必有 $i n 1$。把 $n1$ 代入不变量的表述得到子数组 $A[1..n]$即整个数组中所有元素都不等于 $v$此时执行return NIL是正确的。综上算法正确。这个证明展示了循环不变量方法的完整范式不变量描述循环之前已经完成了什么终止时把不变量代入终态即得结论。它与INSERTION-SORT的不变量前缀有序同属一种技术区别只在于断言的内容从有序换成了不含目标值。关于复杂度仓库中 docs/Chap02/2.2.md 的习题 2.2-3 给出了配套分析若目标等概率地是数组中任意元素平均需要检查 $n/2$ 个元素最坏需要检查全部 $n$ 个两者都是 $\Theta(n)$。此外 docs/Chap02/2.3.md 的习题 2.3-5 指出当序列已排序时可改用二分搜索每次比较砍掉一半搜索空间最坏时间为 $\Theta(\lg n)$——这与本题的线性搜索形成对照。2.1-4 两个 n 位二进制整数相加形式化问题与伪代码题目考虑把两个 $n$ 位二进制整数相加的问题两个整数分别存放在 $n$ 元素数组 $A$ 和 $B$ 中和以二进制形式存入 $(n1)$ 元素数组 $C$。要求形式化地陈述问题并写出伪代码。形式化陈述原文档的解答注意其约定的位序输入布尔数组 $A \langle a_1, a_2, \ldots, a_n \rangle$ 与 $B \langle b_1, b_2, \ldots, b_n \rangle$各表示一个以二进制存储的整数最低有效位在前least-significant digit first即 $a_1, b_1$ 是最低位输出数组 $C \langle c_1, c_2, \ldots, c_{n1} \rangle$使得 $C A B$其中 $A$、$B$、$C$ 是三个数组各自表示的整数。伪代码模拟手工竖式加法从低位到高位逐位相加并传递进位ADD-BINARY(A, B) carry 0 for i 1 to A.length sum A[i] B[i] carry C[i] sum % 2 // remainder carry sum / 2 // quotient C[A.length 1] carry return C正确性与复杂度可以从实现层面进一步确认由于 $a_i, b_i \in {0, 1}$ 且进位carry取值只能是 $0$ 或 $1$因为 $sum \le 3$sum / 2向下取整后最多为 $1$所以carry在循环中始终被维持在 ${0, 1}$ 中与十进制竖式加法中进位是单个数字完全同构循环体只做常数次算术操作总时间 $\Theta(n)$。空间上两个 $n$ 位数的和最大为 $2^{n} - 1 2^{n} - 1 2^{n1} - 2$恰好需要 $n1$ 位表示这正是输出数组长度为 $n1$ 的原因——最高位 $C[n1]$ 只可能是最终的进位值 $0$ 或 $1$。若输入约定改为最高位在前则需把循环方向改为从下标 $n$ 递减到 $1$其余逻辑不变。小结与延伸阅读本篇覆盖了 docs/Chap02/2.1.md 的四道习题四个主题恰好串起算法学习的基本功2.1-1以具体数组逐步图解插入排序理解取 key → 比较右移 → 落位的执行模型2.1-2通过翻转单个比较方向得到降序版本体会伪代码中比较条件与循环不变量的对应关系2.1-3用初始化/保持/终止三要素以循环不变量严格证明线性搜索正确性2.1-4把二进制加法形式化为数组运算用单个进位变量在线性时间完成。想继续深入时建议按以下仓库内文档延伸docs/Chap02/2.2.md第 2.2 节习题——算法分析$\Theta$ 记号、选择排序的循环不变量与运行时间、线性搜索的平均/最坏情况分析docs/Chap02/2.3.md第 2.3 节习题——归并排序图解、二分搜索以及习题 2.3-6 的结论把插入排序的while扫描换成二分搜索并不能把最坏时间降到 $\Theta(n\lg n)$因为右移元素本身仍要 $\Theta(j)$ 时间搜索只是次要开销docs/Chap02/Problems/2-1.md问题 2-1——在归并排序的小子表上改用插入排序的混合策略及其阈值 $k \Theta(\lg n)$ 的推导docs/Chap02/Problems/2-4.md问题 2-4——逆序对与插入排序运行时间的精确关系以及用改造版归并排序在 $\Theta(n\lg n)$ 内统计逆序对数。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐CLRS 第 2.1 章习题精解插入排序、线性查找与 n 位二进制加法含 Python 实现CLRS 第 2.1 章习题精解插入排序、线性查找与 n 位二进制加法含 Python 实现 本篇技术指南围绕《算法导论》Introduction to文档教程示例工程magvit2-pytorch从零训练VideoTokenizer新手也能上手的完整实战教程magvit2 pytorch从零训练VideoTokenizer新手也能上手的完整实战教程 想要从零训练一个属于自己的 VideoTokenizer视频分CLRS 第二章 2.2 习题详解Θ 记号、选择排序、线性搜索与最好情况优化CLRS 第二章 2.2 习题详解Θ 记号、选择排序、线性搜索与最好情况优化 导读 本篇基于《算法导论》CLRS习题解答仓库中的 2.2.md https文档教程示例工程上一篇3分钟解决OpenDrop传输卡顿从网卡配置到代码优化全指南下一篇2025最新awesome-emacs项目解析社区精选Emacs包与工具大全创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考