此笔记位置已失效,请从目录继续阅读。
全书导读
本书是以图解和代码建立算法直觉的入门教程,按复杂度分析、数据结构和算法策略三条线组织。当前输入是靳宇栋《Hello 算法》的Go语言版,正文标明Release1.0.0、2024-02-09;OPF的2016年转换元数据不作为本版日期,未找到可靠出版社或ISBN,未补造。
8项连续正文、71个生成单元及316张图片均已实际读取并处理,覆盖序言、前言、十五章和附录。EPUB由其他版式转换,章节跨文件,故以真实spine位置记录来源,卡片仍注明实际原书章号。部分公式变量在EPUB HTML原已缺失,不能把推测补全冒充摘录;当前解释采用实际可读文字、代码和已读图支持的机制,并就近说明不能照抄的排版、边界和数值问题。
信息浓度高,复杂度、不变量和策略取舍具有长期解释力。具体性能依输入、计算模型、数据布局与版本,原书Java类型表、旧Go map桶、语言工具安装及硬件价格属于局部背景。阅读目标是能够解释为何正确、何时失效及成本来自哪里,而不只是记住题解或增长阶。
全书主线
起点是建立知识地图。生活中的查字典、扑克整理和找零,分别引出利用有序信息、维持已排前缀和局部选择。复杂度分析再给出比较资源的共同语言:先定义输入规模与操作模型,区分增长界、输入情形和同时存活空间,才能避免把大O当秒数或把递归节点总数当栈深度。
数据结构把逻辑关系落实到存储布局。数组用固定槽位支持直接访问,链表用链接支持局部更新,动态数组以容量管理换取可增长序列。栈队列通过限制端点形成LIFO/FIFO,哈希靠分桶和冲突机制定位,树用递归关系组织层级,搜索树再加大小范围,AVL再约束高度,堆用完全形状和局部次序维护极值。图则容纳一般网络关系,表示与方向共同决定遍历成本和可达范围。
搜索利用已知结构排除候选,排序为后续操作建立次序。二分须保持一致区间,哈希两数和须先查后存;排序又要权衡稳定、辅助空间、输入适应性与值域。快排的划分、归并的合并、堆排序的有效长度以及计数/基数的范围信息,各有不同正确性条件,不能只以nlogn或线性命名判断。
最后四类策略组织更复杂的决策。分治证明如何分解并合成;回溯探索候选并恢复状态,以有证据剪枝;动态规划合并重复子问题,用充分状态和依赖顺序保存答案;贪心固定局部选择,需证明不丢全部最优解。附录提供运行环境与开源修订参考,术语表帮助回找,不替代对具体机制的理解。
S001 前置说明、初识算法与复杂度分析
先知道自己在学什么。 本书定位为算法入门导航,用图解和代码把题目背后的数据组织及操作方法连接起来。它承认入门框架不能直接保证求职成果,学习者仍要通过练习检验理解。当前版正文标明2024-02-09 Release1.0.0 Go语言版,序言后的目录只用于定位,不作为已经讲解算法的证据。
目录给出路线,不提供论证。 搜索和排序解决基础处理任务,分治、回溯、动态规划及贪心则在后文分别说明如何组织选择和子问题。本单元只保留原书章节次序,具体机制在实际正文处处理。
地图由成本、组织与步骤组成。 复杂度分析帮助比较时间和空间,数据结构决定数据以何种关系保存,算法解释如何利用这些关系解决问题。三者需要结合,不能只记名词。原书要求至少具备一门语言的基础编程能力,图示和多语言代码用于降低理解成本;贡献者名单与致谢不承载新的算法结论。
图与代码承担不同证据角色。 图显示当前状态和下一步的关系,代码固定判断与更新的先后次序。把二者逐步对应,才能把模糊直觉变成能解释的过程。本书跨语言说明有时沿用Python术语,Go版应以实际代码区分;部分注释为排版而简化,不能不经核对就当目标语言的完整程序。
练习用于检验地图,类比用于建立直觉。 入门先认识机制,题目让这些机制接受具体输入约束,再以专题和多解法重组理解。字典折半利用有序关系排除候选;扑克插入保持前缀有序并逐步扩张。类比帮助入门,具体输入前提、边界和效率仍须到后面的真实算法中说明。
先保正确,再讨论成本。 问题给出合法输入和期望输出,数据结构安排操作所需关系,算法规定状态如何变化。找零的局部选择可以得到可行结果,但最优性要另外证明。比较效率时,测试反映特定环境,复杂度在统一模型下比较增长;循环则把这种增长落实为重复次数。嵌套并不自动等于次数相乘,必须读实际边界和循环体成本;递归将用另一种控制方式处理相同任务。
递归把待完成工作留给后续返回。 基本情况让收缩停止,每个未返回层保留继续位置,所以调用树的全部节点决定总工作,而同一时刻的深度决定栈需求。尾位置把后续合并移到参数中,却不保证Go会复用栈帧。显式栈可以重现进入与返回次序,但若仍保存同样多状态,空间不会凭改成循环就消失。选择表达方式要同时考虑状态、边界和可读性。
增长界来自计数模型。 先明确输入规模和基本操作成本,才能从执行次数得到资源函数。常数阶可能做很多固定工作,因此不保证小输入时快;大O给出最终上界,也不自动等于精确增长级别。顺序段相加,嵌套按实际边界累计,再在适用条件下忽略系数和低阶项。本EPUB此处公式原已缺失,解释以实际文字、代码和图为依据,未伪造完整公式摘录。
不要从代码外形猜阶数。 单次扫描和两层循环要看实际执行次数,冒泡内层随外层缩短,仍可由求和得到平方级比较。规模翻倍与规模折半分别产生快速增长和少量轮次;两半都继续递归则要计算整层工作,不能只数一条路径。归并式“每层线性、对数层”的结构解释线性对数增长,具体排序的最坏与平均情形还需另行区分。
先说明比较的是哪种输入、哪种资源。 同规模输入的位置不同,线性查找可立即命中或遍历到底;平均值还需要分布假设,不能把最好最坏与O、Ω记号绑死。全排列即使高效生成,也必须为所有方案付出输出成本。空间则按声明口径计算同时存活峰值,递归深度和结果保留都可能主导,而累计分配量与物理回收时机又是另一问题。
进一步阅读:先建知识地图再练题;用图与执行步骤互相校验;从练习回到知识体系;有序范围可以反复折半;把新元素插入有序部分;局部最优先得到可行方案;算法先明确输入输出与终止;数据组织要权衡访问与维护;复杂度比较增长而非秒数;循环重复直到条件不再成立;递归需要收缩与基本情况;递归深度决定未返回上下文;尾位置不保证尾调用优化;调用树展示重复子问题;显式栈可以模拟递归;基本操作计数需要成本模型;大O给上界而非精确阶;顺序相加嵌套按边界求和;增长阶由规模变化方式决定;分层总工作还要乘层数;全排列的输出数量本身很大;输入情形与渐近记号分开;空间分析关注同时存活峰值。
S002 复杂度分析收尾、数据结构、数组与链表、栈开篇
空间取决于同时保留什么。 同样深度的递归,如果每层只留常数上下文,和每层都留未使用完的大数组,峰值可能不同;实际编译器对不再使用对象的存活判定也会影响测量。完整树保存全部节点与只走一条递归路径的栈更不能混算。额外保存可复用信息能够节省后续计算,但是否值得取决于预算与工作负载。
把关系、布局和内容拆开看。 同一线性抽象可以放在连续数组中,也可以沿节点链接保存;两种实现改变访问与更新成本,却不改变抽象目标。元素的整数、浮点或布尔类型又是另一层:它决定可表示范围,结构决定相互组织。内存图仅为程序地址的简化示意,不能代替虚拟页映射或跨进程共享的真实规则。方法则为某种类型组织操作,Go通过显式接收者声明这个目标。
位模式必须连同解释规则。 同一串位可被解释为无符号值、补码整数或浮点字段,含义并不由位串独立决定。补码解决定宽有符号加法与双零问题;浮点通过指数扩大范围,同时牺牲可表示值的密度,并保留特殊模式。字符又要先确定编号集合,再选择字节编码,不能把文本与数字存储混为一种固定宽度。
文本操作必须先选单位。 编号、字节、UTF-16代码单元、Unicode码点和用户看到的字素不是同一个对象。UTF-8保留ASCII兼容并用前缀组织变长序列,UTF-16也会用代理对,因此按单元随机访问不等于按字符随机访问。选择编码要看交换约定、空间和现有工具,不能仅凭“Unicode”三个字推断实际内存布局。
连续的是槽位,不一定是对象。 数组以固定大小槽位提供直接索引,槽位可以装数字,也可以装指向分散对象的引用。中间插入需搬移并保证容量,不能把教学示例覆盖末元素当成业务正确行为。Go例中常以切片提供操作便利,数组类型长度与切片可增长描述仍要分开;语言内部字符串布局也不替代外部编码约定。
访问方便与改动方便是不同优势。 已知数组下标可以直接取槽,按值查找仍需逐项比较;中间插删靠搬移,扩容又可能复制全部有效数据。链表改为节点保存后继地址,从头沿链接取得次序,省去了整体连续要求,但增加了指针和间接访问。有效长度、末尾旧引用和别名去向都属于容器合同,不能由示例只处理整数就省略。
比较成本必须统一定位前提。 已知前驱后,插入或删除只改有限链接;若必须先从头找到位置,查找仍是线性。删除也只取消这条链的成员关系,外部引用可继续保留节点及其后继。双向和环形分别增加反向遍历或轮转能力,但需要额外状态与终止条件。动态数组则保留连续槽位,并以数量、容量区分“已使用”和“已预留”。
容量增长只解决一种成本。 满了扩容、未满直接追加,经过多次操作可以摊薄搬迁;中间插删仍要移动后缀。容量与数量的维护必须和边界检查同步,调用者取得的切片也可能共享底层,不能把它当隔离快照。原书简易实现意在展示结构,不具备完整通用容器的清尾、所有入口和错误合同;接下来的缓存分析将解释为什么相同大O仍有实际速度差异。
大O之外还要看数据移动。 存储层次用小而快的区域服务常见访问,连续扫描让一个缓存行内的多个槽都有用,分散指针追踪则可能反复等待。但模式、工作集与分配器会改变实际结果,原版硬件表也不能当今天测量。数组在堆或栈上仍有连续槽位;Go数组类型长度由类型规则决定,不能从堆分配推出长度可在运行时任意改变。
抽象由可观察规则定义。 栈不要求一种固定容器,只要求从同一逻辑顶部进入和离开。切片尾部和链表头部或尾部都能实现,空栈结果必须另有合同。引用槽位的连续性也不代表对象连续或隔离,Python列表问答尤其要区分重复不可变值与重复可变内层对象;链表删除是否影响后继回收则取决于外部仍能到达什么。
同一栈合同可以有不同资源取舍。 链表栈靠节点增删并使用明确端点,数组栈靠尾部追加与缩短。二者都需先判断空,再读取顶部;若空状态与合法值可能重合,就要增加存在标志。尾部追加的均摊成本与单次扩容不同,不能因为操作表写常数就忽略底层容量变化。
进一步阅读:数据组织要权衡访问与维护;空间分析关注同时存活峰值;时间与空间可以互相换取;方法将操作关联到对象;逻辑关系与存储布局分开;地址连续不等于物理连续;内容类型与组织方式正交;补码统一定宽有符号加法;浮点范围用精度换取;浮点特殊编码不走普通公式;字符集编号与编码分开;Unicode码点不决定字节数;UTF8用前缀标记序列边界;UTF16按代码单元保存文本;数组索引换算固定步长地址;数组插入先移动后写入;数组删除要维护有效长度;线性查找逐项验证候选;扩容需要保留已有数据;链表用节点指针连接次序;链表插入先接后继再接前驱;删除链接不等于对象回收;链式访问需要沿路径前进;多加链接换取遍历能力;动态数组分开数量与容量;倍增扩容摊薄追加成本;动态数组中间更新仍要搬移;存储层次平衡速度容量成本;局部性让相邻访问更有利;共享引用不等于共享槽位;栈限制同一端进入与离开。
原书依据 · 37 处
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
- · 查看原书依据
S003 栈与队列、哈希表、树与遍历开篇
同一个容器规则不自动带来安全实现。 栈的peek即使处理空状态,pop仍需避免继续缩短空切片;返回nil也不能替代有效数量检查。队列改为尾进头出,把等待顺序固定下来,但并发处理后的完成顺序另由工作协议决定。链表端点操作避免整体搬移,连续数组则需要另一个办法复用已释放的前部槽位。
索引回绕代替整体搬移。 环形数组让逻辑次序与物理槽位起点分开:front指向第一项,size说明有效项数,模运算完成跨尾回头。双端队列进一步允许头入和尾出,链表需双向连接,数组需对称更新索引。所有操作仍要保持数量范围;容量满或队列空是业务结果,不能只打印或返回nil后继续破坏内部状态。
自由度服务于额外合同。 有限撤销仍按最近操作回退,却要在预算满时从另一端丢弃最早记录,这正是deque比普通栈多出的能力。数组实现通过front前后移动和尾位置计算支持同一抽象,size必须在每次成功操作后准确更新。原书空pop继续减计数的问题不能沿用;本例toSlice复制有效序列,则与直接返回共享底层的列表方法不同。
从顺序取出转向按键定位。 两栈用元素转移表示撤销方向,新的操作清掉旧重做分支。哈希表则把键变成桶索引,用额外组织换取少量候选检查;这一过程仍须识别键并处理冲突。原书简表只展示算索引,不能因例子里学号恰好不碰撞就认为任意键都可可靠存取。Go map操作是使用入口,实际实现不由这段教学表决定。
哈希只缩小范围,键相等才确认目标。 有限桶不能避免碰撞,可靠实现要保留同桶候选并逐个比较。负载因子衡量密度,不能独自说明分布是否健康;即使桶更多,相同哈希仍可能相遇。切片桶减少了教学代码复杂度,却保留候选过长时线性退化的边界。查找缺失与合法空值同样需要不同结果表达。
探测路径也是需要维护的数据。 扩容改变索引,必须重新放置有效键。开放寻址则让一个桶的候选沿路径分散,查询必须沿原规则继续,因此“未使用空槽”和“删除槽”不能混淆。墓碑保留这条路径,但插入还要查后续是否已有同键,不能为了复用一个空位破坏映射唯一性。正文提出的查询回移优化没有在Go例完整实现。
机制成立还需要状态和输入域正确。 空槽和墓碑不能与合法键值重合,插入要维护键唯一性,删除要准确更新数量。换探测步长并不自动保证访问全部桶,语言实现也有版本边界,原书Go八槽与溢出桶只能作旧模型。哈希表分布与密码学抗碰撞又是不同目标:均匀只是性能条件之一,不能用来证明认证或密码存储安全。
哈希设计必须带着输入和威胁前提。 混合次序、取模和输入周期共同决定桶分布,单凭大质数不能保证均匀。标准安全哈希的命名也不能替代对应用要求的分析,原书SHA3必然更快、旧推出年份等表述不作为本次结论。映射键则要维护相等与散列的一致身份:按内容变化和按指针身份是不同行为,Go可比较键规则与Python对象hash合同不能互换。
树先规定关系,再规定形状。 左右子关系递归组织后代,根、叶、度、高度和深度用于描述位置。完全、完美、完满各约束不同,形状会影响数组表示和后续算法的路径长度。原书这里以左右高度差不超过1说明平衡,这是AVL式条件,不能当所有平衡树的唯一通用定义;简单改链接也不保证搜索次序等额外性质。
容器决定待访问节点的顺序。 队列保留较早发现节点,形成逐层推进;递归栈先完成当前子树,再回到父节点处理另一侧。前中后序只改变根被记录的时点,递归关系相同。高度影响栈与路径,宽度影响队列,全部输出则另占线性空间;没有声明搜索次序时,树形漂亮也不意味着按值查询必然只走一条路。
进一步阅读:栈限制同一端进入与离开;队列在两端维持先进先出;环形队列用索引复用空间;双端队列开放两端操作;有限撤销需要淘汰最旧记录;双栈分离撤销与反撤销;哈希映射先算桶再比较键;有限桶必需处理冲突;负载因子只是密度指标;同桶容器保留全部候选;哈希扩容需要重新分桶;开放寻址保持一致探测序列;墓碑保留被删除后的搜索路径;空槽状态不能占用合法值;哈希分布与安全性质不同;取模与混合需要匹配输入;作为键需要稳定相等与散列;二叉树用两条子关系递归组织;高度深度必须统一计数口径;完全完美与完满约束不同;树的高度影响路径成本;队列保证树按层推进;深度遍历按访问时点分三序。
S004 树的遍历、搜索树、AVL、堆与图开篇
链接可以显式保存,也可以由位置推算。 完全树按位置装入数组,父子索引便能替代指针;一般树若省掉中间空位,同一层序值序列可能对应不同结构,不能再靠原公式找孩子。搜索树则在普通二叉关系上增加全子树大小范围约束,才允许比较一次后舍去一侧。位置紧凑与查询有序是不同性质,不能互相替代。
所有更新都要维护全路径约束。 新键沿比较路径进入空位,删除则按孩子数选择断开、提升或用合法次序边界替换。只要每个子树仍处在祖先范围内,中序就能输出全部升序键。这里维持的是有序性,还没保证平衡;不能从“比较后走一侧”直接推导每次操作都是对数时间。
平衡是持续维护的结果。 普通搜索树按有序插入仍可能长成链,AVL额外限制局部高度差,并在更新后检查。旋转不改变中序次序,却改变哪些节点靠近子树根;中间子树必须转交到正确一侧,高度也按先下后上的新关系更新。这样保留查询规则的同时控制路径长度,代价是每次更新需维护更多状态。
局部修复必须接回整体。 同向高链用单旋,折线先转孩子再转根;每一层返回可能不同的子树根,上层链接和整树根都要接住。插入与删除都可能影响路径高度,因此更新、重新判定、旋转的过程应沿回溯推进。原书红黑树应用比较属于策略取舍提示,不作为所有负载下更快的实测结论;树章小结由前面的结构、遍历、次序和平衡四层共同承接。
局部规则可以提供专门能力。 搜索树靠全子树范围支持有序查找,堆只维护父子优先关系,便能快速拿到一个极值,却不保证其他位置排序。优先队列是使用方看到的抽象,数组堆是实现之一。Go接口又把末尾存取回调与真正恢复堆序分开,说明方法职责不能仅凭Push或Pop名字猜测。
修复范围来自被破坏的位置。 末尾插入只会影响向上的父子关系,根被末项替换则只需向下;每一步都要保留完全形状。构造整个堆时倒序处理非叶,使孩子先合法,再让父节点下沉。大量靠近底层的短修复让总成本优于把每次都按最长路径估算,具体证明在后续按层加权展开。
只保留任务真正需要的信息。 TopK不要求排好全部输入,小顶堆只维护当前候选集合及其最弱一项,新值能改善集合才替换。结果仍是堆,若要有序输出须再处理;k范围也不能省略。图则从层级结构扩展到一般关系,需要先说明方向和权重,再选择表示与算法。堆的名字与动态内存区域同名,不代表两者共享一种数据结构含义。
表示选择决定直接操作的成本。 矩阵用平方槽位换直接边访问,邻接表只保存存在关系而可能多花查找邻居的工作。无向更新要保持对称,零权与无边要区分;加一顶点不只是改一个边槽,连续行扩展也可能搬移。方向决定可达含义,权重决定路径目标,自环则是模型约定,不能从简单示例推广所有图。
进一步阅读:共享引用不等于共享槽位;树的高度影响路径成本;深度遍历按访问时点分三序;树的数组位置要保留空洞;搜索树按全子树范围排除;搜索树插入沿空位置接入;删除搜索树要保持次序;搜索树中序遍历得到升序;AVL用局部高度差约束形状;旋转保持中序并改变高度;折线失衡要先转孩子;树更新返回新的子树根;公开查询隐藏结构维护;堆用局部次序维护极值;堆接口回调只移动存储端点;入堆从末位向上修复;出堆用末项接替后向下修复;自下而上建堆是线性工作;固定小顶堆保留最大K项;图用边表达自由连接关系;图的连通要先说明方向;矩阵与邻接表保留不同信息。
S005 图的实现与遍历、查找、排序开篇
关系更新必须保持两侧一致。 无向矩阵对应两个对称槽,邻接表对应两个邻居集合;删除顶点还会影响所有进入它的关系。先验证输入再更新,比仅创建一个未返回的错误值更重要。矩阵扩大连续行可能搬移,邻接表键则依实际类型的相等合同;不能把抽象表格的操作次数直接当任意Go实现最坏耗时。
发现与处理是两个时点。 图存在多条路径,若等到出队才标记,一个顶点可能在等待期间被反复加入。入队即记录已发现,使队列保留有限待处理集合。单次遍历的覆盖范围则由起点和方向决定,图不连通时需要从未访问顶点继续启动;矩阵和邻接表扫描邻居的代价也不同。
排除必须有不变量支持。 图遍历借visited避免重复,二分则借有序关系证明某段不可能包含目标。前者从一个起点只覆盖可达部分,后者每轮维护一个候选区间;二者都不能靠“看起来少走了路”证明正确。闭区间与半开区间各有一致的初始化和更新,必须整套保持,不能拿不同版本的边界拼接。
位置与是否存在分开返回。 下界即使找不到相等值,也有合法插入位置;遇到相等仍左缩,才能保留最早位置。调用者用位置检查存在,而不让查找器为了某个分支返回含混控制信号。是否值得排序或建立索引也取决于未来查询与更新总量,单次算法复杂度不是完整系统成本。
优化要保留题目合同。 上下界回答整段相等值的位置,不能用可能溢出的target+1或失真的浮点扰动偷换目标。两数和则利用已见元素的补数映射,把每轮搜索压缩,但必须先查再存以保证两个不同索引。选择查找方案还要把建表、维护、范围查询和内存预算一起计算,单个操作的期望复杂度不足以替代总成本。
排序不只有快慢一个维度。 相等记录是否保留顺序、是否使用辅助数组、递归栈有多深、对已近有序输入是否少做工作,都会改变选择。稳定性可承接已有次要键次序,组合比较器也能直接表达多级排序。选择排序则用扫描最小项扩张前缀,工作量稳定却可能跨越同键元素;计数应从真实循环边界求和,不能只背表中公式。
已有次序可以成为节省工作的证据。 冒泡完整一轮无交换,说明当前区间没有相邻逆序,可以结束;插入排序只移动必须越过的较大前缀元素,近有序时自然少做工作。稳定性则来自相等时不改变相对次序的具体条件,不能仅从“相邻”或“插入”名字推断。小输入常数优势是选择依据之一,仍需实际实现和负载确认。
分治质量决定增长。 快排每次把一个基准放定,再处理两侧;如果一侧持续为空,问题并没有有效分半。三数取中改善常见形状,仍不能承诺所有输入均衡。比较算法还要看交换、访问模式和栈,不能用名字“快”或一组常数估计替代工作量与前提。后续空间优化会控制栈深度,但不会自动消除坏划分的时间退化。
不同改写优化不同资源。 快排只把短边压栈,限制新增上下文,却仍可能做平方比较。归并先排好两半,再利用有序性线性合并,以临时数组换稳定、规则的工作;峰值空间要把数组和栈都算清。链表可重接已有节点,若采用自底向上迭代还可省递归,但这是带所有权前提的路线,原书并未提供完整可运行实现。
进一步阅读:把新元素插入有序部分;矩阵与邻接表保留不同信息;图更新同时维护顶点和边;图BFS在入队时标记访问;图遍历只覆盖起点可达部分;图DFS用访问集阻止回环;二分边界约定必须成套;预处理成本要按查询摊算;下界查找命中后继续向左;上界位置帮助确定最右匹配;两数和先查补数再存当前;排序稳定保留相等项原次序;排序选择比较多种成本;选择最小项扩张有序前缀;相邻交换把当前极值移到尾;一轮无交换证明已无逆序;快排划分后只递归两侧;快排性能依赖划分质量;短边递归控制最坏栈深度;归并先解决两侧再线性合并;链式归并可用重接减少空间。
S006 排序收尾、分治与回溯开篇
不同排序利用不同信息。 堆排序只需比较,用一个有效长度把已放定的尾部隔离;桶排序则先依数值范围把跨桶次序固定,再处理桶内。线性期望依赖分布与桶数,不能只说分治就更快。递归划桶若所有值都相等,也要有停止条件,否则问题不缩小;概率模型分界是待验证假设,不是数据必然正态的事实。
额外信息替代比较时,也带来额外前提。 计数槽把值域本身变成有序索引,累计数量再给原始元素分配位置,从而保留带键对象及稳定性。范围太大就浪费,负数偏移也必须保序且不溢出。基数把大范围拆成小位范围,只有每轮稳定才能保存前面处理的低位次序,位数因此成为成本的一部分。
模板的局部修改也要重新证明。 快排某一分区版本的扫描次序与最终轴交换相互依赖,不能看似对称就随意互换。全相等输入可把等值区一次放定,减少无效递归。基数的稳定性则直接关系排序正确,而比较排序不稳定通常仍能得到正确键序列,只是记录同键次序改变。全书排序对照表在这些具体前提下阅读,不能代替各算法条件。
拆开后能否省工作,需要逐项计算。 两半分别平方处理再合并,可能只减常数;继续均匀拆到小问题并线性合并,才形成不同增长。并行又是另一层:独立子任务可以同时运行,但通信和汇总仍要付费。二分利用比较只保留一半候选,原问题答案就是被选子问题答案,因此无需像归并那样合并两份结果。
分解边界来自输入结构。 前序确定根,中序确定左侧有多少节点,再由数量定位前序中的右根;不需要复制两套子数组,也不保证两边一半大。哈希索引让合法输入下每个根定位快速,但缺失键或不一致序列必须拒绝,不能用默认位置继续构造。二分只保留一侧,树重建要把两侧都接回,二者的递归合同不同。
回溯先恢复现场,再换方向。 汉诺塔看似两次同类递归,但柱状态串起严格依赖,不能并行执行;它也提醒规模必须走向已定义的基本情况。回溯把选择空间逐条展开,路径状态要随进入增长、随返回恢复,记录结果则冻结一份快照。控制流返回本身不会自动撤销共享切片,也不会阻止后续选择覆盖旧结果。
搜索规则服务于问题定义。 当前路径含禁止节点后,后面怎么走都无法满足该约束,所以可整支剪掉;遇到一个合法目标却未必能停,因为其后代可能仍有需要记录的解。状态、选择、合法性、记录和撤销应各有责任,不能把通用框架中的return机械套到所有题。结果保存也必须隔离后续可变路径,才算真正记录。
作用域决定去重含义。 路径占用标志让一个位置在同一排列里只用一次,但回到父层后要允许它用于别的排列。相等值则会让同层不同位置产生相同整支结果,需要在一层的候选循环内只展开一次。穷举的输出本身就可能阶乘,剪枝可减少无效分支,启发式只改变优先方向;未覆盖的分支是否还能省略,需要另外证明。
等价结果应在生成前识别。 排列区分位置顺序,组合不区分,因此同样的选择树会产生不同去重问题:排列的相等值只在同层展开一次,组合还要避免先选4后选5与先选5后选4两条路径。原书可重复子集和要求正整数,使余额持续减少;零或负数会破坏终止和越界剪枝前提。后续通过非降索引把每个组合限制到一种生成顺序。
进一步阅读:二分边界约定必须成套;快排划分后只递归两侧;堆排序把极值留在已排序尾部;比较排序下界依赖比较模型;桶排序先划范围再桶内排序;计数排序成本取决于值域;前缀计数给每个值分配位置;低位基数排序依赖逐轮稳定;分治先证明可分和可合;子问题独立才方便并行;前中序重建依赖互异合法输入;汉诺塔子任务必须按序执行;回溯撤销状态再试其他选择;记录路径需要保存快照;剪枝必须证明后续不可能合法;找到一个解后是否停止看目标;排列选择集随路径使用量缩小;同层去重与路径占用分开。
S007 回溯收尾与动态规划
组合去重依赖生成顺序与选择次数两套规则。 非降索引让同一组元素只以一种顺序出现,传i允许继续用当前项,传i+1则消耗一次性位置。已排序相等值只在同层跳过,下一层仍可用另一个同值位置。余额剪枝还依赖正数使目标单调减少,这些前提一旦变化,原代码就不能直接复用。
状态决定哪些工作可以共享。 皇后用当前行和列/对角占用概括合法选择,撤销时恢复相同占用;楼梯则让不同路径遇到同一个阶数时共享答案。递归是控制工具,回溯是搜索策略,动态规划是对子问题答案的组织;不能用“都递归”把三者混为一类。缓存只有在状态包含足够信息时才能重用,否则会合并本不相同的问题。
把同一递推安排成两种求解顺序。 从目标往下问所需子问题是记忆化,从基本情况往上填依赖是表格法。楼梯用前两阶方案相加,因为最后一步两种来源互斥且覆盖全部合法方案;这首先是计数关系,不必为了使用DP而虚构最优目标。缓存与基本情况必须完整,合法输入和结果范围也不能被“只算一次”四个字掩盖。
状态既是答案索引,也是历史摘要。 楼梯方案的两项依赖可用滚动变量保存;但加入连续步长限制后,阶数本身不再足够,必须携带上一步类型。最小代价又使用取较小值而非方案计数的求和,所以初始条件和合并操作都由题目目标决定。所谓无后效性,是状态已经装下所需历史,而不是忽略仍影响未来的约束。
表项的含义是推导起点。 网格状态表示从起点到某行列的最小累计代价,最后一步只有上或左,因此可以比较两项再加当前代价;首行首列则只有一个来源。约束更复杂时要增加状态信息,能否DP与状态是否小到可用是两回事。最大最小字眼只是线索,真正证明仍来自充分状态和合法来源。
覆盖顺序决定值代表哪一行。 网格正序更新时,左边已经是本行答案,上方仍是上一行,恰好符合依赖。0-1背包则不同:无论选不选当前物品,都只能从上一批物品取得答案,下一步压缩必须保住这一条件。复杂度还要注明容量按数值计,输入和结果范围也不能被数学递推自动保证。
缓存存在不代表所有分支都已缓存。 0-1背包的每个状态由不选和合法选择两类来源构成,过重时也有确定结果;若这条分支直接返回不记录,重复路径仍可能重算。迭代表格则每项只填一次。压缩时更要保护上一行较小容量,倒序更新正是由“每项只可一次”的合同推出来,而不是背诵循环方向。
循环方向来自能否再次使用当前选项。 0-1从上一行读,容量倒序;完全背包可从本行较小容量读,正序。零钱兑换又把目标从最大价值换成最少枚数,并要求恰好凑出,所以不可达不能初始化成可行的零。相同表格外形不代表相同初始条件与合并操作,注释错写方向时要回到代码及题意核对。
同样累加,计算的对象也可能不同。 币种外层固定了组合生成次序,金额正序允许重复使用当前币;换循环层次可能把不同选择顺序都算进去。编辑距离则用两个前缀描述进度,末项相等时不新增代价,不同时从插删替来源取最小。序列单位必须先确定,Go字节操作不能直接冒充一般Unicode字符编辑。
进一步阅读:组合用非降索引消除顺序重复;有重复值的组合只跳同层重复;逐行放皇后用占用表剪枝;记忆化把重复子问题合并;自底向上按依赖顺序填表;滚动状态只保留仍被依赖项;最优子结构要求子解可替换;无后效性来自状态信息充分;先定义状态含义再写转移;网格最短代价来自上或左;滚动网格要读左新上旧;零一背包每项只来自上一行;零一背包倒序保住旧容量;完全背包正序允许当前项复用;恰好凑额要显式标不可达;组合计数先枚举币种再金额;编辑距离按两个前缀做决策。
S008 动态规划收尾、贪心与附录
压缩状态与固定选择都要保留正确依据。 编辑距离少存一行前,要明确哪个旧值会被覆盖并先保存;贪心少探索其他分支前,要证明某项选择不会排除全部最优解。前者优化表示,后者压缩搜索,两者都不能只因代码更短就认定正确。DP也包含记忆化而非只有表格,贪心则仍受当前约束影响,并不是凭空忘掉历史。
反例与证明承担不同职责。 一个币种反例就能推翻通用换币贪心,却不能靠几组正例证明任意金额都正确。分数背包则因可分和价值线性,可把低密度份额等重换成高密度份额,使价值不下降;这个交换思路才是选择安全的依据。若不允许分割,容量离散性改变,不能继续照用同一密度策略。
证明应说明被丢弃部分为何无需再看。 分数背包可用等重量替换保持可行且不降价值;容器则用当前短边限制一组未检查状态的上限,记录当前面积后便可安全舍去它。相等情况不破坏正确性,因此证明应使用不下降或不更优,而不能强说一定严格改变。整数拆分也要保留4拆2+2乘积相等的边界,才能正确推出最优形式。
算法推导到程序还差数值与环境合同。 切分策略可以正确,浮点取幂和整数转换却仍可能让大输入失真;复杂度也要看数值位长。附录把编辑器、语言工具链和插件分开,提供原版配置入口,当前使用时需按目标版本确认。它没有授权在本机安装、克隆或部署,本轮也未把这些操作记作已执行。
把问题转成别人能验证的修订。 贡献流程要求指出具体文本或代码、检查修改并说明意图;完整代码改动还需测试。此处流程和Docker命令仅保留原版操作参考,未实际对外写入或部署。末尾术语表把前文中英文名字重新对照,学习时可用于回找,不再把同义条目拆成重复知识卡。
进一步阅读:编辑距离按两个前缀做决策;滚动编辑距离先存左上旧值;贪心选择需要安全性证明;换币贪心可行也未必最少;分数背包按单位价值填容量;容器双指针舍去受限短边;整数拆分优先三避免余一;编程环境分成运行与编辑能力;开源修订交付可检验改动。
跨章综合
第一条贯穿线是“不变量决定操作”。数组有效区、环形队列front/size、哈希探测路径、搜索树范围、堆序、二分真假边界和DP表项含义,都在说明某一步为什么可以安全改变状态。实现时先说清一直保持什么,再判断索引和更新方向,不从代码形状猜正确性。
第二条是“提前丢弃需要证据”。二分借有序关系排除半段,回溯借不可修复约束剪枝,DP借相同充分状态合并重复工作,贪心借交换或上界论证固定选择。四者都减少探索,但证明对象不同:把一个局部条件套到另一类问题,常会漏解或误报最优。
第三条是“增长阶之外还有口径”。单次扩容与均摊追加、树高度与输出总量、网格状态数与容量数值、整数单位操作与大数位长、辅助空间与结果保存,都可能改变成本解释。缓存和连续布局影响实际常数,不能据此取消输入和模型条件。
第四条是“复制与所有权”。切片槽位可共享底层,节点链接可让外部引用继续保留后继,回溯结果必须保存路径快照,原地更新则要区分新旧状态。逻辑删除、对象回收、独立快照和物理内存归还不是同一个事件。
第五条是“目标与表示相互约束”。按字节算编辑距离和按字素算是不同题目;最少硬币与组合数量用不同初值及合并运算;0-1与完全背包用相反更新方向。输入前提、结果含义和可检查行为应先明确,再选容器和算法。
flowchart TD
A[问题目标与合法输入] --> B[状态与结构不变量]
B --> C[选择操作或子问题]
C --> D[证明保留全部必要答案]
D --> E[计算时间空间与输出成本]
E --> F[按实现版本与测试证据验证]
F --> A
箭头表示推导与验证的循环,不是某个算法固定执行流程。
发散与实践
以下为读者延伸:已交付《追踪二分边界的不变量》《追踪堆回调与堆序修复》两张实现深读计划。固定golang/go go1.25.0,收集并实际全文阅读6份官方实现、测试和示例,附URL、哈希与5条已填写首轮观察。前者把书中边界问题映射到sort.Search的单调谓词,后者区分container/heap公开操作与尾回调,并跟踪优先队列索引。
每份计划提供100分钟快速路径和按机制划分的详细判据。当前交付是计划与首轮材料,完整实践、测试、基准、工具安装、部署及外部贡献均未执行;入口见概览实践表。