来源书籍

Hello 算法--Go版本

Skill 版本:v23 153 张卡片

靳宇栋 · 2024-02-09 · Release 1.0.0,2024-02-09,Go语言版

全书导读

本书是以图解和代码建立算法直觉的入门教程,按复杂度分析、数据结构和算法策略三条线组织。当前输入是靳宇栋《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给上界而非精确阶;顺序相加嵌套按边界求和;增长阶由规模变化方式决定;分层总工作还要乘层数;全排列的输出数量本身很大;输入情形与渐近记号分开;空间分析关注同时存活峰值。

原书依据 · 27 处

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式条件,不能当所有平衡树的唯一通用定义;简单改链接也不保证搜索次序等额外性质。

容器决定待访问节点的顺序。 队列保留较早发现节点,形成逐层推进;递归栈先完成当前子树,再回到父节点处理另一侧。前中后序只改变根被记录的时点,递归关系相同。高度影响栈与路径,宽度影响队列,全部输出则另占线性空间;没有声明搜索次序时,树形漂亮也不意味着按值查询必然只走一条路。

进一步阅读:栈限制同一端进入与离开;队列在两端维持先进先出;环形队列用索引复用空间;双端队列开放两端操作;有限撤销需要淘汰最旧记录;双栈分离撤销与反撤销;哈希映射先算桶再比较键;有限桶必需处理冲突;负载因子只是密度指标;同桶容器保留全部候选;哈希扩容需要重新分桶;开放寻址保持一致探测序列;墓碑保留被删除后的搜索路径;空槽状态不能占用合法值;哈希分布与安全性质不同;取模与混合需要匹配输入;作为键需要稳定相等与散列;二叉树用两条子关系递归组织;高度深度必须统一计数口径;完全完美与完满约束不同;树的高度影响路径成本;队列保证树按层推进;深度遍历按访问时点分三序。

原书依据 · 27 处

S004 树的遍历、搜索树、AVL、堆与图开篇

链接可以显式保存,也可以由位置推算。 完全树按位置装入数组,父子索引便能替代指针;一般树若省掉中间空位,同一层序值序列可能对应不同结构,不能再靠原公式找孩子。搜索树则在普通二叉关系上增加全子树大小范围约束,才允许比较一次后舍去一侧。位置紧凑与查询有序是不同性质,不能互相替代。

所有更新都要维护全路径约束。 新键沿比较路径进入空位,删除则按孩子数选择断开、提升或用合法次序边界替换。只要每个子树仍处在祖先范围内,中序就能输出全部升序键。这里维持的是有序性,还没保证平衡;不能从“比较后走一侧”直接推导每次操作都是对数时间。

平衡是持续维护的结果。 普通搜索树按有序插入仍可能长成链,AVL额外限制局部高度差,并在更新后检查。旋转不改变中序次序,却改变哪些节点靠近子树根;中间子树必须转交到正确一侧,高度也按先下后上的新关系更新。这样保留查询规则的同时控制路径长度,代价是每次更新需维护更多状态。

局部修复必须接回整体。 同向高链用单旋,折线先转孩子再转根;每一层返回可能不同的子树根,上层链接和整树根都要接住。插入与删除都可能影响路径高度,因此更新、重新判定、旋转的过程应沿回溯推进。原书红黑树应用比较属于策略取舍提示,不作为所有负载下更快的实测结论;树章小结由前面的结构、遍历、次序和平衡四层共同承接。

局部规则可以提供专门能力。 搜索树靠全子树范围支持有序查找,堆只维护父子优先关系,便能快速拿到一个极值,却不保证其他位置排序。优先队列是使用方看到的抽象,数组堆是实现之一。Go接口又把末尾存取回调与真正恢复堆序分开,说明方法职责不能仅凭Push或Pop名字猜测。

修复范围来自被破坏的位置。 末尾插入只会影响向上的父子关系,根被末项替换则只需向下;每一步都要保留完全形状。构造整个堆时倒序处理非叶,使孩子先合法,再让父节点下沉。大量靠近底层的短修复让总成本优于把每次都按最长路径估算,具体证明在后续按层加权展开。

只保留任务真正需要的信息。 TopK不要求排好全部输入,小顶堆只维护当前候选集合及其最弱一项,新值能改善集合才替换。结果仍是堆,若要有序输出须再处理;k范围也不能省略。图则从层级结构扩展到一般关系,需要先说明方向和权重,再选择表示与算法。堆的名字与动态内存区域同名,不代表两者共享一种数据结构含义。

表示选择决定直接操作的成本。 矩阵用平方槽位换直接边访问,邻接表只保存存在关系而可能多花查找邻居的工作。无向更新要保持对称,零权与无边要区分;加一顶点不只是改一个边槽,连续行扩展也可能搬移。方向决定可达含义,权重决定路径目标,自环则是模型约定,不能从简单示例推广所有图。

进一步阅读:共享引用不等于共享槽位;树的高度影响路径成本;深度遍历按访问时点分三序;树的数组位置要保留空洞;搜索树按全子树范围排除;搜索树插入沿空位置接入;删除搜索树要保持次序;搜索树中序遍历得到升序;AVL用局部高度差约束形状;旋转保持中序并改变高度;折线失衡要先转孩子;树更新返回新的子树根;公开查询隐藏结构维护;堆用局部次序维护极值;堆接口回调只移动存储端点;入堆从末位向上修复;出堆用末项接替后向下修复;自下而上建堆是线性工作;固定小顶堆保留最大K项;图用边表达自由连接关系;图的连通要先说明方向;矩阵与邻接表保留不同信息。

原书依据 · 28 处

S005 图的实现与遍历、查找、排序开篇

关系更新必须保持两侧一致。 无向矩阵对应两个对称槽,邻接表对应两个邻居集合;删除顶点还会影响所有进入它的关系。先验证输入再更新,比仅创建一个未返回的错误值更重要。矩阵扩大连续行可能搬移,邻接表键则依实际类型的相等合同;不能把抽象表格的操作次数直接当任意Go实现最坏耗时。

发现与处理是两个时点。 图存在多条路径,若等到出队才标记,一个顶点可能在等待期间被反复加入。入队即记录已发现,使队列保留有限待处理集合。单次遍历的覆盖范围则由起点和方向决定,图不连通时需要从未访问顶点继续启动;矩阵和邻接表扫描邻居的代价也不同。

排除必须有不变量支持。 图遍历借visited避免重复,二分则借有序关系证明某段不可能包含目标。前者从一个起点只覆盖可达部分,后者每轮维护一个候选区间;二者都不能靠“看起来少走了路”证明正确。闭区间与半开区间各有一致的初始化和更新,必须整套保持,不能拿不同版本的边界拼接。

位置与是否存在分开返回。 下界即使找不到相等值,也有合法插入位置;遇到相等仍左缩,才能保留最早位置。调用者用位置检查存在,而不让查找器为了某个分支返回含混控制信号。是否值得排序或建立索引也取决于未来查询与更新总量,单次算法复杂度不是完整系统成本。

优化要保留题目合同。 上下界回答整段相等值的位置,不能用可能溢出的target+1或失真的浮点扰动偷换目标。两数和则利用已见元素的补数映射,把每轮搜索压缩,但必须先查再存以保证两个不同索引。选择查找方案还要把建表、维护、范围查询和内存预算一起计算,单个操作的期望复杂度不足以替代总成本。

排序不只有快慢一个维度。 相等记录是否保留顺序、是否使用辅助数组、递归栈有多深、对已近有序输入是否少做工作,都会改变选择。稳定性可承接已有次要键次序,组合比较器也能直接表达多级排序。选择排序则用扫描最小项扩张前缀,工作量稳定却可能跨越同键元素;计数应从真实循环边界求和,不能只背表中公式。

已有次序可以成为节省工作的证据。 冒泡完整一轮无交换,说明当前区间没有相邻逆序,可以结束;插入排序只移动必须越过的较大前缀元素,近有序时自然少做工作。稳定性则来自相等时不改变相对次序的具体条件,不能仅从“相邻”或“插入”名字推断。小输入常数优势是选择依据之一,仍需实际实现和负载确认。

分治质量决定增长。 快排每次把一个基准放定,再处理两侧;如果一侧持续为空,问题并没有有效分半。三数取中改善常见形状,仍不能承诺所有输入均衡。比较算法还要看交换、访问模式和栈,不能用名字“快”或一组常数估计替代工作量与前提。后续空间优化会控制栈深度,但不会自动消除坏划分的时间退化。

不同改写优化不同资源。 快排只把短边压栈,限制新增上下文,却仍可能做平方比较。归并先排好两半,再利用有序性线性合并,以临时数组换稳定、规则的工作;峰值空间要把数组和栈都算清。链表可重接已有节点,若采用自底向上迭代还可省递归,但这是带所有权前提的路线,原书并未提供完整可运行实现。

进一步阅读:把新元素插入有序部分;矩阵与邻接表保留不同信息;图更新同时维护顶点和边;图BFS在入队时标记访问;图遍历只覆盖起点可达部分;图DFS用访问集阻止回环;二分边界约定必须成套;预处理成本要按查询摊算;下界查找命中后继续向左;上界位置帮助确定最右匹配;两数和先查补数再存当前;排序稳定保留相等项原次序;排序选择比较多种成本;选择最小项扩张有序前缀;相邻交换把当前极值移到尾;一轮无交换证明已无逆序;快排划分后只递归两侧;快排性能依赖划分质量;短边递归控制最坏栈深度;归并先解决两侧再线性合并;链式归并可用重接减少空间。

原书依据 · 26 处

S006 排序收尾、分治与回溯开篇

不同排序利用不同信息。 堆排序只需比较,用一个有效长度把已放定的尾部隔离;桶排序则先依数值范围把跨桶次序固定,再处理桶内。线性期望依赖分布与桶数,不能只说分治就更快。递归划桶若所有值都相等,也要有停止条件,否则问题不缩小;概率模型分界是待验证假设,不是数据必然正态的事实。

额外信息替代比较时,也带来额外前提。 计数槽把值域本身变成有序索引,累计数量再给原始元素分配位置,从而保留带键对象及稳定性。范围太大就浪费,负数偏移也必须保序且不溢出。基数把大范围拆成小位范围,只有每轮稳定才能保存前面处理的低位次序,位数因此成为成本的一部分。

模板的局部修改也要重新证明。 快排某一分区版本的扫描次序与最终轴交换相互依赖,不能看似对称就随意互换。全相等输入可把等值区一次放定,减少无效递归。基数的稳定性则直接关系排序正确,而比较排序不稳定通常仍能得到正确键序列,只是记录同键次序改变。全书排序对照表在这些具体前提下阅读,不能代替各算法条件。

拆开后能否省工作,需要逐项计算。 两半分别平方处理再合并,可能只减常数;继续均匀拆到小问题并线性合并,才形成不同增长。并行又是另一层:独立子任务可以同时运行,但通信和汇总仍要付费。二分利用比较只保留一半候选,原问题答案就是被选子问题答案,因此无需像归并那样合并两份结果。

分解边界来自输入结构。 前序确定根,中序确定左侧有多少节点,再由数量定位前序中的右根;不需要复制两套子数组,也不保证两边一半大。哈希索引让合法输入下每个根定位快速,但缺失键或不一致序列必须拒绝,不能用默认位置继续构造。二分只保留一侧,树重建要把两侧都接回,二者的递归合同不同。

回溯先恢复现场,再换方向。 汉诺塔看似两次同类递归,但柱状态串起严格依赖,不能并行执行;它也提醒规模必须走向已定义的基本情况。回溯把选择空间逐条展开,路径状态要随进入增长、随返回恢复,记录结果则冻结一份快照。控制流返回本身不会自动撤销共享切片,也不会阻止后续选择覆盖旧结果。

搜索规则服务于问题定义。 当前路径含禁止节点后,后面怎么走都无法满足该约束,所以可整支剪掉;遇到一个合法目标却未必能停,因为其后代可能仍有需要记录的解。状态、选择、合法性、记录和撤销应各有责任,不能把通用框架中的return机械套到所有题。结果保存也必须隔离后续可变路径,才算真正记录。

作用域决定去重含义。 路径占用标志让一个位置在同一排列里只用一次,但回到父层后要允许它用于别的排列。相等值则会让同层不同位置产生相同整支结果,需要在一层的候选循环内只展开一次。穷举的输出本身就可能阶乘,剪枝可减少无效分支,启发式只改变优先方向;未覆盖的分支是否还能省略,需要另外证明。

等价结果应在生成前识别。 排列区分位置顺序,组合不区分,因此同样的选择树会产生不同去重问题:排列的相等值只在同层展开一次,组合还要避免先选4后选5与先选5后选4两条路径。原书可重复子集和要求正整数,使余额持续减少;零或负数会破坏终止和越界剪枝前提。后续通过非降索引把每个组合限制到一种生成顺序。

进一步阅读:二分边界约定必须成套;快排划分后只递归两侧;堆排序把极值留在已排序尾部;比较排序下界依赖比较模型;桶排序先划范围再桶内排序;计数排序成本取决于值域;前缀计数给每个值分配位置;低位基数排序依赖逐轮稳定;分治先证明可分和可合;子问题独立才方便并行;前中序重建依赖互异合法输入;汉诺塔子任务必须按序执行;回溯撤销状态再试其他选择;记录路径需要保存快照;剪枝必须证明后续不可能合法;找到一个解后是否停止看目标;排列选择集随路径使用量缩小;同层去重与路径占用分开。

原书依据 · 20 处

S007 回溯收尾与动态规划

组合去重依赖生成顺序与选择次数两套规则。 非降索引让同一组元素只以一种顺序出现,传i允许继续用当前项,传i+1则消耗一次性位置。已排序相等值只在同层跳过,下一层仍可用另一个同值位置。余额剪枝还依赖正数使目标单调减少,这些前提一旦变化,原代码就不能直接复用。

状态决定哪些工作可以共享。 皇后用当前行和列/对角占用概括合法选择,撤销时恢复相同占用;楼梯则让不同路径遇到同一个阶数时共享答案。递归是控制工具,回溯是搜索策略,动态规划是对子问题答案的组织;不能用“都递归”把三者混为一类。缓存只有在状态包含足够信息时才能重用,否则会合并本不相同的问题。

把同一递推安排成两种求解顺序。 从目标往下问所需子问题是记忆化,从基本情况往上填依赖是表格法。楼梯用前两阶方案相加,因为最后一步两种来源互斥且覆盖全部合法方案;这首先是计数关系,不必为了使用DP而虚构最优目标。缓存与基本情况必须完整,合法输入和结果范围也不能被“只算一次”四个字掩盖。

状态既是答案索引,也是历史摘要。 楼梯方案的两项依赖可用滚动变量保存;但加入连续步长限制后,阶数本身不再足够,必须携带上一步类型。最小代价又使用取较小值而非方案计数的求和,所以初始条件和合并操作都由题目目标决定。所谓无后效性,是状态已经装下所需历史,而不是忽略仍影响未来的约束。

表项的含义是推导起点。 网格状态表示从起点到某行列的最小累计代价,最后一步只有上或左,因此可以比较两项再加当前代价;首行首列则只有一个来源。约束更复杂时要增加状态信息,能否DP与状态是否小到可用是两回事。最大最小字眼只是线索,真正证明仍来自充分状态和合法来源。

覆盖顺序决定值代表哪一行。 网格正序更新时,左边已经是本行答案,上方仍是上一行,恰好符合依赖。0-1背包则不同:无论选不选当前物品,都只能从上一批物品取得答案,下一步压缩必须保住这一条件。复杂度还要注明容量按数值计,输入和结果范围也不能被数学递推自动保证。

缓存存在不代表所有分支都已缓存。 0-1背包的每个状态由不选和合法选择两类来源构成,过重时也有确定结果;若这条分支直接返回不记录,重复路径仍可能重算。迭代表格则每项只填一次。压缩时更要保护上一行较小容量,倒序更新正是由“每项只可一次”的合同推出来,而不是背诵循环方向。

循环方向来自能否再次使用当前选项。 0-1从上一行读,容量倒序;完全背包可从本行较小容量读,正序。零钱兑换又把目标从最大价值换成最少枚数,并要求恰好凑出,所以不可达不能初始化成可行的零。相同表格外形不代表相同初始条件与合并操作,注释错写方向时要回到代码及题意核对。

同样累加,计算的对象也可能不同。 币种外层固定了组合生成次序,金额正序允许重复使用当前币;换循环层次可能把不同选择顺序都算进去。编辑距离则用两个前缀描述进度,末项相等时不新增代价,不同时从插删替来源取最小。序列单位必须先确定,Go字节操作不能直接冒充一般Unicode字符编辑。

进一步阅读:组合用非降索引消除顺序重复;有重复值的组合只跳同层重复;逐行放皇后用占用表剪枝;记忆化把重复子问题合并;自底向上按依赖顺序填表;滚动状态只保留仍被依赖项;最优子结构要求子解可替换;无后效性来自状态信息充分;先定义状态含义再写转移;网格最短代价来自上或左;滚动网格要读左新上旧;零一背包每项只来自上一行;零一背包倒序保住旧容量;完全背包正序允许当前项复用;恰好凑额要显式标不可达;组合计数先枚举币种再金额;编辑距离按两个前缀做决策。

原书依据 · 19 处

S008 动态规划收尾、贪心与附录

压缩状态与固定选择都要保留正确依据。 编辑距离少存一行前,要明确哪个旧值会被覆盖并先保存;贪心少探索其他分支前,要证明某项选择不会排除全部最优解。前者优化表示,后者压缩搜索,两者都不能只因代码更短就认定正确。DP也包含记忆化而非只有表格,贪心则仍受当前约束影响,并不是凭空忘掉历史。

反例与证明承担不同职责。 一个币种反例就能推翻通用换币贪心,却不能靠几组正例证明任意金额都正确。分数背包则因可分和价值线性,可把低密度份额等重换成高密度份额,使价值不下降;这个交换思路才是选择安全的依据。若不允许分割,容量离散性改变,不能继续照用同一密度策略。

证明应说明被丢弃部分为何无需再看。 分数背包可用等重量替换保持可行且不降价值;容器则用当前短边限制一组未检查状态的上限,记录当前面积后便可安全舍去它。相等情况不破坏正确性,因此证明应使用不下降或不更优,而不能强说一定严格改变。整数拆分也要保留4拆2+2乘积相等的边界,才能正确推出最优形式。

算法推导到程序还差数值与环境合同。 切分策略可以正确,浮点取幂和整数转换却仍可能让大输入失真;复杂度也要看数值位长。附录把编辑器、语言工具链和插件分开,提供原版配置入口,当前使用时需按目标版本确认。它没有授权在本机安装、克隆或部署,本轮也未把这些操作记作已执行。

把问题转成别人能验证的修订。 贡献流程要求指出具体文本或代码、检查修改并说明意图;完整代码改动还需测试。此处流程和Docker命令仅保留原版操作参考,未实际对外写入或部署。末尾术语表把前文中英文名字重新对照,学习时可用于回找,不再把同义条目拆成重复知识卡。

进一步阅读:编辑距离按两个前缀做决策;滚动编辑距离先存左上旧值;贪心选择需要安全性证明;换币贪心可行也未必最少;分数背包按单位价值填容量;容器双指针舍去受限短边;整数拆分优先三避免余一;编程环境分成运行与编辑能力;开源修订交付可检验改动。

原书依据 · 10 处

跨章综合

第一条贯穿线是“不变量决定操作”。数组有效区、环形队列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分钟快速路径和按机制划分的详细判据。当前交付是计划与首轮材料,完整实践、测试、基准、工具安装、部署及外部贡献均未执行;入口见概览实践表。

生成进度与管理记录

Hello 算法–Go版本

Skill版本:book-notes v23

执行模式:light

建档进度:done

评级:经典原理;信息浓度高、稳定性高。

以概念、图解和算法代码解释机制;保留原书十五章与附录顺序,EPUB连续分段不冒充原书章界。

评级理由:复杂度、结构不变量和算法策略可长期迁移;图示与代码信息密集。具体性能依计算模型与输入前提,Go示例中的边界错误不照抄;EPUB部分数学符号原已缺失,只采用实际可读文字、代码与已读图支持的结论。

来源:靳宇栋;正文标明Release 1.0.0,2024-02-09,Go语言版;未找到可靠出版社/ISBN,不补造。OPF的2016时间是转换元数据,不当作本版日期。

整书笔记:_book_note.md

章节进度追踪表

章节号 章节标题 状态(pending/done) 卡片数
S001 前置说明、初识算法与复杂度分析 done 23
S002 复杂度分析收尾、数据结构、数组与链表、栈开篇 done 29
S003 栈与队列、哈希表、树与遍历开篇 done 22
S004 树的遍历、搜索树、AVL、堆与图开篇 done 19
S005 图的实现与遍历、查找、排序开篇 done 19
S006 排序收尾、分治与回溯开篇 done 16
S007 回溯收尾与动态规划 done 17
S008 动态规划收尾、贪心与附录 done 8

非正文排除

spine项 类型 排除理由

待关联术语

术语名 出现章节 一句话语境
Swiss Table spine2 原书Go桶/溢出桶是历史实现;Go1.24后实现已演进,本书未讲Swiss Table机制
最近点对 spine5 分治应用提名;本段未展开其完整机制,不由名字补造算法
Karatsuba spine5 分治应用提名;本段未展开其完整机制,不由名字补造算法
Strassen spine5 分治应用提名;本段未展开其完整机制,不由名字补造算法
逆序对 spine5 分治应用提名;本段未展开其完整机制,不由名字补造算法
B树 spine5 分治应用提名;本段未展开其完整机制,不由名字补造算法
B+树 spine5 分治应用提名;本段未展开其完整机制,不由名字补造算法
数独 spine5 回溯应用/相邻启发式提名,未展开完整解法;启发式不保证求到最优
图着色 spine5 回溯应用/相邻启发式提名,未展开完整解法;启发式不保证求到最优
旅行商 spine5 回溯应用/相邻启发式提名,未展开完整解法;启发式不保证求到最优
最大团 spine5 回溯应用/相邻启发式提名,未展开完整解法;启发式不保证求到最优
遗传算法 spine5 回溯应用/相邻启发式提名,未展开完整解法;启发式不保证求到最优
蚁群算法 spine5 回溯应用/相邻启发式提名,未展开完整解法;启发式不保证求到最优
区间调度 spine7 贪心应用列出一项策略或目标但未给完整证明;Dijkstra需非负边,股票约束变化会改变策略
霍夫曼编码 spine7 贪心应用列出一项策略或目标但未给完整证明;Dijkstra需非负边,股票约束变化会改变策略
Dijkstra算法 spine7 贪心应用列出一项策略或目标但未给完整证明;Dijkstra需非负边,股票约束变化会改变策略
股票买卖 spine7 贪心应用列出一项策略或目标但未给完整证明;Dijkstra需非负边,股票约束变化会改变策略
红黑树 spine3 已保留与AVL平衡/维护成本的定性比较,未展开颜色或旋转规则,不补造完整机制

引用文献

标题 类型(书/论文/框架/源码项目) 出现章节 一句话语境
hello-algo 源码项目 spine0 本书配套源码仓库与图解网页,按源文件名检索实现与测试;入口为原版记载
动手学深度学习 书 spine0 作者明确提名为手脑并用学习方式的启发,不代表已读该书
An algorithm for the organization of information 论文 spine3 1962年AVL原始论文在书中提名;本轮只读本书讲解,未读论文全文
A polynomial-time algorithm for the change-making problem 论文 spine7 Pearson, 2005原书引用,用于判断币种贪心性质;本轮仅登记未读论文

资金安全问题案例

问题标题 问题卡 解决方案卡(如有) 出现章节 一句话说明

实践卡进度

序号 实践标题 实践方式 状态(pending/done) 关联章节 产出
1 追踪二分边界的不变量 实现深读 done 10.2 二分查找插入点 追踪二分边界的不变量
2 追踪堆回调与堆序修复 实现深读 done 8.1 堆 追踪堆回调与堆序修复

实践候选筛选:done

实践取舍:重写全部数据结构与题库:成熟实现已可回答本轮机制问题,不扩大为完整造轮子;Go泛型容器或生产索引改造:需要实际业务合同,当前只交付理解与计划;真实硬件缓存基准:需固定机器与工作负载,原表数字不是当前基线;安装IDE/语言环境、Fork与Docker部署:仅原版操作参考,非本次实践执行任务;股票与币种现实决策:书中仅算法模型,不作为金融建议或现实干预。

轻量模式:未执行笔记复核、独立审查及审查结果优化。实践计划不代表已执行完整实践。当前生成及导入验收以_workflow.md为准。

相关主题

从本书的主题进入跨书阅读,对照其他书籍的讲解。下方数量包含主题关联的全部卡片与书籍。

暂无公开主题。