来源书籍

算法技术手册

Skill 版本:v24 算法与数据结构类 经典原理(高浓度 + 高稳定性) 131 张卡片

George T. Heineman、Gary Pollice、Stanley Selkow · 杨晨等 译 · 机械工业出版社(电子版:华章分社〔北京华章图文信息有限公司〕) · 2009 · ISBN 978-7-111-28674-5

类别清单覆盖

4/7

已覆盖 4 补充生成 0 未覆盖 3

全书导读

本书是一份面向程序员的算法选用手册:从问题和输入约束出发,把算法模式、可执行实现、复杂度和实验结果放在一起理解。读者应先确定结果及数据特性,再选择合适结构,最后核对具体实现的边界;书中历史代码与性能测量不能不经验证地作为当前生产结论。

全书主线

前几章介绍算法为何重要、如何用增长率分析时间和空间,以及模式如何把问题与解法联系起来。随后排序、查找、图、搜索、网络流和计算几何展示同一方法在不同对象上的运用。最后讨论近似、离线、并行和随机算法,并以基准测试附录说明理论与实测如何互补。

O’Reilly Media,Inc.介绍

出版商介绍说明该系列的翻译出版背景。

译者序

译者将本书定位为连接算法理论与程序设计实践的教程。

前言

作者希望读者从具体问题出发,选择算法并理解可执行实现。

先把问题映射到算法契约

面对实际问题,先说清输入、期望结果和约束,再判断一个算法是否符合这些条件,最后把抽象步骤落实到数据结构、错误处理和运行环境。能识别算法名称不等于已经解决了自己的问题。

本书偏重可用代码和经验分析,作者将形式证明的深入内容指向其他资料;这是一种取材侧重,不能推为伪代码或正确性证明没有价值。作者称示例经过测试是其陈述,本次没有执行书中测试,也不能将其推广为任何环境下的正确性保证。

6说明要理解集合、树等性质和控制流程,同时把深入的红黑树平衡证明留给其他资料。实践导向不是忽视证明,而是区分当前解决问题所需的假设与进一步论证来源。

8把数组、链表、栈、队列、散列表、树与图列为读者前置知识;模式化格式、不同语言实现与经验数据共同服务实际方案选择,而不是要求读者重新实现全部基础容器。

9把第1–3章定位为分析基础,第4–9章给出算法描述,第10–11章讨论替代思路与总结,另有基准测试附录。目录按不同问题组织,不表示必须严格按线性步骤执行所有算法。

16描述记录内存分配与释放的包装库:功能可用,但运行速度慢到无法使用。调优应先理解实际工作、数据规模与可观察的性能问题,再选择分析方法;源码中的具体瓶颈尚待后文实验验证。

先把问题映射到算法契约保存独立卡片。

原书依据 · 5 处

原则:使用实际代码,而不是伪代码

伪代码传达方法,实际实现仍需确定数据表示、接口和工程边界。

伪代码到实现须补齐契约

图P-1以残量网络中源到汇的路径反复增广:初始化流,找仍有容量的路径,以路径最小残量增流并更新正反方向。它展示算法轮廓,但没有限定图结构、数值类型、路径搜索、错误处理和外部接口。

把伪代码翻译为程序时,应给这些缺口明确约定,再用实际数据与边界验证;实现语言和数据结构不同,成本也会变化。图中的残量反向更新是允许后续调整已有流,不代表图中代码已经是一套完整可运行程序。

本节用最大流作动机,完整最大流实现及其条件在第8章,不能仅凭前言就断定其源码正确。

伪代码到实现须补齐契约保存独立卡片。

原书依据 · 1 处

原则:将算法和将要解决的问题分开

通用算法与具体问题可以通过明确接口衔接,各自保留责任。

通用搜索与问题状态分离

通用搜索负责选择和探索状态;具体问题负责定义状态表示、可用操作、目标条件及其他算法所需信息。接口清楚时,同一搜索流程可以对接不同问题,而问题代码也不必复制搜索控制逻辑。

作者以A*和八数码为例:3×3棋盘上的移动规则属于问题模型,A*的状态选择属于通用搜索。接口应实际表达算法所需的邻居、代价与目标等信息;前言没有展开完整签名,具体设计和正确性条件留到第7章。

优化应基于需求和测量,分离接口也不自动保证实现高效或正确。

通用搜索与问题状态分离保存独立卡片。

原书依据 · 1 处

原则:仅仅讲述足够的数学

数学用于解释结构和性能,本书对详细证明选择引用其他资料。

先把问题映射到算法契约关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处

原则:用经验来支持数学分析

理论复杂度与基准数据互相补充,但测量结论受平台和工作负载约束。

基准数据解释理论成本边界

数学分析描述随规模增长的行为及前提;基准测试测量具体实现、数据、硬件和环境下的表现。两者回答不同问题:渐近较优的方法不一定在每个有限规模都更快,单次测量也不能证明所有输入的增长界。

书中计划提供JUnit测试和跨平台基准,并承认读者结果可能不同。使用它时应记录输入分布、版本、平台、预热及测量方法;作者“跨平台证明不依赖平台”的表述过强,有限平台结果只能支持其覆盖条件下的观察。

基准可检验性能预期,正确性测试另需覆盖结果与边界;本次没有运行这些基准。

54/03174列三种历史平台上千万次比较、乘法、除法和平方根的耗时;例如表中部分平台浮点乘法不比整数乘法慢。结果只支持所测硬件、编译方式和任务,不证明当前所有CPU或程序都遵循某个固定排名。

基准数据解释理论成本边界保存独立卡片。

原书依据 · 2 处

目标读者

本书面向已有基本数据结构与编程经验、需要选择和测试方案的读者。

先把问题映射到算法契约关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处

本书组织方式

全书从分析基础和统一算法模式出发,进入具体算法,最后讨论替代方案与基准方法。

先把问题映射到算法契约关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处

本书体例

体例区分代码、术语、变量、算法名称与文献引用。

代码使用说明

作者说明书中代码使用许可和归属要求,并给出咨询途径。

联系我们

本书列出出版社联系和书籍资源页面作为读者入口。

致谢

作者感谢审阅者及家人对写作的支持。

参考文献

前言列出算法导论与计算机程序设计艺术两项参考。

第一部分

第一部分导览列出算法意义、数学原理与模式领域三章。

第1章 算法真的很重要

算法是一组解决特定问题的步骤。相同功能的实现可能因数据、规模和执行环境产生很大差别;先确定实际瓶颈,再比较可行解法。

内存记录库的实际案例引出性能分析:可运行的功能仍可能因算法和数据结构选择无法满足运行时间要求。

先把问题映射到算法契约关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处

理解问题

从需求、包装接口和不同工作负载入手,界定内存跟踪器的性能问题。

问题先于算法

选算法前先定义要观察的对象、期望结果和约束,再了解当前实现与异常现象。本例目标是记录内存分配及释放,让程序结束时能识别未匹配的分配;包装malloc、free和exit把事件送入记录结构并继续调用系统服务。

作者观察到小程序尚可接受,而处理大量工作且有泄漏的程序非常慢;这只是初始现象,不足以直接证明“最终泄漏量”是唯一原因。下一步应设计能够区分候选原因的工作负载。

记录器只覆盖通过这些包装入口发生的事件;即便记录全部匹配,也只能在覆盖范围与跟踪假设成立时说明相应分配已释放,不能单独证明程序没有其他任何资源问题。

42指出重复实现的原因包括不知道已有解、无法判断已有方案是否适合、难以找到可调整的实现。选择时应核对问题定义、输入约束和运行环境,存在同名算法并不自动意味着实现可复用。

问题先于算法保存独立卡片。

原书依据 · 2 处

如果需要,尽可能用实践检验

对照未释放、立即释放和最后释放的程序,案例识别出同时存活记录数量与未平衡树形态。

对照实验区分存活峰值与泄漏

三个程序都循环一百万次分配32字节:A不释放;B每次分配后立即释放;C先全部分配再全部释放。书中报告A和C慢、B快,因此“退出时最终未释放量”不能单独解释差异;A/C在运行中同时保留大量记录,B的存活记录峰值很小。

这是作者报告的对照观察,不是本次运行结果。三个程序的释放时机、实际内存使用和其他行为也不同;要将原因落实到记录器,应继续检查数据结构及增长规律,而不是仅凭相关性宣称已经完成所有因果验证。

对照实验区分存活峰值与泄漏保存独立卡片。

原书依据 · 1 处
搜索树成本取决于实际高度

二叉搜索树每步只进入一个子树,操作成本与树高度相关。平衡时高度可为O(log n);若键按顺序插入普通未平衡树,可能退化成单链,高度和一次操作均为O(n)。图中1到15顺序插入形成长链,而以8为根的另一插入顺序形成高度较小的树。

案例的跟踪器以地址为键,作者将慢速归因于树严重右倾;地址分配顺序与平衡策略共同影响形态,不能仅因“使用二叉树”就保证对数复杂度。书中一百万节点约20次比较是平衡树高度量级的说明,不是所有树和每次操作都恰好20次。

搜索树成本取决于实际高度保存独立卡片。

原书依据 · 1 处

解决问题的算法

案例采用红黑树约束搜索树高度,作者报告性能明显改善;理论高度界与实际倍率需分开。

平衡树的保证来自高度界

红黑树在二叉搜索树上维护颜色与路径约束,使含n个内部节点的树高度至多约2log₂(n+1),从而搜索、插入和删除可获得对数级高度界。平衡不是要求所有叶深相差至多1;那是比红黑树所需约束强得多的形状条件。

书中称最长路径“不存在两倍于另一条路径”,应结合标准红黑树从同一节点到后代空叶的路径条件及计数约定理解,不能无条件套到任意两个内部节点或不同起点。

案例作者报告更换结构后约5000倍改善;500000/20只是比较次数的粗略量级估算,完整程序运行还包含分配、维护和其他开销。本次未运行案例,不能把倍率作为普遍预测。

平衡树的保证来自高度界保存独立卡片。

原书依据 · 1 处

花絮

同一分配器在不同释放次序下的测量可以提示差异,但不足以单独推断内部实现。

基准差异不能单独证明机制

作者对每种块大小做100次试验,去掉最好和最坏结果,比较4096块的分配及三种释放策略;图03134展示不同规模和策略的运行时间。作者报告freeDown约慢于freeUp,但结果限于所用平台、数据与实验方式。

不同次序可能影响分配器内部状态,也可能受缓存、计时、后台任务等影响。没有检查实现或设计隔离实验时,不能从曲线断定分配器一定使用红黑树或给出唯一原因。去掉极端值是处理数据的一种选择,应记录原始分布、环境及复现方式,不能因此保证无偏。

本次只阅读图表和作者叙述,没有执行基准。

基准差异不能单独证明机制保存独立卡片。

原书依据 · 1 处

故事的寓意

可接受方案须满足需求,并在改进收益与成本之间做判断。

算法选择以需求和代价为界

目标不是总找理论上最完美的算法,而是在实际输入、可接受延迟、资源和维护成本下选择满足需求的方案。案例中平衡树使作者报告的性能达到可用水平;进一步优化是否值得,应比较收益、风险和实施成本。

“当前可接受”依赖明确指标及预期工作负载,需求变化后需要重新评估。能理解现有算法的前提、增长和实现边界,常比重新发明算法更直接地帮助解决问题。

算法选择以需求和代价为界保存独立卡片。

原书依据 · 1 处

参考文献

第一章引用算法导论作为红黑树及算法分析参考。

第2章 算法的数学原理

复杂度分析研究资源消耗如何随输入增长。大O给出渐近上界,最好、平均与最坏情况需要明确输入和概率假设;递推式则表达分解出的子问题及额外工作。

算法分析把样本规模、操作代价和计算平台联系起来,需要明确抽象假设。

常数成本是分析模型假设

估算算法运行时间时,可以先假定基本操作具有某种固定成本,再研究输入规模增长时的主导项;这使不同方案的增长趋势可比较。

原文称所有平台上这些常数都小到可忽略,不能作为普遍事实。现实中缓存、分配、输入类型、I/O或语言实现可能改变成本,某些操作也随数据位宽或大小增长。渐近分析与测量需各自标明模型和范围。

31将比较k位整数视为O(1),条件是k固定不随问题规模改变。若k作为输入规模变化,大整数表示及比较所需工作也可能随k增长;不能把固定机器字的近似直接推广为任意精度整数。

50引出处理器整数运算、浮点单元与IEEE754表示;速度和语义依赖数据类型、硬件、编译器及运算,不能仅据“整数通常高效”断言所有情况下整数都比浮点快。后续章节再按具体示例讨论舍入、比较和特殊值。

常数成本是分析模型假设保存独立卡片。

原书依据 · 3 处

问题样本的规模

样本规模与表示方法共同决定基本操作代价,附加信息可能改变查询与维护成本。

编码改变查询与维护成本

判断整数二进制表示中1的个数奇偶性,直接扫描n位需要检查输入;若编码额外保存可信的奇偶位,查询该位可为O(1),但生成或更新这个附加位也有成本,且必须保证它与原数据一致。

书例15137300128的二进制为1110000110010000001101111010100000,共34位、14个1;附加0表示偶数。原文在这里混用“字节”和位,并前后把直接扫描相对n的增长说成线性又说对数;以n为二进制位数时扫描为O(n),以数值x为变量才约为O(log x)。

03135还用同一俳句的不同文字编码说明表示并非只有一种。原文“64位算法一定比32位花两倍时间”不能由字宽单独推出,实际取决于平台和操作。

编码改变查询与维护成本保存独立卡片。

原书依据 · 1 处

函数的增长率

增长率描述规模变化趋势;有限规模的常数、输入表示和拟合模型仍影响真实选择。

增长率

增长率描述成本随输入规模变化的趋势。它用于比较规模扩大后的资源需求,但不能代替具体实现、工作负载和平台上的测量;小规模时常数及初始化成本可能决定哪个实现更快。

在n个互异元素中顺序查找,目标保证存在且各位置等概率时,平均比较次数是(1+…+n)/n=(n+1)/2,而非恰好n/2;n/2是大n下的近似,两者比值趋近1。若目标可能不存在或位置分布不均,期望应重新计算。

03136的元素查询表和03140的排序曲线只是作者指定平台与输入下的实验;原文将平台变化一概当固定倍数过于宽泛。书中R²=0.9948也不是“只有0.52%的概率不拟合”:在通常含截距回归语境,它描述样本变异中模型解释的比例,不直接给出这种概率或外推保证。

30将时间和存储空间作为不同衡量维度,并列出常数、对数、次线性、线性、n log n、平方及指数类别。此排序讨论的是规模趋大下的增长,不保证每个有限输入或具体实现的绝对速度排名。

增长率保存独立卡片。

原书依据 · 2 处
拟合优度不是失配概率

R²在常见含截距回归中比较拟合残差与样本总变异,0.9948表示样本内解释比例约99.48%,不能读作“模型只有0.52%概率拟合失败”。高拟合度也不能证明模型在未测规模、其他工作负载或其他平台仍准确。

书中对四种排序方法用历史平台的测量拟合二次与n log n函数,并观察某实现的分段行为;拟合只是对指定数据的描述,源码和额外数据才能帮助解释切换原因。测试设置、数据分布与误差应随结论保留。

拟合优度不是失配概率保存独立卡片。

原书依据 · 1 处

最好最坏和平均情况下的性能分析

最坏、平均和最好情况分别描述不同输入下的性能,平均情况必须指定分布。

性能三种情况

固定输入规模n时,最坏情况取该规模合法输入中最大的成本,最好情况取最小成本,平均情况则按明确输入概率分布计算期望。它们回答上界风险、可能的最小工作和特定工作负载下的平均成本,不能相互替代。

03141–03142对比随机、有序和近有序数据,说明同一排序方法的相对表现随输入结构变化;单一图表不能证明所有规模和环境中的排名。实际选择还要考虑尾部延迟、资源与可靠性,而平均值本身并不描述尾部。

27定义Twc(n)=max_{s∈S_n}t(s),其中S_n为规模n的合法输入集合。最坏输入的构造可以帮助分析,但仅测一个看似困难的样本不能证明它是全部输入的最大值;最坏界也不是对所有实际请求都发生的时间预测。

29说明顺序查找若第一个元素命中可提前结束;若责任是计数所有匹配项,则必须读取完整列表,其最好与最坏扫描次数均随n线性增长。若只需存在性,提前退出通常可减少部分输入的工作;不能因此否定需要完整计数的任务。

性能三种情况保存独立卡片。

原书依据 · 3 处
最坏情况

最坏运行时间定义为固定规模全部合法输入上的最大成本。

性能三种情况关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处
平均情况

平均成本是输入概率加权的期望,图中的额外归一因子与文字给定的概率定义不一致。

期望成本按概率加权一次

若规模n的离散输入集合Sn中每个输入s的概率p(s)已归一化且总和为1,期望成本为Σ{s∈S_n}p(s)t(s)。若各输入等概率,则p(s)=1/|S_n|,公式才可写为Σt(s)/|S_n|。

03143在Σt(s)p(s)外又乘1/|S_n|,与正文“概率和为1”的定义矛盾,会重复除以集合大小;例如两个等概率输入成本2与4,期望为3,额外除以2会错误得到1.5。03144的(n+1)/2仅用于先前目标存在、各位置等概率的顺序搜索例。

概率模型是分析前提,真实工作负载改变时期望也会改变;平均值不能单独证明过载概率或最坏情况下的安全性。

期望成本按概率加权一次保存独立卡片。

原书依据 · 1 处
最好情况

最好情况是同规模合法输入中所需成本最小的情形。

性能三种情况关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处

性能指标

性能除了时间还包括存储,增长类别比较应保留规模和操作模型。

增长率关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处
讨论0:常数级算法的性能

固定字长比较可以视为常数,但字长本身增长时需纳入成本。

常数成本是分析模型假设关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处
讨论1:对数级算法的性能

区间折半提供对数级候选收缩;牛顿迭代是另一类局部数值过程,需单独核验公式和收敛条件。

折半缩小候选需明确胜利条件

在有序候选中,每次猜中点并据高低反馈排除一半,可在对数次数内定位目标。书例一百万个候选在20次内可以猜中;这个数量级来自每步缩小候选区间。

“知道剩余数字”和“实际猜中数字”是不同计数规则。若每次必须明确猜中才能获胜,n=2时最坏需2猜,不能机械套ceil(log₂n)=1。对n个连续候选,标准中点猜测最坏可用ceil(log₂(n+1))描述;图03147在剩余至多三个候选时直接返回1+turns,是把一次反馈后推知答案计入结果,不一定等于要求最后再报出正确数字的猜测次数。示例也未处理mid=(low+high)/2的整数溢出。

折半缩小候选需明确胜利条件保存独立卡片。

原书依据 · 1 处
牛顿迭代先核对导数与收敛

书例方程x sin x−5x=cos x,若设f(x)=x sin x−5x−cos x,则f′(x)=x cos x+2 sin x−5;正文把−cos x的导数写成−sin x,误得x cos x−5。不能将该错误导数直接用于牛顿更新并把表格当成正确推导。

牛顿法xₖ₊₁=xₖ−f(xₖ)/f′(xₖ)的局部收敛依赖初值、导数和函数条件;它不是像二分查找那样每步保证候选区间减半。03148列出作者示例迭代数字,未提供足够依据证明该表来自哪个具体实现;本次未运行数值代码。

牛顿迭代先核对导数与收敛保存独立卡片。

原书依据 · 1 处
讨论2:次线性的算法的性能,时间复杂度为O(nd),d<1

次线性成本在输入规模增大时增长慢于线性,但边界取决于参数与问题。

次线性查询还要计入输出

当0<α时n^α比n增长慢,但具体查询上界依赖维度、树形态、查询类型及返回结果数量。书中提到平衡kd树的区间查询O(n^(1−1/d));如果需要报告k个结果,至少还有输出k项的成本,且维度d、输入假设不能省略。

这只是本节提名的模型,不把它当所有kd树查询和任意维度下的无条件保证;具体构造和查询实现留第9章。

次线性查询还要计入输出保存独立卡片。

原书依据 · 1 处
讨论3:线性算法的性能

逐位相加的操作次数随位数线性增长;具体实现和编译配置影响常数。

逐位加法的进位贯穿输入

按最低位向高位遍历,每位计算aᵢ+bᵢ+carry,当前结果取个位,若和至少10则向下一位传进位,最终进位写到最高位。03150与03151分别用取模和条件减10生成该位,均对n位循环,结果数组需要n+1个位置。

两输入长度、每位0到9以及输出容量是这些示例可正确工作的前提;代码没有完整参数检查。固定字长机器整数可视为常数操作,任意长整数位数n增长时逐位算法则为O(n)。

03152–03154是作者在特定历史机器、数据和编译选项上的测量;优化等级更高或避免取模不保证在所有编译器和工作负载中总更快。没有运行原Java或C代码。

逐位加法的进位贯穿输入保存独立卡片。

原书依据 · 1 处
讨论4:nlogn算法的性能

把问题均分为两个子问题并线性合并时,递归树每层的合并工作至多线性,总上界为n log n。

分治成本按每层合并累计

对T(n)=2T(n/2)+O(n),假设递归在常数规模停止,层数为O(log n),每层总合并工作O(n),因此T(n)=O(n log n)。若每层合并实际达到Θ(n),才能进一步得到Θ(n log n);仅有O(n)上界不能自动证明匹配下界。

这个推导依赖子问题数量、规模和合并成本,不能把所有递归算法都标为n log n。非2的幂可以按舍入处理,通常不改变该上界。

分治成本按每层合并累计保存独立卡片。

原书依据 · 1 处
讨论5a:二次方的算法性能

逐位乘法的双层循环导致二次工作,有限实验可支持观察但不能单独证明渐近界。

同阶优化不排除更快算法

03155的mult对两组数字各遍历一次,每对位置计算部分乘积和进位;两个输入均为n位时核心循环执行n²次。表03157中规模加倍的时间比接近4支持该实验范围内的二次趋势,但有限数据和计时噪声不是对所有规模的严格证明。

作者另提alt跳过零位、减少取模,并报告约40%改善;图表呈现的是指定实现与样本,不保证所有数据均有这个比例。改变常数与改变渐近增长是不同结果,更快的大整数乘法可能采用不同算法,不能据当前双层循环推断乘法问题必有二次下界。

同阶优化不排除更快算法保存独立卡片。

原书依据 · 1 处
讨论5b:性能不明显的计算

求最大公约数的迭代次数依赖数值和变换规则;示例代码的零输入分支与描述存在偏差。

减法与取模改变公约数迭代

反复从较大非负整数减去较小值能保留最大公约数,但若一数为1,迭代次数随另一数值线性增长,相对于该数的位数可能是指数级。取模版一次用余数取代多次减法,迭代次数及每次大整数除法成本需要分别分析。

03158与03159的零值入口均写成:a为零时assign(gcd,a),b为零时assign(gcd,b);若assign的参数方向按同图后续assign(gcd,a)的注释理解为前者接收后者,则gcd(0,b>0)错误返回0而非b,gcd(a>0,0)也同样。辅助函数未展示,结论以该参数方向为前提;不能宣称已运行确认。

减法版对(1000,1)先把1000减至1需999次,再在相等分支把b减为0还需1次循环,源码总共1000轮,正文的999步只覆盖前半。03160–03161随机样本曲线不能单独证明最坏增长;代码和测试均未执行。

减法与取模改变公约数迭代保存独立卡片。

原书依据 · 1 处

混合操作

多种操作的总成本取决于各操作次数及各自平均成本,选择可能随规模和工作负载改变。

混合工作负载按频次加权

把各类操作次数乘以对应单次成本,再求和,才能比较混合工作负载。表03162小规模A为2000×0.008+3000×0.001=19 ms,B为5 ms;大规模对应总数分别1220和201630 ms,结论随规模变化。

这些是表中假设的平均成本和次数,不能当作所有系统实测;如果操作相互影响缓存、锁或数据结构状态,简单加权可能低估交互成本。应确认操作分布、量纲和测量条件,必要时以完整混合负载验证。

混合工作负载按频次加权保存独立卡片。

原书依据 · 1 处

基准测试

基准帮助检验关于基本操作成本的假设,但解释性能断点仍需实现和环境证据。

基准验证

基准应先提出可区分的假设,固定工作负载和环境,再记录多次测量与处理方法。本例对计算2ⁿ及大数乘法提出成本假设,每种设置做50次实验、剔除最高最低后报告48次平均;图中不同数值范围出现不同斜率或台阶。

图03163的Scheme过程每轮把结果乘2,n次递归产生2ⁿ;03164展示2⁸⁵¹的大整数。固定宽度机器整数可能溢出,大整数表示的成本则随位数和实现改变。仅有曲线不能证明某个断点必然来自机器字长,解释需要确认语言运行时、表示和源码;也不能把这个历史平台的结果当全部语言现状。

基准结果用于评估特定假设,测试正确性和测量性能是两项任务。此处只读取原文与图,未运行基准。

48描述通常k≥10次实验,去掉最大最小值后报告其余平均值及标准差;这是一种处理选择,极值不一定都是异常,是否剔除应说明依据并保留原始分布。两台平台不能代表全部现有系统,也不能单独证明算法在任何环境的性能。

基准验证保存独立卡片。

原书依据 · 2 处

最后一点

大O、大Ω和大Θ分别表达渐近上界、下界和匹配阶,宽松上界仍可能成立但信息少。

渐近上界与紧确阶不同

若存在常数c>0和n₀,使充分大n时T(n)≤c·f(n),则T∈O(f)。若存在常数c′>0使T(n)≥c′·f(n),则T∈Ω(f);两者同时成立时T∈Θ(f)。这些关系需要指定输入规模、成本与所讨论的最好/最坏/平均情形。

线性算法也属于更宽松的O(2ⁿ),但该描述没有体现已知的线性上界;这不意味着O(2ⁿ)是精确分析的结果。原文把某些下界写成不带常数因子的g(n)≤t(n),应补上渐近常数与阈值。

大O不是默认等于Θ:获得上界不能自动获得匹配下界;作者在本书用O作简写时,具体结论仍需查看证明和前提。

渐近上界与紧确阶不同保存独立卡片。

原书依据 · 1 处

参考文献

本章列出排序函数和大整数乘法相关论文。

第3章 模式和领域

算法模式把问题、输入输出、适用条件、核心步骤、实现和分析放在同一框架中。抽象算法依赖具体数据结构,整数、浮点及内存模型又会影响实现。

复用已有算法前,需要判断它是否适合当前问题以及是否能找到合适实现。

问题先于算法关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处

模式:一种交流语言

模式为反复出现的问题与经过验证的方案提供共同描述语言,而非替代上下文判断。

算法模式语言

模式把一类反复出现的问题、适用环境和已有解决思路组织成便于交流的描述。算法模式也可以帮助读者比较不同方案的目的、条件、步骤与代价,避免只复制名称或代码。

模式不是填空模板:具体输入、正确性前提、数据结构和实施约束仍须核对。书中将算法视为已知问题的方案,并以未平衡二叉树案例说明直接套用熟悉结构可能不满足性能需求;经过验证也不意味着对任意新环境自动有效。

本节提及建筑模式和软件设计模式的历史背景,以下章节给出本书自己的描述格式;这些背景不等于当前已经检查所有引用原著。

44说明算法描述通常有固定栏目,但可按知识点省略或新增;格式帮助读者比较,不应让空栏目代替真实约束和证据。

46/03167把顺序查找的名称、最好/平均/最坏性能、数组概念、逐项比较伪代码和实例放在同一图中;03168图标既包含数组、树等结构,也包含分治、回溯等方法。比较算法时不能把图标共同出现误认成相同问题或相同成本前提。

算法模式语言保存独立卡片。

原书依据 · 3 处
算法模式的格式

统一描述格式便于交流,但各算法章节可按需要增减。

算法模式语言关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处

算法模式的格式

算法模式依次描述名称、目的、环境、驱动因素、方案、结论、分析与相关算法。

比较算法要同时看环境与代价

统一算法描述把名称与目的放在入口,使用环境限定问题,驱动因素说明选择理由;解决方案展示实现,结论说明优缺点与反例,分析呈现性能和解释,相关算法提供替代或变种。栏目顺序帮助比较,但每项都必须结合当前输入与约束填写。

对同一问题比较两个算法时,可以先核对它们是否解决相同输出,再比较前提、数据结构、最好/平均/最坏成本及实现边界。仅比较某个O记法或基准数字,可能遗漏不同的目标或输入假设。

比较算法要同时看环境与代价保存独立卡片。

原书依据 · 1 处

伪代码模式的格式

算法详解将伪代码、例子、性能和使用的概念放在同一视图中。

算法模式语言关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处

设计格式

类图区分继承、接口实现和成员访问级别;阅读代码时需结合语言规则。

类图用不同关系表达继承

03169显示SegmentTreeNode实现IInterval和IBinaryTreeNode接口,DefaultSegmentTreeNode与StoredIntervalsNode继承SegmentTreeNode;图中空心三角实线表示继承,空心三角虚线表示接口实现。类框列出字段与方法,符号+、−、#、~分别表示公共、私有、保护和包可见。

Java protected允许同包访问,并允许符合条件的跨包子类访问;原文“Java中只对同包可见”遗漏后者。final字段赋值后不能重新赋值,不代表引用指向的对象状态一定不可变。参见Java语言规范6.6.2,2026-11-06核验相关规则。

结构图

classDiagram
class IInterval {
 <<interface>>
 +getLeft() int
 +getRight() int
 +intersects(int,int) boolean
}
class IBinaryTreeNode~T~ {
 <<interface>>
 +getLeftSon() T
 +getRightSon() T
}
class SegmentTreeNode {
 ~int left
 ~int right
 ~int count
 ~SegmentTreeNode lson
 ~SegmentTreeNode rson
 +getLeft() int
 +getRight() int
 +getLeftSon() SegmentTreeNode
 +getRightSon() SegmentTreeNode
}
class DefaultSegmentTreeNode
class StoredIntervalsNode {
 #ArrayList intervals
}
IInterval <|.. SegmentTreeNode
IBinaryTreeNode <|.. SegmentTreeNode
SegmentTreeNode <|-- DefaultSegmentTreeNode
SegmentTreeNode <|-- StoredIntervalsNode

图为03169关键关系与代表性成员,不声称列尽全部方法。

类图用不同关系表达继承保存独立卡片。

原书依据 · 1 处

基于经验的评价格式

作者用多个独立实验和摘要统计展示特定平台上的性能。

基准验证关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处

领域和算法

应用领域的约束和算法所解决的问题共同决定方案选择。

领域约束影响算法适用性

应用领域描述实际场景、目标和限制;算法领域描述常用的问题与方法。二者不是一一对应:同一图搜索算法可用于不同场景,同一场景也可能使用多种算法。

移动设备场景中,空间、延迟和存储等约束可能改变选择,最快的方案未必满足内存预算。应把实际问题映射为输入、输出和资源约束,再核对算法使用环境,而不是凭领域名称或经验标签直接选定实现。

领域分类可以帮助检索候选,不能代替对数据规模、正确性和代价的验证。

领域约束影响算法适用性保存独立卡片。

原书依据 · 1 处

浮点计算

硬件支持的整数和浮点运算属于成本模型的一部分,表示精度和特殊值也影响算法结果。

常数成本是分析模型假设关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处
舍入的错误

有限位浮点格式只能精确表示部分实数,误差需要按表示与尺度解释。

浮点表示误差依赖数值与尺度

binary32格式使用1位符号、8位指数和23位显式尾数;并非所有十进制数都能精确表示。03170的3.88f位模式0x407851ec对应约3.880000114440918,绝对误差约1.144×10⁻⁷,相对于3.88约2.95×10⁻⁸。

相对误差是绝对误差除以非零参考值的绝对值;参考值为0时须另选误差度量。标准规格化写法为1.f×2^(E−127);原文使用0.1f×2^(E−126)的另一规格化约定,指数偏移差一可与前者等价,不能只比较偏移数值就断定例子错误。

有限精度不意味着每个数和每次操作都必然有误差;整数、二进制分数等在范围内可能精确表示。表中“总共32个字节”应为32位。

浮点表示误差依赖数值与尺度保存独立卡片。

原书依据 · 1 处
值之间的比较

近似比较依赖误差容限,但由固定阈值产生的关系通常不具备传递性。

近似相等未必满足传递性

若以|a−b|<δ定义近似相等,则a≈b和b≈c不保证a≈c。例如δ=1时0≈0.75且0.75≈1.5,但0不近似1.5。不能直接把这种关系当作需要等价关系的集合键或排序相等规则。

03172的点按数学值在y=5x上,浮点计算叉积却得到约4.8828125×10⁻⁴,双精度得到约−4.55×10⁻¹³;运算顺序和表示误差会影响结果。阈值应考虑绝对尺度、相对尺度和问题对边界的要求,近乎共线的可靠判定可能需要更稳健的谓词。

精确浮点比较并非永远错误;当业务契约需要比较实际存储值、特殊值或已保证精确的量时,它表达的是另一种语义。

近似相等未必满足传递性保存独立卡片。

原书依据 · 1 处
特殊的量

浮点特殊值可参与运算,其传播和比较行为需要按语言规则理解。

特殊浮点值仍参与运算

浮点格式有正负无穷、NaN和带符号的零。它们可以作为浮点操作的输入或结果,不能按原文“不会被标准运算使用”理解成禁止参与运算;NaN的比较及传播需要按语言与操作定义处理。

03173将正零、负零的64位编码写反:binary64正零是0x0000000000000000,负零是0x8000000000000000;无穷位模式在图中另列。符号零的数值相等性与某些运算中符号影响是不同问题。

Java例中1/0.0是浮点除法,1/0则是整数除法并抛ArithmeticException;不能把它们当成相同类型的计算。

特殊浮点值仍参与运算保存独立卡片。

原书依据 · 1 处
性能

浮点与整数操作的测量结果因操作类型和平台而异。

基准数据解释理论成本边界关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处

手动内存分配

自动存储对象和动态分配对象有不同的生命周期责任,示意地址不是语言保证。

指针对象与动态内存寿命分开

03175中ar1和ar2是局部指针对象,malloc返回的内存对象有独立生命周期;函数f的局部temp结束时不再有效,但它复制到inner指向的缓冲区的数据可随该缓冲区继续存在。代码没有检查malloc失败,也没有free两块分配,不能当作完整资源管理范例。

03176的地址和03177的栈向下、堆向上只表示一种平台布局;C语言不保证所有局部变量实际放栈、地址按这种方向增长,栈溢出也不必表现为覆盖堆。递归层数及故障位置受环境、编译优化等影响。

03179每轮把新分配结果赋回s而未释放旧对象,丢失旧分配地址造成泄漏;malloc失败没有检查,空字符串时n−1也不安全。代码实际将abcdef变为bcdefa,注释所说fabcde方向不一致。书中历史内存占用只是作者报告,未执行这些程序。

指针对象与动态内存寿命分开保存独立卡片。

原书依据 · 1 处

选择一门编程语言

语言选择涉及内存管理、执行方式与类型检查,也必须结合实际实现和任务。

语言取舍不能只按执行方式

自动垃圾收集能管理部分不再可达对象,手动内存管理要求程序明确对象所有权和释放;文件、连接等非内存资源仍需明确关闭。类型检查、运行时行为和性能都是选择因素,但各自解决的问题不同。

书中把Java字节码概括为解释执行、认为编译代码每次更快,是过于简化的历史描述:具体运行时可以使用即时编译等技术,性能受实现和负载影响。静态类型也不能消除所有缺陷,动态类型程序同样可以使用静态分析;不把语言类别直接等同可靠性或速度结论。

语言取舍不能只按执行方式保存独立卡片。

原书依据 · 1 处

参考文献

本章列出模式、算法领域、浮点和算法设计等参考文献。

第二部分

第二部分列出排序、查找、图、寻路、网络流与几何等算法章节。

第4章 排序算法

排序把元素按比较或键的规则重新排列。插入、快速、堆、计数和桶排序以不同方式组织工作,稳定性、键范围、重复值及输入分布决定其适用性。

第四章开始讨论排序算法。

概述

排序预处理使与排序键一致的查询更容易,但收益需计入构建成本。

排序键决定可加速的查询

03180中的州名按末尾字母排序,因而以s结尾的条目可以集中查看;它不是按完整州名字典序排序,所以不能直接对完整名称做普通字典序二分查找。

排序可能让后续查询或范围操作更方便,但构建排序的时间、数据更新与查询次数都影响总体成本。书中从10项到1000项的人手时间估计只是说明,不是机器查询的性能预测。

排序键决定可加速的查询保存独立卡片。

原书依据 · 1 处
术语

排序结果须保持输入元素并符合比较顺序,区间端点和重复键应明确。

排序保持排列与有序两项性质

排序结果应同时满足两个条件:元素构成原输入的排列(包括重复次数),并按给定比较规则非递减。只检查有序而遗漏元素,或保留全部元素但顺序不对,都不能算正确排序。

同键元素在总序下相邻,但它们的原有相对顺序是否保留属于稳定性,需另行规定。长度n的半开区间可写[low,low+n),闭区间[low,low+n]则有n+1项;原文两个表示排印相同,不能按字面同时成立。

排序保持排列与有序两项性质保存独立卡片。

原书依据 · 1 处
表述

排序可以移动引用或移动定长记录,数据表示决定搬移与存取成本。

排序引用与搬移记录成本不同

03181的数组保存指向字符串的引用,排序可交换引用而不必每次复制字符串对象;03182将记录按固定长度s连续存储,第i条占B[i·s,(i+1)·s)。引用排序仍要求被引用对象保持有效,记录排序则要明确长度和终止符约定。

磁盘文件可存储偏移而非进程内指针,随机交换可能产生较多I/O;不能将内存比较次数直接等同外存访问成本。文本中某些满长度记录没有终止符,读取时不能假定它们都是以零结尾的C字符串。

排序引用与搬移记录成本不同保存独立卡片。

原书依据 · 1 处
可比较的元素

比较函数确定排序键的顺序;文本编码与人类排序规则是不同层次。

比较规则决定排序结果

cmp(p,q)约定负数、零和正数分别表示小于、等于和大于。复合记录可以只按某些键比较,比较相等不代表其他字段也相同;一致的比较规则需要满足算法所要求的顺序性质,并明确大小写、区域和特殊值。

字符编码用于表示文本,排序规则则决定比较顺序;大小写、重音等可能需要特定排序规则。原文称UTF-16每个字符都用4字节不准确:Unicode官方说明其以16位代码单元表示,某些码点需一个单元,补充码点需代理对两个单元。见Unicode UTF-16 FAQ,2026-11-06核验。

浮点NaN也不能直接满足普通小于、等于、大于三选一的直觉,需要比较器或输入契约明确处理。

66明确后续统一通过cmp比较输入,输入要么是连续值记录,要么是指向对象的指针数组。选择实现时仍需确认比较函数的顺序性质、被引用对象寿命与具体算法的索引边界。

比较规则决定排序结果保存独立卡片。

原书依据 · 2 处
稳定排序

稳定排序保留比较相等记录的原始相对顺序,可用于组合排序键。

稳定排序保留同键先后

若两个记录在比较键上相等,稳定排序保证它们在输出中的先后与输入一致。不稳定排序只是没有这个保证,某次输出仍可能碰巧保持顺序。

03183先按起飞时间排列,再稳定按目的地排序;同一目的地组内保留先前的时间顺序。此技巧要求第一次顺序和第二次比较键明确,若需要按更多字段排序还要定义相应优先级。

稳定排序保留同键先后保存独立卡片。

原书依据 · 1 处
分析技术

比较排序可用决策树分析最坏比较次数,结论依赖比较模型和输入范围。

比较排序下界来自排列区分

对n个互异元素,比较排序必须区分n!种可能排列。二元比较决策树高度h最多容纳2^h个叶子,因此最坏比较次数至少ceil(log₂(n!)),增长为Ω(n log n)。03184展示四元素24种排列的决策树,最长路径需要5次比较。

原文把下界写成“至少O(n log n)”容易与上界符号混淆,应写Ω;又把树高误解释为存在一条最短路径的长度。平均情况的Ω(n log n)还需要指定如所有排列等概率的模型,不能仅凭最坏树高证明任意分布下的期望。计数、基数等使用额外键结构的算法不受纯比较模型下界的直接限制。

比较排序下界来自排列区分保存独立卡片。

原书依据 · 1 处
通用输入

本章后续算法假设输入在内存中,元素由连续值或指针数组表示。

比较规则决定排序结果关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处

插入排序

插入排序保持已处理前缀有序,逐个将未处理元素插入合适位置。

插入排序维护有序前缀

初始时单个元素构成有序前缀;每轮暂存下一个元素,将前缀中比它大的元素右移,再将暂存值放入空位。前缀扩展一位后仍有序,循环结束得到完整排序。

03187示意把7插入1、4、8、9、11、15之间;03188展示16个元素各轮变化,书中统计60次移动。原文称前缀“严格有序”不适合含重复键的输入,这里应理解为非递减。相等元素不被右移时,稳定性得以保留。

68指出近有序输入通常需要较少移动,小数据也可能受益;具体阈值需按机器、语言、比较与搬移成本测量,不能将一个固定n视为普遍边界。

71以16项例子的60次移动说明工作量;有序输入每轮仍需检查但不右移,互异逆序输入每个新元素需跨过此前全部元素。近有序的具体成本取决于逆序对和比较方式,不能仅凭口头“接近”给出固定次数。

插入排序维护有序前缀保存独立卡片。

原书依据 · 3 处
使用环境

插入排序常适用于较小或近乎有序的数据,但规模阈值依环境和元素而异。

插入排序维护有序前缀关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处
驱动因素

原地插入排序仍需保存当前元素,引用和完整记录的暂存开销不同。

原地排序仍需要暂存元素

将当前元素从数组位置移开前,需要保留它的值或引用,才能在右移后填回。对指针数组,暂存一个指针通常是常数个机器字;对固定宽s字节的记录,暂存空间需要容纳s字节。原地排序通常指额外空间不随元素个数n增长,不意味着零辅助存储。

元素比较和数据搬移可以用回调与块移动实现,但接口必须明确记录大小、比较器语义、内存可写和失败行为。

原地排序仍需要暂存元素保存独立卡片。

原书依据 · 1 处
解决方案

两份C实现分别暂存指针和记录,通过严格大于比较移动前缀。

插入实现需处理临时空间失败

03189的sortPointers暂存ar[j]指针,并在cmp(ar[i],value)>0时逐项右移;相等键不跨越,因此按比较器相等语义稳定。03190–03191的sortValues先分配s字节saved,找到插入位置后用memmove搬移重叠区,再复制暂存记录。

值版本未检查malloc(s)是否返回NULL,后续写saved可能出错;void*上直接按字节做base+j*s算术是某些编译器扩展,不是标准C的可移植指针算术,应先转换为字符指针并检查大小乘法溢出。函数返回void也无法报告分配失败。

输入指针、长度、元素大小和cmp的有效性均需接口约定;这些是静态阅读结论,没有编译或运行原程序。

插入实现需处理临时空间失败保存独立卡片。

原书依据 · 1 处
结论

有序输入无需大规模右移,逆序互异输入需要最多的插入移动。

插入排序维护有序前缀关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处
分析

最好线性、随机排列平均二次和互异逆序最坏二次,块移动改变常数但不消除位移总量。

插入排序移动量由逆序对决定

标准稳定插入排序每次把较大的前缀元素右移一位;右移次数等于输入中严格逆序对的数量。互异逆序输入有n(n−1)/2对,均匀随机排列的期望为n(n−1)/4;已有序输入为0次右移,但仍有线性轮次和比较。

03192比较逐项移动与块移动在历史平台上的时间;memmove可改善复制常数,但最坏移动的字节总量仍随n²增长。实验中若每个元素占s字节,成本分析也应保留s;n加倍耗时接近四倍只能支持观察范围,不能单独证明渐近界。

重复键通常减少严格逆序对,但“唯一基于比较的排序算法”明显不对,本章后续还有快速排序和堆排序;已有序输入也并非现实中没有价值。

插入排序移动量由逆序对决定保存独立卡片。

原书依据 · 1 处

中值排序

中值排序先选择真实中值,再按中值分割并递归排序两个半区。

中值排序以选择换取平衡

在闭区间内选择按秩位于中间的元素,将它放到中间位置,再交换两侧不符合中值分界的元素,递归排序两边。图示选择和分区使子数组大小大致均衡;重复值需按秩和一致的比较约定处理。

平衡递归本身不保证总耗时为 O(n log n):每层还要计入选择中值的代价。若每个子问题能在线性时间选择并分区,则总时间为 O(n log n)。

76中C实现以子区间长度的一半作为相对秩调用selectKth,随后递归处理两侧;选择完成时分界已建立。示例保存了返回索引me但没有再用它,递归边界直接从left与mid计算;正确性依赖selectKth确实把目标秩放到该位置。

77指出精确寻找中值有额外开销;随机选枢轴的快速排序可避免每次求精确中值,但随机化不能保证每次平衡,也不能单独排除重复键造成的退化。

78称平均 O(n log n) 与最坏 O(n²);需要区分一次partition的线性扫描与selectKth多轮最坏二次。精确中值排序若每次选择最坏线性则整体最坏 O(n log n),而书中给出的四元组代码及等值分区不足以直接支持这一结论。

中值排序以选择换取平衡保存独立卡片。

原书依据 · 4 处
使用环境

分区返回中枢最终索引,选择算法只在包含目标秩的一边继续。

分区将中枢放入最终秩

实现先把中枢交换到右端,扫描其余元素,将小于等于中枢者移到左侧,最后把中枢放到 store。返回 p 后,[left,p) 的元素均小于等于中枢,(p,right] 均严格大于中枢。分区只保证局部分界,并不保证两侧各自有序。

图中 pivot=6、p=5;若需要升序第八个元素,目标仍在右边,变成该右子区间的第2个。书中将其称作第八大,但该比较方向和示例对应第八小。

分区将中枢放入最终秩保存独立卡片。

原书依据 · 1 处
快速选择维护相对子区间的秩

在闭区间 [left,right] 寻找第 k 小,k 从1开始。分区返回 p 后,中枢相对秩为 p−left+1;若目标更小则保留 k 并搜索左区间,若更大则搜索右区间并令 k 减去该相对秩。函数返回的是数组索引,不是元素值。

这个换算在 left 不为零时不可省略。调用者应保证区间有效且 1≤k≤right−left+1;示例代码没有显式验证。随机中枢对互异元素可得到期望线性选择时间,但分区把等值全部放左侧,所有键相等时仍可能每次只缩小一项,导致二次时间。

75指出可将尾递归改写为循环:每轮分区后更新 left、right 和必要时的 k,命中目标后返回索引。这样可避免递归栈增长,但不会消除重复键导致的分区退化。

快速选择维护相对子区间的秩保存独立卡片。

原书依据 · 2 处
驱动因素

选择算法的尾递归可以用循环替换,同时保持区间和相对秩更新。

快速选择维护相对子区间的秩关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处
解决方案

选择算法返回时已经分区,中值排序无需重复执行示意图中的交换步骤。

中值排序以选择换取平衡关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
结论

平衡子问题的收益必须与获得真实中值的额外成本一起评估。

中值排序以选择换取平衡关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
分析

中值排序的成本取决于选择算法;书中四元组实现的线性最坏界不能由所列论证直接得到。

中值排序以选择换取平衡关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
最坏线性选择需要可靠分割

标准中位数的中位数选择将元素分成五个一组,选各组中位数,再递归求这些中位数的中位数作为枢轴。互异键下,足够多元素位于枢轴两侧,可得到 T(n)≤T(⌈n/5⌉)+T(7n/10+O(1))+O(n),因此最坏线性。含重复键时需采用能排除整个等值区间的分区等措施,才能保留相应保证。

书中改用四元组并声称最坏线性;即使按正文声称的分界,直接递推也只有 T(n/4)+T(3n/4)+O(n),不能由此证明线性。图中代码递归取多层组中值,与精确选出所有组中值的中位数也不是同一过程,因此不能直接套用正文的分界证明。书中时间表只说明特定机器、输入和实现的观察,不能证明渐近上界。

最坏线性选择需要可靠分割保存独立卡片。

原书依据 · 1 处

快速排序

快速排序按枢轴分区并递归排序两侧,不必每次求真实中值。

快速排序递归处理分区

选择枢轴并将其放到最终位置;左侧不大于枢轴,右侧不小于枢轴,再独立排序两个子区间。具体不等号由分区实现决定,书中代码把等值放左侧。图中首次选2得到1和14个元素,另一次选择中值附近元素则较平衡。

均匀随机枢轴在互异键下有期望 O(n log n) 时间,最坏仍为 O(n²);分区质量和重复键处理决定实际性能。图中的原地交换一般不保持相等元素的原始顺序。

80指出一侧为空而另一侧只少一个元素时,递归总工作量为二次。选择多个样本的中位数可改善通常的分区质量,但增加采样成本,不能无条件保证最坏情况。

82强调实践中的快速排序及其优化;具体性能需要与数据结构、输入分布和替代算法在同一环境下比较,不能把书中历史结论视为对所有工作负载的保证。

83分析:若每次均等分区,线性分区成本加上两半递归得到 O(n log n);若持续只排定一个元素,递推 T(n)=T(n−1)+O(n) 得到 O(n²)。随机策略的期望复杂度与每次恰好平衡是不同命题。

快速排序递归处理分区保存独立卡片。

原书依据 · 4 处
使用环境

每次只缩小一个元素时快速排序发生二次退化;多样本枢轴是成本与分区质量的权衡。

快速排序递归处理分区关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
解决方案

混合实现对小分区使用插入排序,阈值应结合具体运行环境评估。

混合排序在小分区切换算法

快速排序的递归区间较小时,可转用插入排序以减少递归与分区的固定成本;合适阈值取决于数据、比较成本、元素布局和环境,需要实测。03209按左右分区长度对应的下标差与minSize比较,左右子区间可能为空,插入排序接口需要允许空区间。

枢轴选择由外部函数提供,不能仅凭函数名保证其选择真实中值;交换式分区也不继承插入排序对相等键的稳定性。

混合排序在小分区切换算法保存独立卡片。

原书依据 · 1 处
结论

快速排序的实践性能依赖输入和实现,不存在普遍领先于所有排序算法的保证。

快速排序递归处理分区关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
分析

平衡分区递推为 O(n log n),持续极端分区则为 O(n²)。

快速排序递归处理分区关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
变种

优化包括枢轴采样、小分区插入排序、控制栈深,以及深度过大时转堆排序。

内省排序以深度限制兜底

先执行快速排序,给分区递归设置与初始规模对数成比例的深度预算;预算耗尽时对剩余区间切换堆排序,并可对小区间采用插入排序。快排部分每层总工作量为 O(n),层数受限于 O(log n),堆排序兜底提供最坏 O(n log n)。

三数取中和固定插入排序阈值只是经验优化,不单独保证最坏界。书中说只有使用BFPRT才可保证该界过于绝对,紧接的内省排序就是另一种办法。

内省排序以深度限制兜底保存独立卡片。

原书依据 · 1 处
快排优先处理较小子区间

分区后递归处理较小一侧,并以循环继续处理较大一侧,可使同时存在的递归层数为 O(log n):每一层递归的区间最多为上一层的一半。显式栈也可以先压入大区间、后压入小区间,使小区间先出栈;实现仍应检查栈容量。

栈空间控制与比较次数是不同问题,极端分区仍可能导致 O(n²) 时间。对于大量重复键,三路分区将小于、等于、大于枢轴的元素分组,再跳过等值区,可避免全等输入反复处理同一批等值元素。

快排优先处理较小子区间保存独立卡片。

原书依据 · 1 处

选择排序

选择排序每轮寻找剩余区间的最大值并交换到末尾。

选择排序减少交换但仍需比较

每轮在线性扫描中选出未排序区间的最大值,再把它交换到区间末端。n 个元素固定比较 n(n−1)/2 次,即使输入已有序也如此;交换次数至多 n−1,通常为 O(n),相比比较次数更少。

跨位置交换可能改变相等元素之间的先后次序,因此该实现不稳定。它有时适合写入比比较更昂贵的小规模场景,但是否有利仍需评估。

选择排序减少交换但仍需比较保存独立卡片。

原书依据 · 1 处

堆排序

最大堆是可按层序存入数组的完全二叉树;堆排序反复提取最大值。

最大堆用数组表示完全二叉树

最大堆满足两个条件:树是完全二叉树,且每个父节点不小于其子节点。根节点因此是最大值,但兄弟之间和不同分支不必有序。零基数组中节点 i 的左右子节点是 2i+1、2i+2,非根父节点是 ⌊(i−1)/2⌋;访问前需检查索引仍在堆区间。

自底向上对非叶节点下沉可建立堆;排序时把根与堆尾交换,缩小堆区间并下沉新根。循环不变量是前缀为最大堆,后缀已升序且不小于堆中的所有元素。

87指出堆排序不稳定;频繁交换大记录可能昂贵,但这不意味着不能对值类型排序。可按应用权衡直接移动值、交换指针或排序索引,并注意间接访问和额外存储成本。

88指出堆排序避开普通快排的二次最坏情形,但两者平均性能依环境而异。堆排序的最坏时间为 O(n log n),其缓存访问和比较搬移成本应与实际快排实现一起测量。

89的实现比较节点与存在的两个子节点,将较大者换到父位置并递归修复受影响分支;buildHeap从 n/2−1 递减到0,排序每次将堆顶换到末尾,再对缩短后的堆调用heapify。子节点索引是 int,极大输入需避免 2*idx+2 溢出。

最大堆用数组表示完全二叉树保存独立卡片。

原书依据 · 4 处
使用环境

交换式堆排序通常不稳定,数据搬移代价取决于记录表示。

最大堆用数组表示完全二叉树关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
驱动因素

快速排序与堆排序需要按实际工作负载比较,堆排序提供确定的渐近最坏界。

最大堆用数组表示完全二叉树关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
解决方案

heapify 从节点向下修复堆,建堆和排序阶段复用同一操作。

最大堆用数组表示完全二叉树关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
分析

一次下沉成本与高度有关,建堆整体为线性,后续提取阶段为 O(n log n)。

自底向上建堆是线性时间

底层节点数量多但高度小,上层节点数量少而高度大;将各层节点数乘以其最大下沉距离求和,可得自底向上建堆 O(n),而不是把每次调用都按堆的最大高度计费。随后 n−1 次取最大与下沉的总最坏时间为 O(n log n)。

零基实现对 n≥2 调用 ⌊n/2⌋ 次建堆下沉;书中把调用次数写成 ⌊n/2⌋−1,且将调用次数乘对数称作堆深度,均不准确。完全二叉树的高度是 O(log n)。

91的03216–03217表比较递归与非递归实现,在给定平台和随机测试下数值接近;实际差异应在目标环境测量,两者渐近上界相同。

自底向上建堆是线性时间保存独立卡片。

原书依据 · 2 处
变种

递归与迭代下沉在同一算法下有不同常数,历史表格不代表所有机器。

自底向上建堆是线性时间关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处

计数排序

已知有限键范围时,按键计数可以避免逐对比较。

计数排序利用有限键域

对 n 个整数且每个值属于 [0,k) 的输入,先分配 k 个计数桶并统计频次,再按桶序输出相应数量的值。时间 O(n+k),辅助空间 O(k);只有 k=O(n) 等条件下才能写成 O(n)。

若键域远大于数据量,初始化和扫描空桶的代价可能超过收益。比较排序下界只适用于比较模型;利用整数键直接索引使用了不同的信息和操作。

93说明使用有限全序的映射:对于正整数 p,1/p 随 p 增大而减小,若 p 在有效范围内,则可选择反向映射使桶序对应数值升序。实际使用应检查映射范围、重复键以及空间成本;该方法不是所有固定范围整数问题的无条件最佳选择。

94进一步强调桶序需要与所需全序一致;映射只作为分组标签而不保序时,直接按桶序输出会得到错误排序。

96正确指出输出写入总共 n 次,但遗漏 k 个桶的初始化与扫描,完整成本应为 O(n+k),而不是无条件 O(n)。

计数排序利用有限键域保存独立卡片。

原书依据 · 4 处
使用环境

计数排序要求键可映射到有限桶,映射顺序应符合目标排序顺序。

计数排序利用有限键域关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
驱动因素

键与桶的映射必须保序,才能按桶序还原所需结果。

计数排序利用有限键域关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
解决方案

示例直接重写整数值;计数分配和输入边界必须验证。

计数桶写入前验证键和容量

03219–03220先calloc k 个int计数器,以输入值索引并累加,再逐桶重写整数。安全实现需验证 k 和 n 非负、每个键在 [0,k)、分配成功且计数类型足以容纳频次;还应明确空输入与错误返回。示例声明返回 int 却未返回值,不能可靠报告成功或失败。

直接重写值只适合无需保留附属记录的情况;若需稳定排序完整记录,可用前缀和确定位置并按合适顺序写入输出数组,其额外空间应计入。

计数桶写入前验证键和容量保存独立卡片。

原书依据 · 1 处
分析

计数排序除输入扫描和输出外还要遍历 k 个桶。

计数排序利用有限键域关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
桶排序

桶排序按保序区间分桶,对每桶排序再顺序拼接。

桶排序依赖分布与保序映射

把元素分配到有序的桶,对每桶排序,再按桶序连接。正确性需要较早桶中的元素不大于较晚桶中的元素;普通散列函数通常不保序。桶内使用插入排序时,工作量与 Σni² 有关,ni 为各桶元素数。

独立均匀输入、n 个等宽桶的模型下期望总时间为 O(n),但所有元素落入同一个桶时仍可能达到 O(n²),因此书中图示和正文给出的无条件最坏线性不成立。桶数组及元素存储也需计入空间。

98称均匀分配时最快;性能结论仍取决于具体实现、分布和对照算法。保序是正确性要求,均匀分布主要影响桶内排序成本。

99强调存储与全序;全序并不自动提供高效均匀映射,实际还需考虑键分布、桶数组和桶内元素存储。

101在 n 个独立均匀分配到 n 个桶的模型下,E[ni]=1、Var(ni)=1−1/n,由 E[ni²]=Var(ni)+E[ni]² 得 E[ni²]=2−1/n。各桶期望平方和为 O(n),故桶内插入排序总期望 O(n);这是概率模型下的期望,不是每个输入的最坏保证。

桶排序依赖分布与保序映射保存独立卡片。

原书依据 · 4 处
使用环境

桶排序性能取决于映射成本、分布、桶数和桶内排序方法。

桶排序依赖分布与保序映射关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
驱动因素

全序本身不足以保证存在廉价、均匀且保序的桶映射。

桶排序依赖分布与保序映射关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
解决方案

示例链表入桶、逐桶插入排序并释放节点,需检查分配和索引。

桶排序实现须校验映射边界

书中对 [0,1) 数值用 floor(n*x) 分配 n 个桶,按桶拼接并对桶内元素插入排序。输入必须为有限数且满足 0≤x,桶数须有效,浮点计算及整数转换后也要检查桶索引;x=1、负数、NaN 或越界索引不能直接访问桶。

示例未检查 calloc 失败,也使用静态全局桶状态,因此不适合并发或重入;异常时应释放已分配节点。链表头插会颠倒同键记录的原顺序,即使桶内插入排序稳定,整体也未必稳定。

桶排序实现须校验映射边界保存独立卡片。

原书依据 · 1 处
分析

期望线性分析依赖独立均匀分配及桶内平方成本的期望。

桶排序依赖分布与保序映射关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
变种

前缀编码可构造保序桶,但短字符串和非法字符必须处理。

字符串前缀分桶需保序且校验

把至少三个小写拉丁字母组成的字符串前三字符按26进制映射到 0..17575,字典序不同前缀会落入有序桶,同前缀仍需桶内比较完整字符串。给定固定桶数,数据不断增长或高度偏斜时,桶内插入排序可退化到二次。

03227直接读取前三字节且假设字母在 a..z;短字符串、其他字符、编码规则或大小写顺序不符合假设时可能越界或破坏顺序,应验证并设计终止符及排序规则。

字符串前缀分桶需保序且校验保存独立卡片。

原书依据 · 1 处

选择排序算法的标准

排序算法选择需同时考虑输入形态、比较成本、空间和最坏情况。

排序基准须覆盖输入分布

排序方案应考虑规模、有序程度、重复率、键类型、稳定性、空间限制与最坏延迟。比较字符串可能需要读取多个字符,不能总按常数成本处理;近乎有序也需描述扰动的数量和距离。

基准应覆盖随机、有序、近有序及针对枢轴策略的不利输入,并在目标机器上测量。表中以插入、快排、堆和桶排序给出初步选择,但实际顺序取决于实现与输入。

104的字符串表比较随机、有序、三中值对抗和两类局部交换数据;03233–03234注明对抗数据中的三中值快排仅10次实验并去掉极值,其他通用描述为100次去掉极值。表中并未列出插入排序,因此不能直接从这些表验证文中对插入排序的速度说法。

105的03237–03241列出随机、有序、枢轴不利和两种局部扰动的双精度数据结果;应检查输入分布与NaN等排序规则,再在目标环境比较,不能把固定历史时间直接当成当前性能。

257在凸包排序中比较堆排序与快排;堆排序保证最坏 O(n log n),实际平均速度应在目标环境测试,不能绝对断言哪一种最优。

299的03466汇总排序算法;计数排序需计入键域k,桶排序期望性能依赖分布与桶内算法,二者都不能无条件写为最坏 O(n)。稳定性和更新需求也影响选择。

排序基准须覆盖输入分布保存独立卡片。

原书依据 · 5 处
综合分析基准测试结果

基准比较展示特定数据与实现的差异,而非普遍排序排名。

排序基准须覆盖输入分布关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
双浮点数的基准测试结果

浮点数据的比较成本不同,基准结论仍受分布和实现影响。

排序基准须覆盖输入分布关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处

参考文献

本章参考文献列出排序工程、选择算法及内省排序等资料。

第5章 查找

查找可以只判断存在、返回元素或读取关联值。顺序查找无需索引,二分查找利用有序数组,散列和树用额外结构换取不同的查询及更新成本。

第五章转向查找。

概述

查找需求可区分存在性、取回元素和关联键值,结构选择应计入维护成本。

查找结构按查询与更新权衡

存在性查询回答目标是否存在;检索查询返回匹配元素;关联查找由键获得附加信息。设计接口时应明确匹配规则、重复键行为以及未找到如何表示,避免把合法值与缺失哨兵混淆。

索引或排序可加速某些查询,但建立、插入、删除和额外空间均有成本;应按查询频率、更新频率、随机访问能力和数据量一起选择结构。

112指出无序链表头插在已持有头指针时为常数操作;尾插需有尾指针,删除给定值通常先线性查找,而已持有合适节点或前驱时删除成本可以不同。数组扩容与移动也要计入总体工作量。

120指出有序数组便于二分查找,插入和删除可能移动 O(n) 元素;动态树等结构可以调整更新与查询成本,但具体界依赖平衡策略和实现。

122指出磁盘数据也可以按偏移读取,但单次随机读取、缓存与记录长度影响延迟;页式索引等结构可能减少外部存储访问,不应只比较内存中的比较次数。

130强调需要结合输入的静态或动态性质选择存储结构;查找快慢还要包括冲突处理和容量管理。

301与03468–03469图算法表强调优先队列及结构操作成本;二叉堆可取最小,但一般成员查询是线性时间,可额外维护索引或使用其他结构。不存在仅凭选择数据结构就使任意问题达到 O(n log n) 的普遍保证。

查找结构按查询与更新权衡保存独立卡片。

原书依据 · 6 处

顺序查找

顺序查找逐项检查,找到目标即停止或遍历完整集合。

顺序查找无需预先建立索引

从集合起点逐个检查元素,匹配时返回,迭代结束仍未匹配则报告不存在。它适用于小集合、单次查找或只有顺序访问的输入;代价最坏为 n 次比较,首次命中为常数,未命中必须检查所有元素。

多次查找时,排序或索引可能降低查询成本,但还要考虑构建和更新开销;比较单个元素本身的成本也可能不恒定。

110的图03242分别给出数组和迭代器版本,均在找到相等元素时返回true,耗尽后返回false;空集合自然返回false。

111指出仅能顺序遍历时适合顺序查找;如果允许额外构建索引或缓存,后续查询仍可能有其他方案,取决于访问和更新约束。

113展示Ruby、Java和C实现:Ruby使用each与==;Java调用元素equals,若元素为null会抛异常;C以比较函数返回0代表相等,示例中的ar与n需由上下文提供。

115在目标必定存在且每个位置等可能的前提下得到 (n+1)/2 次比较;有未命中概率时还要计入每次 n 次比较。最好首次命中 O(1),最坏 O(n);03248为特定实验的历史时间。

顺序查找无需预先建立索引保存独立卡片。

原书依据 · 5 处
输入/输出

顺序查找可通过数组索引或迭代器访问,输出可为布尔存在性。

顺序查找无需预先建立索引关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
使用环境

无法随机访问或没有可利用的结构时,顺序查找提供通用方案。

顺序查找无需预先建立索引关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
驱动因素

小集合或低查找频率下,索引维护成本可能超过查询节省。

查找结构按查询与更新权衡关联本项背景,实质主要讲解在对应位置。

原书依据 · 6 处
解决方案

不同语言的顺序查找共享逐项匹配逻辑,空值和比较接口需约定。

顺序查找无需预先建立索引关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
结论

空槽和缺失值应有明确语义,哨兵不能与合法键混淆。

哨兵值必须排除合法输入

集合包含空槽时,查找可跳过空槽,或使用保证不与合法目标匹配的哨兵。选择哨兵前必须确认输入域不包含该值,并明确空值本身能否作为可查找元素;否则会漏报或误报。

03246的Ruby示例先过滤nil,因此即使目标为nil也不会匹配;书中注释指出Ruby可直接比较nil,是否需要过滤取决于接口语义,而非性能断言。

哨兵值必须排除合法输入保存独立卡片。

原书依据 · 1 处
分析

命中位置均匀时平均比较次数为 (n+1)/2,未命中为 n。

顺序查找无需预先建立索引关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
变种

可根据访问局部性重排元素,但移动成本和顺序语义必须纳入。

自组织查找权衡局部性与移动

查找成功后移到表头适合近期命中可能再次命中的访问;交换到前一位减少每次移动但适应较慢;预计不再访问时可移到末尾。收益取决于请求分布,数组整体移动可能需 O(n),并可能破坏原有顺序或影响并发读者。

自组织查找权衡局部性与移动保存独立卡片。

原书依据 · 1 处

二分查找

二分查找利用有序数据,在每轮比较后排除一半候选。

二分查找保持候选区间

对按同一比较规则升序排列且可随机访问的数组,维护闭区间 [low,high];比较中点与目标后,匹配则返回,目标较小保留左半区,较大保留右半区,直到 low>high 表示不存在。每次未命中至少排除中点及一侧,最坏 O(log n) 次比较。

避免固定宽整数中 low+high 溢出,可在合适范围约束下使用 low+(high−low)/2。含重复键时普通命中并不保证返回首个或最后一个位置。

118要求集合按键有序;键可比较本身并不意味着数组已排序,查找比较规则也必须与排序规则一致。存在性接口不规定重复键返回哪一个。

119的对数结论计数的是比较次数;若访问中点或比较本身不是常数,实际时间需要加上相应成本。

121图03250的Java实现以compareTo判断方向;其 (low+high)/2 在大型索引上可能整数溢出,且仅拒绝null目标,集合中null元素能否比较仍需约定。实现Comparable接口本身不能保证调用者正确维护一致的顺序。

123的精确比较次数表述漏掉边界:例如 n=1 时最多一次比较,而 log₂1=0。对 n>0,常见闭区间实现最坏次数为 ⌊log₂n⌋+1;03251–03252是内存与磁盘条件下的历史实验,倍率不宜泛化。

二分查找保持候选区间保存独立卡片。

原书依据 · 5 处
输入/输出

查找键需按同一全序排列,二分过程才能可靠排除半区。

二分查找保持候选区间关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
使用环境

有序随机访问数组上的二分查找最坏需要对数次比较。

二分查找保持候选区间关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
驱动因素

静态有序数组查询高效,但动态插入删除可能需要移动元素。

查找结构按查询与更新权衡关联本项背景,实质主要讲解在对应位置。

原书依据 · 6 处
解决方案

Java二分示例使用compareTo并在闭区间内推进边界。

二分查找保持候选区间关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
结论

磁盘随机访问的成本可能主导二分查找,存储布局影响总延迟。

查找结构按查询与更新权衡关联本项背景,实质主要讲解在对应位置。

原书依据 · 6 处
分析

每轮折半保证对数比较次数,精确界需处理终止和取整。

二分查找保持候选区间关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
变种

未命中时插入位置由最终边界确定,动态更新和外存可选其他索引。

二分插入点来自收敛边界

闭区间二分查找未命中并以 low>high 结束时,low 是保持升序的插入位置。不能直接使用最后一次中点 ix:例如查找比全部元素大的值,最后中点为 n−1,但插入位置为 n;空数组也没有最后中点。

若存在重复键且需要首个不小于目标的位置,应使用明确的 lower_bound 变种,而不是遇到相等即返回。数组插入仍可能移动 O(n) 元素;平衡树和页式 B 树适合不同的更新与存储访问需求。

二分插入点来自收敛边界保存独立卡片。

原书依据 · 1 处

基于散列的查找

散列表将键映射到桶,冲突需要保留并检查候选元素。

散列查找以桶缩小候选集

先计算键的散列并映射到桶,再在桶内查找满足相等关系的元素。链地址法允许多个键映射到同一桶;相等键必须产生相同散列,但相同散列不代表键相等,仍需比较。

若 n 个元素、b 个桶且分布均匀,平均链长为负载因子 α=n/b;计算散列和比较的成本也应计入。散列糟糕或敌对输入可让单条链增长到 n,最坏查找 O(n)。

126说明原集合不需排序,映射到空桶可直接判定不存在;非空桶需要按键相等规则逐项核对,查询和插入必须使用一致的散列与相等关系。

127以31进制多项式字符串散列、262143个桶和213557个单词举例;03258显示空桶116186个,非空桶为145957个,平均每非空桶约1.46项。图03257中缓存值为0时重新计算,真实哈希为0也会重复计算。

03256–03257展示的Java字符语义是char值及32位整数运算,并非一般UTF-8字节;完美散列只保证针对指定键集合无冲突,未知键仍需验证。原文大小与指针字节数为历史平台假设。

128将均匀散列的平均查找描述为 O(1);需要负载因子受控、散列与相等比较成本有界。动态扩容的平均成本、冲突链节点及对象布局也应计入;历史4字节指针和内存估算不能套用所有运行时。

131将固定词表中字符串最长长度视作常数;若键长随输入增长,散列与相等比较应显式计入键长,而非无条件 O(1)。均匀散列、负载因子有界且操作成本受控时,链式查询期望 O(1+α),集中冲突最坏 O(n)。

03264标注的部分负载因子与正文 n=213557、α=n/b 不符,例如 b=262143 时约0.815而非3.5;表格不可直接当作该定义的计算结果。扩容也带来重散列成本,03263和03265展示特定实验的查找与构建权衡。

散列查找以桶缩小候选集保存独立卡片。

原书依据 · 5 处
输入/输出

链式散列查找只需检查映射到的桶,空桶立即返回未找到。

散列查找以桶缩小候选集关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
使用环境

字符串散列示例展示键分布和链式冲突处理,但数据及内存数字依赖环境。

散列查找以桶缩小候选集关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
驱动因素

散列表开销包括桶、节点、键对象和负载因子,并受实现与输入分布影响。

散列查找以桶缩小候选集关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
解决方案

Java示例用链表解决冲突,但负散列转索引存在最小整数边界。

散列取模须处理最小整数

Java的余数可以为负。03262试图通过 h=0−h 把负hashCode变正,但 Integer.MIN_VALUE 取负后仍是自身,余数可能仍为负,导致数组越界。应在正桶数前提下用 Math.floorMod(h, tableSize) 等明确得到非负索引;还要保证键的equals和hashCode一致。

示例对空桶返回false,非空桶用contains核对元素;构造和查找必须使用相同映射。

散列取模须处理最小整数保存独立卡片。

原书依据 · 1 处
结果

查找性能依赖散列策略、容器结构和输入数据的动态特征。

查找结构按查询与更新权衡关联本项背景,实质主要讲解在对应位置。

原书依据 · 6 处
分析

散列查找需分别计入散列计算、桶访问和冲突检查。

散列查找以桶缩小候选集关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
变种

开放定址通过探测序列解决冲突,扩容和删除处理影响正确性与性能。

开放定址依赖探测与删除规则

开放定址将元素放入桶数组的槽中;查找沿与插入一致的探测序列前进,遇到从未使用的空槽才可判定不存在。删除不能简单地把已使用槽改为从未使用,否则会截断后续元素的探测链;可使用删除标记或合适的回填策略。

线性探测可能产生聚集,二次探测需要参数和表容量满足覆盖要求;容量接近满时探测成本上升。书中探测次数公式是特定均匀散列模型下的期望界,不是所有实现的最坏界;最坏可扫描 O(b) 个槽。扩容需重新映射元素,并把一次性成本与摊销成本区分。

开放定址依赖探测与删除规则保存独立卡片。

原书依据 · 1 处
完美散列只保证固定键集无冲突

静态键集可先构建无冲突的散列结构,例如两级方案:主表将键分组,针对每组构造无冲突的二级表。预处理和空间需要单独计入;对于不在原集合中的查询,仅得到一个槽位并不能证明存在,仍需核对实际键。

完美散列针对指定集合,不自动适用于后续任意插入,也不意味着任意散列函数无碰撞。

完美散列只保证固定键集无冲突保存独立卡片。

原书依据 · 1 处

二叉查找树

动态集合可以使用查找树,但未平衡的二叉树不保证对数性能。

二叉查找树用键约束子树

每个节点的左子树和右子树按键分别位于节点两侧;重复键应约定放置规则或单独计数。查找沿比较结果向左或向右,成本与树高成正比。平衡时高度 O(log n),按有序键依次插入普通树可能退化为链,高度 O(n)。

二叉查找树的节点可以只有一个子节点或没有子节点,书中“每一个内部节点都有两个子节点”不是普遍要求。

134指出元素可含多个属性并选其中键进行查找;若键不唯一,需定义覆盖、计数或返回多个元素等语义。

135图03267平衡例子与03268链状例子含相同键,结构不同导致查找路径不同。书中“每个节点恰有两个子节点”既排除了叶子也不足以定义高度平衡;满二叉树、完全二叉树与高度平衡各有不同条件。

二叉查找树用键约束子树保存独立卡片。

原书依据 · 3 处
输入/输出

树节点以可比较的键区分,接口需明确重复键和返回值语义。

二叉查找树用键约束子树关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处
使用环境

普通二叉查找树可能因插入顺序退化;平衡形状不能仅由每个节点孩子数定义。

二叉查找树用键约束子树关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处
驱动因素

平衡二叉树支持有序遍历并控制高度,父指针不是遍历的唯一实现。

红黑树用颜色约束保持近似平衡

红黑树维持二叉查找树次序,并约束节点红黑颜色、黑色根与空叶、红节点不得有红子节点,以及每个节点到后代空叶路径上的黑节点数相同。由此树高为 O(log n),正确维护后的查找、插入、删除可达到 O(log n)。

AVL树要求每个节点左右子树高度差的绝对值不超过1,并非书中所述任意不同节点的子树高度相差不超过1。遍历可用递归或显式栈,父指针有助于某些后继操作但不是必要条件。

138称根节点必须为空,这是错误表述:非空红黑树的根是实际节点且按常规定义为黑色;空孩子可用共享黑色哨兵表示。颜色和父指针具体存储依实现而定,父指针并非理论必需。

139概括 O(log n) 操作:前提是正确实现并维持红黑性质;普通不平衡二叉查找树的最坏复杂度仍是 O(n)。

红黑树用颜色约束保持近似平衡保存独立卡片。

原书依据 · 3 处
解决方案

旋转改变局部指针结构但保持中序次序,插入后配合变色恢复红黑性质。

树旋转保持中序键顺序

左旋以 p 的右子节点 r 为新的局部根:r 的左子树成为 p 的右子树,p 成为 r 的左子节点,并更新相关父指针及必要时的整棵树根。旋转前后中序顺序相同,所以保留二叉查找树顺序;旋转本身不保证颜色性质,需配合重着色和进一步修复。

操作前必须存在右子节点;若实现没有父指针,也可通过递归返回新子树根或由调用方维护父链接。03270–03271查找比较目标与当前节点键,而非原文所说比较左子节点。

树旋转保持中序键顺序保存独立卡片。

原书依据 · 1 处
结论

平衡树需要维护附加状态,空叶哨兵与实际根节点应区分。

红黑树用颜色约束保持近似平衡关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处
分析

红黑树通过高度约束保证查找、插入、删除最坏对数时间。

红黑树用颜色约束保持近似平衡关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处
变种

外存索引可用高分支数的B树降低树高及页面访问次数。

B树用多路节点减少外存访问

B树将多个有序键和子节点引用组织在一个节点中,通过较高分支数降低树高,使一次节点访问可对应一个存储页。具体页大小、缓存、键分布及更新策略决定实际I/O;应结合范围查询和持久化需要选择索引。

普通二叉树适合内存中的有序操作,但“最好选择”取决于查询、更新、空间以及可用实现,不能一概而论。

B树用多路节点减少外存访问保存独立卡片。

原书依据 · 1 处

参考文献

本章参考文献列出平衡树、顺序查找和散列资料。

第6章 图算法

图用顶点和边表示对象及关系。深度与广度遍历回答可达性,最短路径比较路径代价,最小生成树则最小化连接所有顶点的边权;这些目标不能混为一谈。

第六章讨论图算法。

概述

图以顶点及顶点之间的关系表达多类结构。

图用顶点和边表达关系

图 G=(V,E) 以顶点表示对象、以边表示关系;应用可使用有向或无向、加权或无权模型。建模前要明确自环、平行边和权重语义,因为这些约束会影响表示和算法。

148区分单源最短路径、所有顶点对最短路径以及最小生成树。最小生成树针对连通无向加权图,连接所有顶点且总边权最小;图不连通时相应结果是最小生成森林。最短路径树与最小生成树目标不同。

图用顶点和边表达关系保存独立卡片。

原书依据 · 2 处
图

邻接表和邻接矩阵表达同一图,但空间、操作和边的表示方式不同。

邻接表与矩阵权衡稀疏性

邻接表按顶点保存出边,空间 O(V+E),遍历一个顶点的邻边与其度数相关;邻接矩阵占 O(V²) 空间,可在 O(1) 时间检查指定位置,但遍历所有候选邻点需 O(V)。无向图的邻接表通常保存两个方向,矩阵则对称。

若用0表示无边,就不能同时不加区分地表示权重为0的边;需要单独存在标记或不同哨兵。带方向的关系、重复边与权重范围也须明确。

145指出矩阵无论有多少边都需要 V² 个位置,邻接表可节省稀疏图空间。邻接项排序或压缩为连续范围可能加速某些存在性查询并减少存储,但插入删除更复杂;具体成本依数据结构而定。航班频次不等同于不同机场对数,不能据此严格计算矩阵稀疏度。

147图03281的接口包括建图、加载、查询边与权重、迭代邻接点、增加和删除边。无向图若以双向邻接项表示,更新时必须同时维护两侧;顶点范围、重复边和删除不存在边的行为需约定。

邻接表与矩阵权衡稀疏性保存独立卡片。

原书依据 · 3 处
连通要求路径而非直接边

无向图连通指任意两个顶点之间存在一条路径,不要求二者直接有边;任意两顶点都有直接边称为完全图。有向图还需区分强连通和忽略方向后的弱连通。

超图的边可以连接任意数量的顶点;同一顶点对有多条边通常称为多重图,而非超图的定义。

连通要求路径而非直接边保存独立卡片。

原书依据 · 1 处
存储问题

稀疏图的矩阵空间为平方级,邻接组织方式应按查询和更新权衡。

邻接表与矩阵权衡稀疏性关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处
图分析

比较图算法时应将顶点数、边数和图密度都保留在复杂度中。

图算法复杂度同时依赖顶点边数

邻接表配合堆的某些算法可为 O((V+E) log V),矩阵版本可为 O(V²+E)。当 E=Θ(V) 时前者通常渐近更优;当 E=Θ(V²) 时后者的 O(V²) 优于前者的 O(V² log V)。交界量级约 E=Θ(V²/log V)。

稀疏通常指边数相对 V² 较少,并不必然意味着 E=Θ(V);图可能含孤立点或处在中间密度。大O只给上界,不应单凭两个上界断定实际速度。

165的03306–03308比较不同规模和密度的历史数据;Bellman-Ford支持负边,Dijkstra只适用于非负边。不同实验的次数不同,稀疏与稠密结果只能在各自条件下比较。

图算法复杂度同时依赖顶点边数保存独立卡片。

原书依据 · 2 处
数据结构设计

图接口应明确创建、查询和更新操作以及无向边的双向维护。

邻接表与矩阵权衡稀疏性关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处
问题

图算法问题包括单源和全对最短路径、生成树与遍历。

图用顶点和边表达关系关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处

深度优先搜索

深度优先搜索沿未访问邻边深入,完成后回溯并可记录时间和前驱。

深度优先搜索沿分支回溯

从起点将未访问顶点标为灰色,沿未访问邻边递归深入;处理完所有邻边后标黑并回溯。发现与完成时间以及前驱记录了搜索森林,邻边迭代顺序会影响具体树和时间。只从s运行访问s可达顶点;若还从其余白色顶点继续,得到覆盖全图的森林。

前驱链提供搜索树中的路径,但不保证边数或权重最短;森林其他根的前驱链也不通向s。递归实现还需要 O(V) 最坏调用栈,不能只计算颜色数组。

150说明每棵DFS树根的前驱为−1;有向图的遍历森林由顶点顺序决定,树根不是无向连通分量的通用替代。输入源点须属于图。

151强调DFS仅要求可遍历邻接点;完整空间包括颜色、可选前驱和时间数组以及最坏 O(V) 的递归栈。

153在邻接表下,完整森林遍历耗时 O(V+E):无向边通常以两个邻接项出现,仍只是常数倍。若用邻接矩阵逐行扫描,成本可为 O(V²)。

深度优先搜索沿分支回溯保存独立卡片。

原书依据 · 4 处
输入/输出

DFS输出的发现时间、完成时间和前驱可描述森林结构。

深度优先搜索沿分支回溯关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
使用环境

DFS只需枚举邻接点,但访问状态和递归栈仍随图规模增长。

深度优先搜索沿分支回溯关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
解决方案

DFS时间与颜色可用于边分类,需区分有向和无向图。

DFS颜色和时间用于边分类

在有向图DFS中,指向白色顶点的边成为树边;指向灰色祖先的边为后边;指向黑色顶点时,可结合发现时间区分指向后代的前向边和交叉边。前驱关系及时间区间依邻接顺序变化。

无向图中父边会从子节点再次被看到,不能仅凭灰色邻点就认定有环;应排除对应父边,多重边还需按边身份处理。递归深度可能达到 V,输入顶点必须有效。

DFS颜色和时间用于边分类保存独立卡片。

原书依据 · 1 处
分析

邻接表DFS在完整遍历时逐顶点和邻接项处理一次。

深度优先搜索沿分支回溯关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处

广度优先搜索

广度优先搜索按边数距离分层,队列保证先发现较近的顶点。

广度优先搜索按层发现顶点

从源点入队并标记,反复取出队首并将尚未发现的邻接点标记、记录前驱和距离后入队。这样每个顶点首次发现时的距离是源点到它的最少边数;前驱构成可达区域的最短路径树。不可达顶点保持无穷距离或其他明确标记。

这个结论适用于无权图或各边具有相同正权重的情况;不同权值下最少边数不一定是最小总代价。邻接表下时间 O(V+E),队列及状态空间 O(V)。

155指出dist[v]是边数最短距离,pred[v]是前驱;源点和不可达点都可能有pred=−1,因此应结合距离或访问状态判断可达。

156强调队列的空间开销,最坏可达 O(V);最短指经过边数最少,适用有向或无向图。

157正文称在栈中存储状态,但03290实际使用 queue:取front,处理邻点后pop,新顶点在push前标灰。该先进先出顺序对分层和最少边数保证至关重要;示例没有显式检查源点索引。

158分析每个顶点至多入队一次,扫描所有可达顶点的邻接项;加上全图初始化,在邻接表与常数时间队列操作下为 O(V+E)。邻接矩阵通常需要 O(V²) 扫描。

188把BFS应用于状态空间;在有限分支、每步相同代价且状态去重正确时,首次发现目标得到最少步数。开放集和闭合集都需要考虑重复状态;图03335的伪代码只查closed,开放集中仍可能存在重复项。

189将BFS输出称作开销最小;这需要每步相同代价,否则最少步数不一定最小成本,可考虑统一代价搜索等方法。

190提醒逐层搜索可能耗费大量时间和空间;可否寻找多个路径取决于是否保留多个前驱和具体目标,而非队列结构本身。

191图03338–03339只在出队后加入closed且生成时只检查closed,同一状态可能多次进入open;可在首次入队时记录已发现状态以避免重复,并保存该次最短前驱。

192强调队列空间;队列操作、状态复制、哈希和相等比较分别有成本,不能仅依据入队出队常数就忽略其他开销。

193以分支因子b和解深度d估计BFS边界可达 O(b^d),纯深度优先路径栈可为 O(bd);但若DFS维护全局闭合集,其总空间可能随已访问状态数增长,不能一概写 O(bd)。

广度优先搜索按层发现顶点保存独立卡片。

原书依据 · 11 处
输入/输出

BFS输出最少边数和前驱,不可达顶点保留缺失标记。

广度优先搜索按层发现顶点关联本项背景,实质主要讲解在对应位置。

原书依据 · 11 处
使用环境

广度优先搜索队列可能包含大量同层顶点。

广度优先搜索按层发现顶点关联本项背景,实质主要讲解在对应位置。

原书依据 · 11 处
解决方案

BFS示例使用先进先出队列,入队前标记避免重复加入。

广度优先搜索按层发现顶点关联本项背景,实质主要讲解在对应位置。

原书依据 · 11 处
分析

邻接表BFS的初始化、入队和邻接项扫描合计 O(V+E)。

广度优先搜索按层发现顶点关联本项背景,实质主要讲解在对应位置。

原书依据 · 11 处

单源最短路径

Dijkstra逐步确定到源点的最短距离,并松弛其出边。

非负权最短路贪心定案

对边权非负的图,维护每个顶点当前已知最短路径上界;每轮选取尚未确定且距离最小的顶点 u,将其距离定案,再用 dist[u]+w(u,v) 松弛出边。非负权确保尚未处理的路径不能让已定案顶点变得更短。

源点距离为0,不可达点为无穷;只有需要单目标时,可在目标以最小距离出队并定案后停止。负权边可能破坏该保证,应选择支持负边的算法并处理负环。

161图03292示例通过顶点2更新顶点3的距离为17;二叉堆取最小和decreaseKey各需 O(log V),完整邻接表实现常为 O((V+E) log V)。堆顶读取可为 O(1),但删除最小不是常数。03293–03294没有显式在最小距离为无穷时终止;使用无穷哨兵进行加法前须特别处理。

163比较邻接表加二叉堆 O((V+E) log V) 与每轮扫描顶点的 O(V²+E);若使用邻接矩阵扫描行,整体通常 O(V²)。图03299–03300直接遍历矩阵中的每个权重,必须约定无边哨兵并避免将其当成普通权重参与加法。历史平台的STL优化幅度不能直接推广。

非负权最短路贪心定案保存独立卡片。

原书依据 · 3 处
输入/输出

Dijkstra依赖非负边权并需要处理不可达与整数溢出。

最短路加法须检查无穷与溢出

计算候选距离前先判断起点距离是否为无穷,并检查有限距离加边权是否超出可表示范围;用更宽类型只有在确认其范围足够时才安全。C++有符号溢出不能靠事后检查 newLen≥0可靠检测,且负权本身也使这种检查无效。

Dijkstra标准正确性要求边权非负,包含零;负权会使结果不可靠,是否死循环取决于实现,不应一概而论。

162示例以long计算newLen,但long宽度依平台而定,结果写回int前仍需验证是否可表示;无穷哨兵也不能直接作为正常距离参与计算。

最短路加法须检查无穷与溢出保存独立卡片。

原书依据 · 2 处
解决方案

优先队列保存候选距离并在松弛时降低键值。

非负权最短路贪心定案关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处
结论

较宽的中间数类型可以扩大范围,但不替代可表示范围检查。

最短路加法须检查无穷与溢出关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处
分析

稠密图可线性扫描最小距离,避免堆操作。

非负权最短路贪心定案关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处
变种

Bellman-Ford允许负权,通过重复松弛并额外检查检测可达负环。

重复松弛检测可达负环

初始化源点为0、其余为无穷;最多进行 V−1 轮边松弛,每轮按 dist[u]+w(u,v) 改善 dist[v],若某轮无变化可提前停止。再检查一轮,如果仍可从有限距离继续松弛,说明存在从源点可达的负环;仅影响能从该负环到达的目标的最短距离。

无穷距离不能直接参与算术,尤其无穷加负权可能被误当成有限路径。图03302–03304未先检查不可达起点,不能可靠检测源点可达性;中间加法与写回也需检查范围。标准实现时间 O(VE),前驱可重建有限最短路径。

重复松弛检测可达负环保存独立卡片。

原书依据 · 1 处
可靠路径可用负对数转最短路

若各边成功事件相互独立且 0≤1,路径成功概率为各边概率的乘积;将每条边权设为 −log(p),最大化概率等价于最小化非负权和,可使用Dijkstra。p=0的边代表无法成功,可视为不可用或无限成本。

若故障存在相关性,边概率之积可能不成立,应使用能够反映联合概率的模型。

可靠路径可用负对数转最短路保存独立卡片。

原书依据 · 1 处
比较

最短路径算法应按边权、图密度及实现成本选择。

图算法复杂度同时依赖顶点边数关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处

所有点对最短路径

Floyd-Warshall以逐步允许中间顶点的动态规划求所有点对最短路。

全对最短路逐步放开中间点

设 Dk[i,j] 为只允许前k个顶点作为中间点的最短距离。每次允许顶点k后,更新 D[i,j]=min(D[i,j],D[i,k]+D[k,j]),外层循环必须是k;初始化对角线为0、已有边为权重、无边为无穷。维护前驱或下一跳可恢复路径。

时间 O(V³)、距离矩阵空间 O(V²)。可处理负边,但若某对路径可经过负环,则该对不存在有限最短距离;可借助最终 dist[k,k] 识别负环并传播受影响范围。

167把边权限制为正是书中示例假设,Floyd-Warshall本身允许负边,只要要报告的路径不受可达负环影响;无路径应以明确的无穷标记表示。

168的03310–03311先检查 dist[i][k] 非无穷,却未检查 dist[k][j];若允许负边,有限负数加无穷哨兵可误更新不可达路径,因此两段均需检查,并检查整数范围。03312沿pred回溯,正确前驱应可终止;损坏数据或负环时应限制步数并报告异常。

169的三重循环为 O(V³)。一次前驱回溯的成本与路径边数成正比;无负环下可选简单最短路径,最多 V−1 条边,因此常写 O(V),不是必须按所有 E 条边遍历。

全对最短路逐步放开中间点保存独立卡片。

原书依据 · 4 处
输入/输出

全对最短路距离矩阵区分不可达,并可通过前驱恢复路径。

全对最短路逐步放开中间点关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
解决方案

就地更新距离矩阵可节省空间,但无穷值相加和路径重建需保护。

全对最短路逐步放开中间点关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
分析

Floyd-Warshall三重循环为立方时间,路径重建与输出路径长度相关。

全对最短路逐步放开中间点关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处

最小生成树算法

Prim每步选择跨越已选顶点集的最轻边,逐步构建最小生成树。

最轻跨割边扩展生成树

在连通无向加权图中,从任意根开始维护已加入集合S;为每个未加入顶点记录来自S的最轻连接边,每次选择全局最轻的跨割边,将新顶点并入并更新候选。割性质保证这样的选择可扩展为最小生成树。

Prim比较单条连接边,不像Dijkstra比较从源点累计的路径距离;最小生成树可以包含负权边。断开图不能得到覆盖所有顶点的一棵树,需要分别处理连通分量形成森林。

171的03314–03315以inQueue标记顶点是否留在堆中,key[v]记录当前最轻连接边,并在改进时调用decreaseKey;堆实现仍需高效定位顶点才能保证对数更新。代码无条件写key[0],空图需单独处理。

172给出斐波那契堆 Prim 的 O(E+V log V) 摊销时间;它依赖相应堆操作的摊销界,常数和实现复杂性可能影响实际表现。稠密图上数组或矩阵 O(V²) 方案也值得比较。

173对无向邻接表的边扫描按两条邻接项计数,至多 O(E) 次键更新;加上各顶点的出队与堆操作得到 O((V+E) log V),前提是堆可高效定位并降低指定顶点的键。

最轻跨割边扩展生成树保存独立卡片。

原书依据 · 4 处
解决方案

Prim示例用堆与外部数组维护待处理状态和最轻连接边。

最轻跨割边扩展生成树关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
结论

不同优先队列影响Prim复杂度,但渐近改进不等于实际必然更快。

最轻跨割边扩展生成树关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
分析

二叉堆Prim的出队及边松弛总成本为 O((V+E) log V)。

最轻跨割边扩展生成树关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
变种

Kruskal按边权排序,使用不相交集避免形成环。

按边权连接不同分量

按权值非递减遍历边,若两个端点当前属于不同连通分量则加入该边并合并分量;同分量的边会形成环,应跳过。连通图得到最小生成树,不连通图得到最小生成森林。

排序通常占 O(E log E),配合路径压缩和按秩合并的不相交集,合并查找总成本近线性;简单图中 E≤V²,因此 log E=O(log V)。

按边权连接不同分量保存独立卡片。

原书依据 · 1 处

参考文献

图算法参考文献指向算法导论。

第7章 人工智能中的寻路

状态空间搜索把局面和合法行动变成图。广度、深度和A星采用不同的探索顺序;对抗博弈还要考虑对手回应,极小极大与剪枝共同组织有限深度决策。

第七章讨论人工智能中的寻路。

概述

状态空间用状态与合法转换表示搜索问题,博弈和单主体目标有所不同。

搜索从状态与合法转移建模

以初始状态为根、合法操作为边,按需生成后继状态;状态空间很大时无需预先展开全部节点。单主体搜索寻找通往目标的动作序列;交替对抗博弈还必须考虑对手可能选择的回应。

同一状态可能由多条路径到达,树形展开会重复计算;能否合并或缓存取决于状态是否完整记录轮次、历史与规则。

179以八数码的格局为状态、相邻滑动为动作,前驱链还原动作序列。树形展开不自动防止重复:不同动作序列可能到达同一局面,需明确开放集和闭合集的去重策略,以及状态键是否覆盖影响后续行动的全部信息。

181的Tiny-Puzzle用两个非负整数作状态,每次增加其中一个;不同动作顺序可抵达相同状态,说明去重必须根据状态而非路径文本决定。状态空间无限时,搜索终止与完整性需额外条件。

183指出输出可以是走法序列或存在性;复杂度记号应区分分支因子 b 与最大深度 d,原文把两者都写成d。

202列出迭代加深、状态缓存、层次化和内存限制等思路。缓存剪枝须记录与未来搜索相关的状态、剩余深度和成本;直接丢弃节点或做层次近似可能改变完整性或最优性,需按具体算法分析。

303的03470汇总搜索算法;解空间搜索可能指数增长,若已知排序、图或动态规划等直接方法,应比较其约束和成本。

搜索从状态与合法转移建模保存独立卡片。

原书依据 · 6 处
博弈树

博弈树将对手回应纳入决策,通过接口分离游戏规则和搜索。

对抗决策必须考虑对手回应

轮流行动的双人确定性完全信息游戏中,决策节点选择自己的走法,对手节点需要考虑对手所有合法回应;不能只找到一条自己获胜的路径,就断定能强制取胜。状态接口应提供终局判断、合法走法、复制或可逆更新及评估;搜索算法再基于这些接口选择走法。

有限深度搜索在非终局处依赖评估函数,结果只是该模型和深度下的估计;终局胜负和平局分值须与当前玩家视角一致。图03317–03318展示状态、玩家、走法和评估接口。

对抗决策必须考虑对手回应保存独立卡片。

原书依据 · 1 处
搜索树

搜索以状态、合法动作、目标与状态去重方式构造解路径。

搜索从状态与合法转移建模关联本项背景,实质主要讲解在对应位置。

原书依据 · 6 处
关键思想

搜索质量依赖完整状态表示、合法动作、启发式与深度限制。

状态键必须保留影响未来的信息

搜索状态不仅是当前可见局面,还须包含影响后续合法行动、目标或成本的历史信息;例如国际象棋王车是否移动过会影响王车易位。只有在变换保留目标、合法转移和成本时,才能安全地把对称状态合并。

启发式和走法顺序可以减少探索,但错误地丢弃可能通向解的分支会损失完整性;固定深度也可能看不到稍后的补偿或终局,即水平线效应。

186展示旋转棋面;只有目标、合法动作及代价在旋转下保持等价时才能合并。状态搜索也可用原位执行与撤销,博弈搜索也可复制状态,并非必然的实现分界。闭合集可能使DFS总空间远高于单纯栈的空间。

状态键必须保留影响未来的信息保存独立卡片。

原书依据 · 2 处
假设

同一状态可由多条动作序列到达,搜索结构可能是图。

搜索从状态与合法转移建模关联本项背景,实质主要讲解在对应位置。

原书依据 · 6 处

深度优先搜索

有限深度DFS以栈探索状态,但去重与深度限制的交互影响完整性。

限深搜索去重需保留剩余深度

深度优先搜索可使用栈保存待扩展状态,在深度上限内沿一条分支探索后回溯。对同一状态,较浅路径拥有更多剩余深度;若先从较深路径访问就永久标记为已访问,之后可能错误丢弃较浅路径,从而漏掉上限内的解。

可记录该状态已访问的最小深度,并在发现更浅路径时重新扩展;或使用当前路径上的循环检测,具体完整性取决于状态和成本约束。限深搜索找不到解只说明该限制下未找到,不证明全局无解。

184指出限深可控制探索范围;若实现保存全部闭合集,内存仍可能随访问状态数增长,而纯路径回溯的空间模型不同。

185的03324–03325从开放栈取状态后加入闭合集,但生成后继仅检查closed,尚未展开的重复状态可能同时进入open;而且首次深层访问会阻止之后更浅访问,可能漏掉限深解。初始状态等于目标会立即返回;代码先检测后继是否为目标再判断depthBound,边界语义需明确。

187以八数码例说明深层首次访问使浅层重访被闭合集抑制,甚至加大深度上限后仍可能找不到本可达到的解。03329–03332列出访问数和解长度,03334图及03328拟合仅描述实验范围;闭合集结构的查找成本也需计入。

限深搜索去重需保留剩余深度保存独立卡片。

原书依据 · 4 处
输入/输出

搜索输入为初始和目标状态,输出为可重建的动作序列。

搜索从状态与合法转移建模关联本项背景,实质主要讲解在对应位置。

原书依据 · 6 处
使用环境

深度上限控制搜索范围,但并不单独保证内存充足。

限深搜索去重需保留剩余深度关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
解决方案

示例以散列闭合集和前驱数据支持状态去重及路径恢复。

限深搜索去重需保留剩余深度关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
结论

搜索状态可复制或执行并撤销,是否合并对称状态取决于问题语义。

状态键必须保留影响未来的信息关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处
分析

限深DFS的访问量与走法顺序、去重和深度上限相关。

限深搜索去重需保留剩余深度关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处

广度优先搜索

单位代价搜索使用队列逐层扩展,首次发现目标得到最少步数。

广度优先搜索按层发现顶点关联本项背景,实质主要讲解在对应位置。

原书依据 · 11 处
输入/输出

最少步数只有在每步代价一致时才等同最小总成本。

广度优先搜索按层发现顶点关联本项背景,实质主要讲解在对应位置。

原书依据 · 11 处
使用环境

BFS在解深度较大时可能需要保存大量边界状态。

广度优先搜索按层发现顶点关联本项背景,实质主要讲解在对应位置。

原书依据 · 11 处
解决方案

示例用队列和闭合集记录状态,并通过前驱恢复动作。

广度优先搜索按层发现顶点关联本项背景,实质主要讲解在对应位置。

原书依据 · 11 处
结论

BFS队列操作可为常数时间,但保存与去重状态仍有开销。

广度优先搜索按层发现顶点关联本项背景,实质主要讲解在对应位置。

原书依据 · 11 处
分析

树搜索BFS的边界可能随解深度指数增长,DFS空间取决于去重策略。

广度优先搜索按层发现顶点关联本项背景,实质主要讲解在对应位置。

原书依据 · 11 处

A*搜索

A星以已走成本与剩余成本估计之和选择待扩展状态。

A星按已走成本加启发式排序

对待扩展状态使用 f(n)=g(n)+h(n),其中g是当前已知路径的实际累计成本,h估计到目标的剩余成本;从开放集中取f最小的状态扩展。不同边代价时g不能简单用深度代替。f小表示估计总成本较小,不等于该状态几何上更接近目标。

在非负边权、目标启发式为0、h不高估真实剩余成本等标准条件下,正确处理更优路径并在目标以最小优先级出队时终止,可得到最优解;若启发式不一致,图搜索通常需在发现更优g时重新开放状态。

195称估计接近就得到最优,这不充分:轻微高估也可能改变搜索顺序并得到次优解。需要结合不高估、目标值、代价模型及重复状态处理证明。

196的03341–03343展示两种评估函数在同一八数码例子中访问不同数量状态;更少扩展不自动证明最优或所有输入上更快。评估函数本身的计算成本也须计入。

198列举三种八数码评价函数与不同搜索规模。h=0时A星退化为统一代价搜索,只有等步长代价时才与BFS按成本层相对应。负启发值不一定破坏可采纳性,但目标通常需h=0,且具体最优性证明还依赖其他条件。

200的03349–03352展示不同十五数码状态:一个实例较快找到解,另一个耗尽给定内存。启发式不一定总能减少搜索空间;扩展数、计算成本、重复状态和内存都需结合目标工作负载评估。

203的03353–03356比较八数码实验,记录平均搜索规模、路径长度及限深失败次数。特定启发式与输入下A星扩展较少不代表所有实例均如此;经验拟合不能替代理论复杂度,随机移动次数也不一定等于最短解深度。

A星按已走成本加启发式排序保存独立卡片。

原书依据 · 6 处
输入/输出

启发式接近真实值并不足以单独保证最优,关键是满足可采纳性等条件。

A星按已走成本加启发式排序关联本项背景,实质主要讲解在对应位置。

原书依据 · 6 处
使用环境

启发式质量与计算开销共同决定实际搜索成本。

A星按已走成本加启发式排序关联本项背景,实质主要讲解在对应位置。

原书依据 · 6 处
解决方案

更优路径可能要求更新开放状态或重新开放已关闭状态。

图搜索发现更优路径要更新

A星应为每个状态维护已知最小g及前驱:发现更小g时更新开放集中的优先级;若该状态已关闭且启发式不一致,则重新开放。取出优先队列中已过期的条目时应跳过,或使用支持更新的索引堆。

03344–03345只检查closed并在更优时移除,未展示开放集中重复状态的统一更新;同一状态h固定时比较f等价于比较g,否则不一定。代码用深度表示g,适用于单位步长,不直接支持不同代价。

199称未知状态数时不能用二叉堆,这不成立:动态数组堆可以扩容;可用索引堆实现decrease-key,或插入新条目并在弹出时丢弃过期项。平衡树也是一种可选实现。

图搜索发现更优路径要更新保存独立卡片。

原书依据 · 2 处
结论

可采纳启发式不高估最优剩余成本,过高估计可能失去最优保证。

A星按已走成本加启发式排序关联本项背景,实质主要讲解在对应位置。

原书依据 · 6 处
驱动因素

开放集需要高效取最小与处理更新,可以使用动态扩容的堆。

图搜索发现更优路径要更新关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处
分析

启发式效果和内存占用高度依赖实例,实验不能保证一般复杂度。

A星按已走成本加启发式排序关联本项背景,实质主要讲解在对应位置。

原书依据 · 6 处
变种

IDA星反复进行有成本阈值的深度优先搜索,以空间换取重复计算。

IDA星逐步提高估计成本阈值

IDA*以 f=g+h 作为阈值进行限界深度优先搜索,下一轮阈值通常取本轮超过阈值的最小f;它并非单纯每轮增加搜索深度,也并非不使用启发式。可采纳启发式、合适的代价及终止条件下可获得最优解,通常节省开放集空间,但会重复扩展节点。

IDA星逐步提高估计成本阈值保存独立卡片。

原书依据 · 1 处
相关算法

内存限制、层次化和缓存是搜索优化方向,但需要维护各自的正确性条件。

搜索从状态与合法转移建模关联本项背景,实质主要讲解在对应位置。

原书依据 · 6 处

比较

搜索策略比较应同时记录扩展状态数、解质量、失败次数和资源限制。

A星按已走成本加启发式排序关联本项背景,实质主要讲解在对应位置。

原书依据 · 6 处

Minimax

极小极大搜索假设双方交替行动并分别选择对自己最有利的结果。

极小极大交替评估双方选择

以初始玩家为固定评分视角:轮到该玩家的MAX节点取子节点最大值,轮到对手的MIN节点取最小值,递归到终局或深度上限后评价。根节点选择能保证最佳最坏结果的走法。

这依赖双人、轮流、确定性、完全信息及零和等建模假设;有限深度时结果还受评估函数和截断影响,不是对真实胜率的无条件保证。

205说明返回的最佳走法由给定深度和评估函数决定;终局状态应按实际胜负处理,无合法走法是否表示终局也由游戏规则决定。

206图03358使用 b!/(b−i)! 的逐层递减分支模型,b=10、d=6得到187300个非根节点;若每层都固定有b个走法,则应使用 Σb^i,不能将两个模型混用。评估值需要从固定玩家视角一致地解释。

207的03359–03361实现复制根状态,递归中执行与撤销走法,并由比较器在MAX和MIN之间切换;撤销必须完整恢复状态,异常或提前退出也应保证恢复。

208图03362给出 Σ(i=0..d)b^i,b=30、d=5得到25137931个节点;缓存和对称性可能减少重复搜索,但缓存键必须包含行动方、深度及影响局面的规则信息。

209图03363展示深度2的井字棋搜索,完整展开有固定分支b、深度d时节点量为 O(b^d)。若某分支已不可能改善祖先可保证的结果,可通过正确的上下界剪枝而不改变同一搜索深度下的极小极大值。

210说可在树完全可处理时取消深度限制;游戏若存在循环,仍需终局规则或重复状态处理,不能只凭状态有限就保证朴素递归结束。

极小极大交替评估双方选择保存独立卡片。

原书依据 · 7 处
输入/输出

极小极大输入包括可行走法、状态评估和搜索深度。

极小极大交替评估双方选择关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
使用环境

博弈树规模取决于每层分支数,叶子评估需保持同一视角。

极小极大交替评估双方选择关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
解决方案

递归搜索可执行并撤销走法,交替选择最大和最小分数。

极小极大交替评估双方选择关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
结论

固定分支因子的完整树节点数随深度指数增长。

极小极大交替评估双方选择关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
分析

完整极小极大搜索的分支增长为指数级,可利用上下界剪枝。

极小极大交替评估双方选择关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
变种

有限博弈树可搜索至终局,但仍需处理循环和重复状态。

极小极大交替评估双方选择关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处

NegMax

NegMax利用零和对称性,把交替最大最小归约为取负后求最大。

零和博弈可用取负统一递归

零和游戏中当前玩家的价值等于对手价值的负数,因此每个节点可统一计算 max(−子节点值),递归时交换行动方。叶子评价必须始终采用当前行动方视角,并满足双方评分符号一致;不满足零和假设时不能直接套用。

同一深度与相同走法顺序下,不剪枝的NegMax和Minimax探索相同状态,只是表达方式不同。

212沿用Minimax的状态、合法走法、深度和最佳走法接口;叶子分数需与当前行动方视角相符。

213承接Minimax适用环境;游戏规则和评分需支持玩家间取负转换。

214的03365–03366代码以当前player评价叶子,递归交换player和opponent,撤销动作后比较−me.score。动作撤销需恢复全部状态,且终局处理应遵守游戏规则。

216的03367井字棋树与Minimax例子对照:递归中每层从当前行动方视角评分,父层对返回值取负并选最大,未剪枝时复杂度仍按分支和深度指数增长。

零和博弈可用取负统一递归保存独立卡片。

原书依据 · 5 处
输入/输出

NegMax输入输出与极小极大搜索相同,但评分视角不同。

零和博弈可用取负统一递归关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
使用环境

NegMax适用于满足零和视角转换假设的对抗搜索。

零和博弈可用取负统一递归关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
解决方案

NegMax执行动作后交换玩家递归,撤销动作并取子节点分数的负值。

零和博弈可用取负统一递归关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
结论

固定宽有符号整数的最小值取负可能溢出。

取负评分需避开整数最小值

Java int 范围是 −2³¹ 到 2³¹−1,因此 −Integer.MIN_VALUE 仍为 Integer.MIN_VALUE。NegMax反复取负时若用最小整数作负无穷会破坏比较;可选对称的有限哨兵、使用更宽类型并预留范围,或显式处理无穷值。所有实际评分也须落在约定范围内。

取负评分需避开整数最小值保存独立卡片。

原书依据 · 1 处
分析

NegMax与Minimax的未剪枝搜索量相同,差别在分数视角。

零和博弈可用取负统一递归关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处

AlphaBeta

AlphaBeta利用已知上下界剪除不影响根节点决策的分支。

上下界剪枝保留极小极大值

搜索维护当前路径上的α、β界:α是MAX方已能保证的下界,β是MIN方可限制的上界;当α≥β时,该分支后续结果无法改变祖先决策,可以停止搜索。NegMax形式递归时交换并取负窗口 [−β,−α]。

在相同树、深度、评价和正确边界处理下,AlphaBeta得到与Minimax相同的根值;多个走法并列时具体返回哪个还取决于遍历与平局规则。剪枝数量依走法顺序而异,并非保证跳过所有无用节点。

218说明接口与Minimax相同;搜索顺序会影响工作量,而正确剪枝不改变固定深度下的根值。

219的03371–03372在子调用传入−beta、−alpha,撤销走法后以负分更新alpha,在alpha≥beta时返回。整数哨兵应支持安全取负,执行与撤销需要保持状态一致。

220强调剪枝效果;正确算法不是近似结果,但并列最优走法可能受顺序影响。

221描述理想排序下常见的 O(b^(d/2)) 量级与最坏 O(b^d);具体节点数依深度奇偶、终局和顺序而异。03373–03375表与旋转棋盘说明遍历顺序可显著改变扩展量,历史样例不能保证固定加速倍数。

上下界剪枝保留极小极大值保存独立卡片。

原书依据 · 5 处
输入/输出

AlphaBeta输入输出与Minimax相同,但搜索中利用界限提前停止。

上下界剪枝保留极小极大值关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
解决方案

NegMax式AlphaBeta递归传递取负并交换后的窗口。

上下界剪枝保留极小极大值关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
结论

有效剪枝减少搜索量,根值保持与相同条件的Minimax一致。

上下界剪枝保留极小极大值关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
分析

走法排序决定剪枝效果,最坏仍可能搜索完整树。

上下界剪枝保留极小极大值关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处

参考文献

本章参考文献包含状态空间搜索和博弈算法资料。

第8章 网络流算法

网络流用容量限制和中间节点守恒描述输送。最大流通过残量路径增广,匹配和运输问题可转换为网络模型;费用目标还必须说明所需流量和需求约束。

第八章讨论网络流算法。

概述

最大流、匹配、运输和最小费用流是相关但目标不同的问题。

网络流建模先区分容量与成本

网络流模型用顶点和有向边表达输送关系;容量限制每条边的流量,成本刻画单位流量代价。最大流最大化源到汇的流量;最小费用流在指定流量或供需约束下最小化总成本;二部匹配可规约为单位容量最大流。

运输、转运及任务分配可建立不同网络约束,目标和可行条件不能仅凭问题名称互换。通用线性规划与专用算法的性能应按实例与实现评估。

227限定整数容量并讨论邻接表与矩阵;边是否平行、源汇是否不同和初始流是否可行需由接口定义。达到最大流后,可通过残量可达集合构造最小割。

网络流建模先区分容量与成本保存独立卡片。

原书依据 · 2 处
网络流

可行流满足边容量和中间顶点流量守恒。

可行流满足容量与守恒

对每条实际有向边使用非负流量 f(e),要求 0≤f(e)≤c(e);除源和汇外,每个顶点流入总量等于流出总量。流值可由源点净流出或汇点净流入计算。

也可使用反对称净流表示,但此时 f(v,u)=−f(u,v) 不能与每个方向独立非负流的记号直接混用;若两方向都有实际边,应明确净流与独立边流如何对应。

可行流满足容量与守恒保存独立卡片。

原书依据 · 1 处

最大流

增广算法在残量网络中寻找源到汇路径,直到不存在增广路。

残量网络允许撤回部分流量

对实际边 u→v,正向残量为 c−f,反向残量为 f;残量路径允许增加尚有容量的正向流,也允许减少此前的反向流。路径瓶颈为各残量最小值,按该值更新各边,保持容量与中间点守恒。

没有源到汇残量路径时,当前可行流为最大流。整数容量下每次正增广至少1,因此朴素Ford-Fulkerson有限终止;任意无理实数容量和任意增广策略不能无条件保证有限终止。

228的03379–03384区分前向剩余容量和反向可撤回流;路径前驱需保存边方向,处理时对正向加流、反向减流。使用BFS寻找按边数最短的增广路径是Edmonds-Karp。反向增广会调整先前流量,因此不是完全不撤销先前决策。

230给出整数容量Ford-Fulkerson以邻接结构搜索时 O(E·F) 的常见界,其中F为最大流整数值;Edmonds-Karp用BFS得到 O(VE²) 上界,与容量数值大小无关。实际搜索成本还依图表示和初始化而定。

231的03385–03387用容量与反对称净流矩阵、循环队列和BFS;空间为 O(V²),适合特定规模与密度。容量、流值、总流及残量算术需检查溢出;输入边、源汇及队列边界需验证,性能应在目标环境测量。

残量网络允许撤回部分流量保存独立卡片。

原书依据 · 4 处
输入/输出

最大流输入包含源、汇和容量,输出可行最大流及相应割。

网络流建模先区分容量与成本关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处
解决方案

搜索器可以通过DFS或BFS寻找残量路径,沿路径瓶颈增广。

残量网络允许撤回部分流量关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
结论

终止后的残量可达顶点构成最小割的一侧。

残量可达集合给出最小割

最大流结束后,从源点沿正残量边可达的顶点集合为S,其他顶点为T;汇点不可达。原网络从S到T的边均已饱和,反方向跨割的净贡献相应受限,割容量等于最大流值。

书中把S描述为不能组成增广路径的顶点,容易误解;S应是残量网络中从源点可达的集合。割容量是S到T原边容量总和,不是两个集合之间的流量最小值定义。

残量可达集合给出最小割保存独立卡片。

原书依据 · 1 处
分析

整数容量下增广次数与最大流值有关,BFS增广得到多项式界。

残量网络允许撤回部分流量关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
优化

数组实现可降低部分常数,但需明确空间、输入和数值边界。

残量网络允许撤回部分流量关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
相关算法

顶点容量可通过拆点转换成边容量,多物资流需要独立流约束。

顶点容量通过拆点变成边容量

把顶点v拆为v_in和v_out,并添加容量为k(v)的边 v_in→v_out;原入边连接v_in,原出边从v_out出发并保留各自原容量。根据问题定义决定源、汇是否也受顶点容量约束。

无向边的建模需明确是否共享双向容量;在普通单物资净流问题中可用两条反向容量边并消去互相抵消的流,但不能把这一转换无条件推广到多物资共享容量。

240的03394通过仓库入点和出点之间的边表达仓库吞吐上限及单位处理成本;源供给与汇需求边则表达上下限。规约后仍需核验总需求是否全部满足,不能只检查求解器返回任意非负流。

顶点容量通过拆点变成边容量保存独立卡片。

原书依据 · 2 处

二部图匹配

二部图最大匹配可以归约为单位容量网络最大流。

二部匹配归约为单位容量流

把二部图左右两侧分别接到源点和汇点;源到左点、可行配对边、右点到汇的容量均为1。整数最大流中的单位流配对边组成匹配,源汇边容量保证每个顶点至多参与一次。

反向残量边允许重新安排已有配对;最大匹配的数量最优,但可能存在多个不同匹配。

234的左右集合应是不相交集合,并非没有跨集合连接;可行配对正是跨两侧的边。输出匹配大小最大,不保证唯一。

235的03388例子通过反向残量重新配对;03389–03390仅从pairs创建顶点映射,若集合有孤立元素,map.get可能为空;左右集合对象相等或编号与汇点构造不一致也需处理。实现应校验两侧成员、唯一标识和配对合法性。

236以n、m、k表示两侧大小和配对边数,构图 O(n+m+k),扫描配对边输出结果 O(k);最大流计算本身的成本不能省略。

243把任务分配建模为每一侧单位容量;若要求所有任务完成,须同时指定总匹配量或满足每个需求,而不能只最小化非负费用。

二部匹配归约为单位容量流保存独立卡片。

原书依据 · 5 处
输入/输出

最大匹配要求每个顶点最多出现在一个选中配对中。

二部匹配归约为单位容量流关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
解决方案

单位容量最大流可映射回配对边,示例输入需要完整校验。

二部匹配归约为单位容量流关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
分析

匹配到流网络及结果映射的工作量与顶点和可行边数成正比。

二部匹配归约为单位容量流关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处

在增广路上的深入思考

最小费用增广要在残量网络考虑反向边的负费用。

费用流的反向残量边带负费用

若原边单位费用为c,增加流量费用为+c,撤回已有流量的反向残量边费用为−c。逐次最短增广需在残量网络正确求最短费用路径,并维护可行流和要求的目标流量;可用势函数将适用情况下的约化费用转为非负,再使用Dijkstra,或采用支持负权的最短路方法。

03391–03392直接以优先队列处理可能为负的反向费用、限制候选距离非负并在汇点出队时提前结束;没有展示势函数,不能据此对一般费用网络保证最短增广路。费用总和和距离还需防溢出。

费用流的反向残量边带负费用保存独立卡片。

原书依据 · 1 处

最小开销流

供应与需求上限本身不保证所有需求得到满足。

最小费用流须明确要求的流量

超级源到供应点的容量可表示供给上限,需求点到超级汇的容量可表示需求上限;要满足全部需求,还需要求送达总流等于需求总和,或为每个需求点设定适当的等式或下界,并在容量不足时报告不可行。

若仅最小化非负费用且只有上限,零流通常就是最优,因此必须明确固定流量、供需平衡或先最大流再最小费用的目标。残量边的负费用及反向增广也需纳入求解。

239用供应点、需求点和中转仓库构造目标:总费用为各条运输和仓库处理边的流量乘单位费用之和;仓库节点满足流守恒并受吞吐容量限制。所有需求必须满足时需明确可行性。

241没有中转节点;按每条供应到需求边的流量乘单位费用求总成本。若需求必须满足,需要相应等式或下界;仅有不超过需求和供给的上界且成本非负时零运输就是最小费用。

242说明运输到转运的规约;求解和结果验证仍须检查需求量、容量与总流目标。

244将每侧限制为单位供需;若只允许部分配对或存在不等人数,要定义不可行和未分配的处理。

最小费用流须明确要求的流量保存独立卡片。

原书依据 · 5 处

转运问题

转运模型应包含仓库容量、运输费用与流守恒。

最小费用流须明确要求的流量关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
解决方案

转运网络将仓库拆点,以容量边限制吞吐并计入处理费用。

顶点容量通过拆点变成边容量关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处

运输问题

运输问题在供给、需求与线路约束下优化运输费用。

最小费用流须明确要求的流量关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
解决方案

运输问题可视为无中转仓库的转运模型。

最小费用流须明确要求的流量关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处

任务分配问题

一对一任务分配可视为单位供给、单位需求及带费用的匹配。

二部匹配归约为单位容量流关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
解决方案

任务分配规约还需要明确允许的配对、数量和目标费用。

最小费用流须明确要求的流量关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处

线性编程

线性规划用目标函数与约束表达流问题,再验证求解结果。

线性规划把流约束写成等式

以每条边流量为变量,写出流量守恒、容量上下界以及目标函数;若目标是满足指定需求后的最小费用,应通过等式或流量约束明确该要求。求解后验证非负、容量、供需及目标值。

03395–03396例子对两个供应点和需求点都约束为300,费用为 7e13+6e14+4e23+6e24。书中给出的100、200、200、100方案费用为3300,符合容量和等式;结果取决于模型而不是软件名称。

线性规划把流约束写成等式保存独立卡片。

原书依据 · 1 处

参考文献

网络流参考文献涉及最大流、运输和线性规划。

第9章 计算几何

计算几何处理点、线段与区域之间的空间关系。凸包扫描、线段扫描和空间索引通过排序或划分减少候选,但重复、共线、边界和浮点精度影响正确性。

第九章讨论计算几何。

概述

计算几何研究几何对象及其高效算法与数据结构。

计算几何把空间关系转为算法

几何任务可以涉及点、线段、多边形等对象的查询、构造和更新;选择算法时应明确维度、输入规模、精度模型与是否需要多次查询。

249的03397–03399定义点、线段、矩形、多维对象和半开整数区间接口;03400–03401列出最近点、相交和几何包围等应用。预处理是否值得取决于查询次数与更新成本;浮点舍入、退化位置、维度及边界包含规则会影响正确性。

260提及动态维护凸包以及按极角排序的Graham扫描;角度相同的点需正确处理距离与共线,方向比较可基于叉积,无须必然计算三角函数。

计算几何把空间关系转为算法保存独立卡片。

原书依据 · 3 处
经典问题

几何问题可按输入对象、计算任务和静态或动态数据分类。

计算几何把空间关系转为算法关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处
假设

几何算法应明确共线、水平垂直、重复点和输入分布等假设。

几何算法先定义退化与精度

开始前明确重复点、共线、端点重合、水平或垂直线段、边界包含及数值精度的处理。一般位置假设可以简化证明,但真实数据不一定满足;浮点舍入使接近零的方向判定不稳定,应采用适合输入范围的稳健谓词或精确算术。

262限制重复线段、共线重叠和零长度线段,水平或垂直线段仍需精确排序与事件处理。平行且不同直线不等于共线;共享端点是否算交点应事先定义。

几何算法先定义退化与精度保存独立卡片。

原书依据 · 2 处
计算几何经典问题

凸包、线段交点、最近邻和范围查询需要不同的输出和复杂度模型。

几何查询须计入预处理与输出

凸包可用排序加扫描构造;线段两两测试有 n(n−1)/2 对,报告所有交点至少需要输出相关工作;空间索引可加速多次最近邻或范围查询,但要计入建索引和更新成本。

书中给出的kd树 O(log n) 最近邻和 O(√n+r) 范围查询依赖维度、树平衡和输入等假设,不能作为任意数据分布下的保证;最坏情况下最近邻仍可能访问线性数量节点。

271指出小数据集或高维数据可能使kd树不划算;维度阈值不是普遍常数,应对目标分布、索引构建及查询负载做测量。

279提醒高维kd树可能退化,应比较构建、更新与查询总成本,而不是预设某个维度阈值。

280指出kd树可复用于最近邻和范围查询;两者分别基于距离下界和区域相交关系进行剪枝。

几何查询须计入预处理与输出保存独立卡片。

原书依据 · 4 处

凸包扫描

Andrew单调链按坐标排序,以方向测试维护上、下凸包。

单调链凸包用叉积维护转向

将点按x、y字典序排序,分别按正向和反向扫描;每加入一点后检查末尾三点的叉积,若转向不符合所需方向则移除中间点,直到满足条件。上、下链去重端点后合并得到凸包。

叉积符号表达左右转,等于0表示共线;是否保留边界上的共线点必须先约定。排序 O(n log n),每点在各链至多入栈和出栈一次,扫描 O(n)。

253假设至少三个且点不太接近;实际接口仍须定义空集、单点、重复点和全共线输入。数值误差是否可忽略取决于应用,不能预先保证。

254以坐标极值点组成内接四边形,严格位于其内部的点不可能是凸包顶点,可以在线性预处理中过滤;边界共线点是否可删取决于输出要求,极值点重合时也需处理退化。过滤效果依分布而异。

255讨论排序选择;Graham扫描也可使用叉积和比较器而不必计算三角函数,链表也可用归并排序,并非只能插入排序。桶排序的期望线性依赖分布和映射条件,不能无条件承诺线性。

256的03414–03416代码排序后维护两条链并去除重复端点;调用的areLastThreeNonRight决定共线如何处理,重复点、空输入及浮点比较仍需核验。

258指出排序后上下链的总删除次数各至多线性;03417–03418中的点数和时间来自单位正方形均匀样本,不能推广到任意分布,例如圆周点可全部属于凸包。固定δ=10⁻⁹的叉积容差依坐标尺度,不能普遍消除数值误差。

259说明已按所需顺序排序的点可线性扫描;03419比较圆周、均匀和偏斜分布,桶排序的优势依均匀条件。高维凸包和已按简单多边形顺序给出的输入也需要各自算法及假设。

单调链凸包用叉积维护转向保存独立卡片。

原书依据 · 7 处
输入/输出

凸包接口需定义点数不足、重复和共线情形。

单调链凸包用叉积维护转向关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
使用环境

极值点构成的内接多边形可用于过滤确定不在凸包顶点上的内部点。

单调链凸包用叉积维护转向关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
驱动因素

凸包扫描总成本由排序与线性扫描共同决定。

单调链凸包用叉积维护转向关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
解决方案

示例分别构造上下链并删除不符合转向的中间点。

单调链凸包用叉积维护转向关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
结论

排序算法选择应考虑最坏界、数据及实现常数。

排序基准须覆盖输入分布关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处
分析

凸包扫描的线性部分来自每个点有限次进出栈,固定容差需要谨慎。

单调链凸包用叉积维护转向关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
变种

已排序输入可以跳过凸包排序,其他变种的表现依分布而异。

单调链凸包用叉积维护转向关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
相关算法

动态凸包和Graham扫描针对不同输入与更新需求。

计算几何把空间关系转为算法关联本项背景,实质主要讲解在对应位置。

原书依据 · 3 处

线段扫描

扫描线以事件队列和活动线段顺序减少不必要的线段对检查。

扫描线在事件处更新活动顺序

将线段端点及发现的交点作为事件按扫描方向处理,活动集合维护与扫描线相交的线段顺序;新相邻线段可能产生未来交点,将其加入事件队列。事件发生时更新活动顺序并报告交点。

一般位置和合适平衡结构下,常见输出敏感复杂度为 O((n+k) log n),k为交点数;交点大量出现、重叠或多线共点时,需要明确输出定义及专门处理。

263强调少交点场景;大量交点时输出与事件维护开销增加,穷举实现虽然渐近不同,仍可能在小规模数据更简单或更快。

264用平衡树维护扫描线活动顺序与事件队列;比较器依扫描位置变化时,应在事件处按算法正确移除并重新插入相关线段,避免破坏树的不变式。

265的03423–03427维护事件点、扫描状态和线段集合;相同事件点需要合并,并在状态更新后检查邻居是否在后续位置相交。数值相等、多个线段同点与水平线段都需一致规则,否则可能漏报或重复。

266指出线性查找插入位置或线性查询事件成员会降低性能;优先队列可结合哈希表或索引支持成员检查,不必排除所有堆实现。

267说明事件队列最多 O(n+k) 个事件,活动集合最多n条线段;在一般位置与对数操作假设下,O((n+k) log(n+k)) 可化为 O((n+k) log n),因为线段对交点数至多 O(n²)。03428–03430实验展示交点多时管理常数可能使穷举更快。布丰投针公式还依针长不超过平行线间距等条件。

268指出存在性问题可以在找到第一个交点后终止;不同颜色线段交点是另一种有额外约束的变种。

扫描线在事件处更新活动顺序保存独立卡片。

原书依据 · 7 处
输入/输出

线段扫描的正确性依赖明确退化输入与边界约定。

几何算法先定义退化与精度关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处
使用环境

当交点较少时扫描线可能优于两两测试,复杂度与输出规模相关。

扫描线在事件处更新活动顺序关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
驱动因素

事件队列与活动集合需要支持有序操作和相邻线段查询。

扫描线在事件处更新活动顺序关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
解决方案

扫描事件合并同一点的端点和交线,并检查新相邻关系。

扫描线在事件处更新活动顺序关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
结论

扫描线的复杂度依赖活动集合和事件去重操作的实现。

扫描线在事件处更新活动顺序关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
分析

扫描线在事件数和操作成本受控时有输出敏感界。

扫描线在事件处更新活动顺序关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
变种

只判断是否存在交点时可在首次发现交点后停止。

扫描线在事件处更新活动顺序关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处

最近点查询

kd树按坐标递归划分空间,利用距离下界排除不可能更近的区域。

最近邻用区域距离下界剪枝

kd树逐层按某坐标切分点集。最近邻搜索先维护当前最小距离,再检查另一子区域到目标的距离下界;只有该下界不可能改善当前结果时才能跳过该区域。切分面距离是一种可用下界,区域包围盒可提供更强下界。

平衡树高度为 O(log n) 不保证最近邻只访问一条路径;查询可能跨越许多区域,最坏仍 O(n)。高维或高度聚集数据常削弱剪枝效果。

270允许浮点误差但认为影响不致命;实际影响依业务阈值而定,接口应约定相等距离的选择、维度匹配和空集行为。

272的03435每层选择当前维度中位点并递归构建两个子树;选择算法的成本和重复坐标分配影响构建效率。书中引用四元组BFPRT实现的最坏线性结论,不能不加证明地套用;参见最坏线性选择卡。

273的03436–03438记录当前最佳距离并依据目标到切分面的垂直距离选择一侧或两侧;若要求返回所有等距点,应按接口语义处理相等边界。空树返回null,维度和坐标有效性仍需校验。

274说平衡树能排除近半点,但某些数据和查询会在多层同时探索两侧;平衡只限制树高,不单独保证对数最近邻查询。

275的03439–03442展示高维双分支搜索增多及与穷举的实验交叉;即便树平衡,剪枝不足时查询可能接近 O(n),每次距离计算还要考虑维度d。书中一处称高维性能逼近log(n),与其后线性退化描述矛盾,应以实际访问量为准。

276提到自底向上的变种;无论顺序如何,都必须检查可能含更近点的区域。

最近邻用区域距离下界剪枝保存独立卡片。

原书依据 · 7 处
输入/输出

最近邻接口应定义空集、距离度量、并列结果和浮点精度。

最近邻用区域距离下界剪枝关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
使用环境

索引成本须与查询次数和维度一起衡量。

几何查询须计入预处理与输出关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
驱动因素

按维度中位数递归切分可以构建按点数相对平衡的kd树。

最近邻用区域距离下界剪枝关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
解决方案

近邻实现比较候选点并按切分面距离决定是否搜索另一侧。

最近邻用区域距离下界剪枝关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
结论

平衡kd树也可能需要访问切分线两侧的大量区域。

最近邻用区域距离下界剪枝关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
分析

kd树在高维或不利分布中可能搜索大量分支。

最近邻用区域距离下界剪枝关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处
变种

kd树最近邻可从不同遍历顺序实现,但剪枝必须保持正确下界。

最近邻用区域距离下界剪枝关联本项背景,实质主要讲解在对应位置。

原书依据 · 7 处

范围查询

范围查询可按区域是否相交或被完整包含来裁剪。

范围查询按区域关系裁剪

对空间索引节点,若其包围区域与查询区域不相交则跳过子树;若查询区域完全包含该节点区域,可直接收集整棵子树;部分相交时检查节点并递归相关子树。输出r个点至少需要 Ω® 的工作。

标准平衡kd树在固定维度和相应构造假设下可得到 O(n^(1−1/d)+r) 的范围报告界;实际边界处理、数据分布和维度影响性能,不能无条件套用。

278要求d维输入与查询区域一致;矩形边界是否包含、重复点是否逐个输出和空结果如何表示需由接口明确。

281正文有一处将包含关系写反;03445代码为 space.contains(region),即查询区域包含节点区域时收集子树,而不是节点区域包含查询区域。子树收集仍需逐个输出点。

282的03446–03449比较不同维度与查询区域;当结果包含全部n点,输出本身就是 Ω(n),并非低效算法的充分证据。实验的交叉点与数据、维度及实现相关。

范围查询按区域关系裁剪保存独立卡片。

原书依据 · 4 处
输入/输出

查询区域和点集必须维度一致,接口应定义边界包含规则。

范围查询按区域关系裁剪关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
使用环境

高维可能使空间划分剪枝效果变差。

几何查询须计入预处理与输出关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
驱动因素

同一空间索引可支持不同查询,但各查询有不同的剪枝条件。

几何查询须计入预处理与输出关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
解决方案

查询区域包含节点区域时,整棵子树都可输出。

范围查询按区域关系裁剪关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
分析

范围查询收益取决于输出量、维度和区域与索引的关系。

范围查询按区域关系裁剪关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处

参考文献

计算几何参考文献涉及凸包、线段交点和空间索引。

第三部分

第三部分包含最后的招数和尾声。

第10章 最后的招数

当精确顺序算法不合适时,可改变模型:近似算法提供有条件的质量保证,批处理和并行改变执行方式,随机算法以概率或期望描述结果和成本。

随机算法把随机选择作为计算过程的一部分。

随机算法需明确随机性与保证

随机算法在运行中使用随机选择,同一输入可能产生不同运行时间或结果。设计时应区分结果是否总正确、错误概率或期望成本,并明确随机数来源和生成开销;伪随机序列的性质与可复现性也应符合用途。

286列出结果准确性、实例处理方式、顺序执行和确定性四项假设;放宽任一项都需重新定义成本及正确性要求。

290强调随机数生成和伪随机序列;是否需要不可预测性、统计独立性或可复现实验应由用途决定。

293指出重复实验可降低错误率,但需要给出单次错误模型、独立性和组合规则,不能对任意相关实验直接套乘法。

随机算法需明确随机性与保证保存独立卡片。

原书依据 · 4 处

另类算法

放宽精确、单实例、顺序和确定性假设可得到不同算法模型。

随机算法需明确随机性与保证关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处

近似算法

近似算法以可量化的解质量换取计算成本。

近似保证依赖问题约束

近似算法返回可行解,并在适用条件下提供与最优值的误差或比例保证。度量旅行商问题满足非负对称距离和三角不等式时,Christofides算法可给出不超过最优长度1.5倍的路线;这一保证不能直接推广到任意不满足条件的距离矩阵。

一般TSP为NP难问题,但是否存在多项式时间精确算法与尚未解决的复杂性问题相关,不能当作已被证明不存在。

近似保证依赖问题约束保存独立卡片。

原书依据 · 1 处

离线算法

批量已知查询可通过排序和合并扫描减少重复工作。

离线批处理利用已知查询

若所有查询预先可用,可分别排序数据与查询,再用双指针合并扫描,随后按原查询位置还原答案;比较模型下排序成本 O(n log n),扫描 O(n)。

书中把在线查询必然写成 O(n²) 过于绝对:静态数据可先排序、每次二分,或按适用假设构建散列索引。离线方案应与合理的在线预处理方案比较,并计入建索引和输出成本。

289讨论并行顺序查找;拥有n个处理器时的并行时间不等于总工作量,还需要计入调度、内存带宽、归并及实际处理器数量。

离线批处理利用已知查询保存独立卡片。

原书依据 · 2 处

并行算法

并行加速需考虑处理器数、总工作量和通信同步。

离线批处理利用已知查询关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处

随机算法

伪随机数生成可以复现,但随机假设与生成成本要单独评估。

随机算法需明确随机性与保证关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
估算集合的大小

重复抽样直到碰撞可估计集合规模,但示例估计式不是严格无偏。

碰撞估算依赖抽样模型

从n个等概率元素独立有放回抽样直到首次重复,首次碰撞通常在约 √(πn/2) 次抽样附近;示例以重复前不同元素数k计算 2k²/π,抽样次数期望为 O(√n)。实际需要支持均匀随机抽样与记录已见元素,成本应计入。

书中称该估计严格无偏,但 n=1 时 k恒为1、估计值为2/π而不是1,已构成反例;不能以期望抽样次数近似值的平方直接替代二阶矩。去掉最大最小样本后均值也改变估计性质。

碰撞估算依赖抽样模型保存独立卡片。

原书依据 · 1 处
估算搜索树的大小

随机游走按路径分支数乘积估计搜索树解数。

随机路径乘分支数估计解数

从根开始,在每层均匀随机选择一个合法子节点,将沿路径各层分支数相乘;到达完整解时该乘积是一次估计,提前遇到死路则记0。每个完整解被抽中的概率等于路径分支数倒数,因此在满足均匀选择且无溢出等条件下,估计值期望等于解的数量。

单次结果可能偏差很大;独立重复取均值可降低方差,但更多样本不保证每次误差都单调缩小。代码中的long乘积可能溢出,采样偏差也会改变估计。

随机路径乘分支数估计解数保存独立卡片。

原书依据 · 1 处

结果可能出错却可以衰减错误率的算法

概率算法可以通过多次独立尝试降低特定错误概率。

随机算法需明确随机性与保证关联本项背景,实质主要讲解在对应位置。

原书依据 · 4 处
检测数据库间的不一致

模素数指纹可快速发现差异,但相等指纹不保证数据相同。

指纹一致不能证明数据相同

把数据编码成整数后取模,模值不同可确定编码不同;模值相同仍可能是碰撞。若随机选取素数,碰撞概率由两个编码差值含有多少候选素因子以及素数的抽样分布决定,不能无条件写成1/p。多次独立取样有助于降低假一致概率,但要按实际选择空间计算。

比较前还须固定编码、记录顺序、版本或一致性快照;对抗性修改场景需采用适合威胁模型的认证或密码学方案。

指纹一致不能证明数据相同保存独立卡片。

原书依据 · 1 处
零知识证明

零知识认证需要同时说明完备性、可靠性和不泄露知识的证明条件。

交互证明需要绑定承诺与挑战

身份认证的交互证明希望证明者能回答随机挑战,同时不向验证者泄露秘密。若每轮攻击成功率至多1/2且挑战独立,连续100轮成功概率至多2⁻¹⁰⁰;这一结论依赖协议真正具备该单轮可靠性。

书中03465直接发送完整重标记图并声称不泄露任何信息,没有展示标准承诺机制及零知识模拟证明;不能把它当作已验证的安全认证协议。实际系统应采用经过审查的协议、可信随机挑战和绑定身份的认证信道。

交互证明需要绑定承诺与挑战保存独立卡片。

原书依据 · 1 处

参考文献

本章参考文献包括近似、并行和随机搜索估计。

第11章 尾声

尾声归纳选算法的方法:了解数据、分解问题、选择结构、权衡空间和时间,并在需要时搜索或归约。测试和实验必须检查前提,不能只依赖名称或历史性能表。

第十一章为全书尾声。

概述

尾声按跨算法原则汇总数据、分解和结构等思想。

原则:了解数据

算法选择首先需要了解数据的访问方式、分布和约束。

排序基准须覆盖输入分布关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处

原则:将问题分解至更小的问题

分解问题需要分别计算子问题数量和合并代价。

分治复杂度由递推和合并决定

将问题分解为子问题后,写出子问题数量、规模与每层额外工作,再由递推分析总体成本;例如 T(n)=2T(n/2)+O(n) 为 O(n log n),二分查找每次只继续一个半区,递推为 T(n)=T(n/2)+O(1)。

不是所有 O(n log n) 算法都必须采用两个等规模子问题。书中把“反复选最大并交换到末尾”称为插入排序,实际描述的是选择排序。

分治复杂度由递推和合并决定保存独立卡片。

原书依据 · 1 处

原则:选择正确的数据结构

数据结构必须支持算法实际需要的操作和对应成本。

查找结构按查询与更新权衡关联本项背景,实质主要讲解在对应位置。

原书依据 · 6 处

原则:空间换时间

缓存状态或冗余索引可以减少重复计算,但应计入空间和维护成本。

空间换时间要计入维护成本

保存已计算结果、访问标记或额外索引,可以减少后续查找与重复运算;同时要计算空间占用、更新和失效成本。Prim的key记录到已选集合的最轻连接边,而不是从起点的最短路径距离。

邻接矩阵适合某些稠密图和快速边查询,但空间为 O(V²);桶排序的线性期望依赖分布与映射,不能从“正态分布”单独推出。

空间换时间要计入维护成本保存独立卡片。

原书依据 · 1 处

原则:如果没有显而易见的解法,使用搜索

搜索提供通用建模方式,但应先检查是否有更直接的算法。

搜索从状态与合法转移建模关联本项背景,实质主要讲解在对应位置。

原书依据 · 6 处

原则:如果没有显而易见的解法,将问题归约为另一个有解的问题

问题归约需要同时映射输入、解和正确性条件。

问题归约要验证输入和解映射

把原问题的实例转为已知问题,求解后再把结果映射回原问题;需要证明可行性及目标值之间的对应,并计入转换成本。比如二部匹配可归约成单位容量最大流,而第k个元素也可通过排序后取值,但不一定是最省时间的方法。

最大流算法族不能直接求解任意线性规划;最小费用流和一般线性规划还需各自的目标与约束处理。

问题归约要验证输入和解映射保存独立卡片。

原书依据 · 1 处

原则:编写算法难,测试算法更难

算法测试可结合性质、对照实现与数值边界,不能只检查单个预期输出。

算法测试结合不变量与对照

对搜索可用小规模穷举或已知最短路径作参考,验证输出路径合法、代价及最优性条件;对排序检查有序、元素保留与稳定性;对几何算法检查边界、退化情况并与精确或高精度参照比较。

浮点固定绝对阈值并不适用于所有尺度,统计比较也不能替代关键案例的正确性检查。随机测试应记录种子以便复现,失败案例应保留。

算法测试结合不变量与对照保存独立卡片。

原书依据 · 1 处

第四部分

附录介绍基准测试。

附录 基准测试

基准测试用具体输入观察性能,与理论界互补。

基准测试描述输入与环境

理论复杂度描述随规模增长的界,基准测试测量特定实现、平台及输入上的行为;应记录输入分布、规模、运行环境、重复次数和统计方式,并同时验证计算结果。有限采样不能穷举所有输入,也不能单凭曲线证明渐近界。

309记录Pentium 4桌面机和AMD Opteron集群,书中绝对时间和相对排名不能直接视为现今环境的测量结果。

310以不同规模的求和任务、30次实验比较语言实现;比较时应保持计算语义、数据和测量范围一致。

312的03476–03482展示输入规模、随机种子、重复运行及统计脚本;被测求和结果同样未被消费,编译优化可能消除工作。脚本结果应保留原始数据、执行参数和失败状态,删除极值的策略应明确。

313的03483–03488展示Scheme辅助函数、计时、求和和结果;标准差实现及剔除极值口径应与其他语言一致,计时精度和运行时行为也影响比较。

基准测试描述输入与环境保存独立卡片。

原书依据 · 5 处

统计基础

测量分布、均值和标准差时必须说明统计假设。

标准差区间不是自动的置信区间

样本标准差为 sqrt(Σ(xi−均值)²/(m−1)),图03473缺少平方根,所示实际是样本方差。均值±一个或两个标准差的68.27%、95.45%覆盖率来自正态分布等假设;它描述单次观测分布,不能直接当作总体均值置信区间。

人为剔除最大和最小值会改变样本分布,必须预先说明理由和规则;重复计时可能相关,还需考虑预热、系统负载和计时器分辨率。

314的03489–03493给出历史结果;仅假设样本独立不足以推出均值±2个样本标准差覆盖未来测量的概率为95.45%,还需分布和估计假设。图表单位均标毫秒,正文对Java“秒级”表述与代码及表不一致。

标准差区间不是自动的置信区间保存独立卡片。

原书依据 · 2 处

硬件

历史硬件环境决定了书中时间数值的适用范围。

基准测试描述输入与环境关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处

例子

基准设计应控制输入规模并重复测量。

基准测试描述输入与环境关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处

Java基准测试解决方案

微基准需防止编译器或虚拟机消除未使用的计算。

微基准要防止计算被优化掉

03475的Java求和结果没有被消费,优化编译器可能删除或改写被测工作,因此测量结果不一定代表原操作。应使用可靠的微基准框架或可观察的结果消费,预热执行,记录计时范围与环境,并验证计算结果。

调用System.gc只是请求垃圾回收,不能保证回收时机;短任务还需关注计时精度和测量开销。

315的03494–03495比较两个Java计时方法;纳秒单位不代表纳秒级准确度或分辨率,应使用单调计时、预热、足够长的测量批次及重复样本。历史平台计时限制不能直接推广到当前环境。

微基准要防止计算被优化掉保存独立卡片。

原书依据 · 2 处

Linux基准测试解决方案

基准脚本应保留随机种子、配置、原始样本和验证结果。

基准测试描述输入与环境关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处

Scheme基准测试解决方案

不同语言的计时示例需保持同一工作量和统计口径。

基准测试描述输入与环境关联本项背景,实质主要讲解在对应位置。

原书依据 · 5 处

报告

不同运行时的计时结果不能脱离分辨率、分布和实现比较。

标准差区间不是自动的置信区间关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处

精度

计时器标称单位不等于真实分辨率,需测量足够长的工作并报告分布。

微基准要防止计算被优化掉关联本项背景,实质主要讲解在对应位置。

原书依据 · 2 处

作者简介

作者简介介绍三位作者的背景。

封面介绍

封面介绍介绍寄居蟹及其生态。

跨章综合

输入模型贯穿全书:排序的稳定性与键域、查找的数据访问方式、图算法的方向和边权、几何算法的精度与退化情况,都决定一个算法是否适用。复杂度要连同数据结构、比较成本和空间成本一起解释;实验则只能检验特定条件下的实现。

许多算法复用共同结构,但承担不同任务:堆既能维护排序候选,也能为最短路径或生成树选取下一项;Dijkstra比较源点累计距离,Prim比较连接已选树的单条边。BFS按边数分层,A星以已走成本和启发式选择状态,最大流则用残量网络允许撤回之前的流。各自的正确性依赖不同的前提。

将理论翻译为代码时还需要处理不可达、溢出、重复键、空集合与数值边界。正文所述历史示例中存在已在相关小节标注的错误或过强主张;本轮以实际原文和代码静态阅读为依据,没有运行书中程序。

发散与实践

读者延伸:可先从两项成熟实现入手,分别追踪 CPython 堆队列的建堆与维护、NetworkX 最短路径的优先队列和松弛。两项均已准备源码入口和阅读计划,完整实践尚未执行。

生成进度与管理记录

算法技术手册

类别:算法与数据结构类

四象限结论:经典原理(高浓度 + 高稳定性)

阶段一:整体评级

四象限结论:经典原理(高浓度 + 高稳定性) 判断理由:本书从问题建模、数学增长率、性能分析、算法模式和领域约束来组织排序、查找、图、寻路、网络流和计算几何,强调为什么选择某类算法,稳定性很高。

阶段二:章节重点确认(恢复前历史记录)

章节号 章节标题 精读/略读 状态(pending/done) 卡片数
01 第1章 算法真的很重要 精读 done 1
02 第2章 算法的数学原理 精读 done 3
03 第3章 模式和领域 精读 done 1
04 第4章 排序算法 精读 done 0
05 第5章 查找 精读 done 0
06 第6章 图算法 精读 done 0
07 第7章 人工智能中的寻路 精读 done 0
08 第8章 网络流算法 精读 done 0
09 第9章 计算几何 精读 done 0
10 第10章 最后的招数 精读 done 0
11 第11章 尾声 精读 done 0
12 附录 基准测试 略读 done 0

来源说明

本书来自合集 EPUB《OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)》;合集 spine 范围为 1436..1702,已按单本书独立建目录与卡片。

类别清单核对(恢复前历史记录)

必答维度 覆盖状态 已有卡片/说明
问题建模与领域约束 已覆盖 [[问题先于算法]]
复杂度、增长率与性能边界 已覆盖 [[增长率]]、[[性能三种情况]]
算法设计范式 已覆盖 [[算法模式语言]]
排序、查找与基础数据结构 未覆盖 当前卡片未具体展开具体算法及其适用边界。
图、路径与网络流 未覆盖 相关章节尚未补跑卡片。
几何、组合及其他专门领域算法 未覆盖 相关章节尚未补跑卡片。
基准、验证与工程实现取舍 已覆盖 [[基准验证]]

2026-11-06 全流程恢复

执行模式:light

本次实际执行版本:book-workflow v4 / book-notes v24。旧记录无Skill版本,不回填首次版本;历史5卡与数据库身份/关系基线保留。

继承经典原理评级,概念解析为主;接口定义局部按操作参考处理。旧done不代替本轮全文与证据。当前来源来自实际合集one-based spine1437–1703,旧1436–1702为zero-based偏移;267来源项中264实质项、317阅读单元、369唯一图像。

建档进度:done

本轮生成:317/317单元和369/369图实读,131张知识卡、295处结构化来源、2项实践计划;轻量模式未执行笔记复核、独立审查及审查结果优化。实践候选筛选已完成,具体结果见文末进度表。

当前章节进度
章节号 章节标题 状态(pending/done) 卡片数
spine-1440 O’Reilly Media,Inc.介绍 done 0
spine-1441 译者序 done 0
spine-1442 前言 done 1
spine-1443 原则:使用实际代码,而不是伪代码 done 1
spine-1444 原则:将算法和将要解决的问题分开 done 1
spine-1445 原则:仅仅讲述足够的数学 done 0
spine-1446 原则:用经验来支持数学分析 done 1
spine-1447 目标读者 done 0
spine-1448 本书组织方式 done 0
spine-1449 本书体例 done 0
spine-1450 代码使用说明 done 0
spine-1451 联系我们 done 0
spine-1452 致谢 done 0
spine-1453 参考文献 done 0
spine-1454 第一部分 done 0
spine-1455 第1章 算法真的很重要 done 1
spine-1456 如果需要,尽可能用实践检验 done 2
spine-1457 解决问题的算法 done 1
spine-1458 花絮 done 1
spine-1459 故事的寓意 done 1
spine-1460 参考文献 done 0
spine-1461 第2章 算法的数学原理 done 2
spine-1462 函数的增长率 done 2
spine-1463 最好最坏和平均情况下的性能分析 done 1
spine-1464 平均情况 done 1
spine-1465 最好情况 done 0
spine-1466 性能指标 done 0
spine-1467 讨论1:对数级算法的性能 done 2
spine-1468 讨论2:次线性的算法的性能,时间复杂度为O(nd),d<1 done 1
spine-1469 讨论3:线性算法的性能 done 1
spine-1470 讨论4:nlogn算法的性能 done 1
spine-1471 讨论5a:二次方的算法性能 done 1
spine-1472 讨论5b:性能不明显的计算 done 1
spine-1473 混合操作 done 1
spine-1474 基准测试 done 1
spine-1475 最后一点 done 1
spine-1476 参考文献 done 0
spine-1477 第3章 模式和领域 done 1
spine-1478 算法模式的格式 done 1
spine-1479 伪代码模式的格式 done 0
spine-1480 设计格式 done 1
spine-1481 基于经验的评价格式 done 0
spine-1482 领域和算法 done 1
spine-1483 浮点计算 done 1
spine-1484 值之间的比较 done 1
spine-1485 特殊的量 done 1
spine-1486 性能 done 0
spine-1487 手动内存分配 done 1
spine-1488 选择一门编程语言 done 1
spine-1489 参考文献 done 0
spine-1490 第二部分 done 0
spine-1491 第4章 排序算法 done 2
spine-1492 表述 done 1
spine-1493 可比较的元素 done 1
spine-1494 稳定排序 done 1
spine-1495 分析技术 done 1
spine-1496 通用输入 done 0
spine-1497 插入排序 done 1
spine-1498 驱动因素 done 1
spine-1499 解决方案 done 1
spine-1500 结论 done 0
spine-1501 分析 done 1
spine-1502 中值排序 done 3
spine-1503 驱动因素 done 0
spine-1504 解决方案 done 0
spine-1505 结论 done 0
spine-1506 分析 done 1
spine-1507 快速排序 done 1
spine-1508 解决方案 done 1
spine-1509 结论 done 0
spine-1510 分析 done 0
spine-1511 变种 done 2
spine-1512 选择排序 done 1
spine-1513 堆排序 done 1
spine-1514 驱动因素 done 0
spine-1515 解决方案 done 0
spine-1516 分析 done 1
spine-1517 变种 done 0
spine-1518 计数排序 done 1
spine-1519 驱动因素 done 0
spine-1520 解决方案 done 1
spine-1521 分析 done 0
spine-1522 桶排序 done 1
spine-1523 使用环境 done 0
spine-1524 驱动因素 done 0
spine-1525 解决方案 done 1
spine-1526 分析 done 0
spine-1527 变种 done 1
spine-1528 选择排序算法的标准 done 1
spine-1529 双浮点数的基准测试结果 done 0
spine-1530 参考文献 done 0
spine-1531 第5章 查找 done 1
spine-1532 顺序查找 done 1
spine-1533 使用环境 done 0
spine-1534 驱动因素 done 0
spine-1535 解决方案 done 0
spine-1536 结论 done 1
spine-1537 分析 done 0
spine-1538 变种 done 1
spine-1539 二分查找 done 1
spine-1540 使用环境 done 0
spine-1541 驱动因素 done 0
spine-1542 解决方案 done 0
spine-1543 结论 done 0
spine-1544 分析 done 0
spine-1545 变种 done 1
spine-1546 基于散列的查找 done 1
spine-1547 使用环境 done 0
spine-1548 驱动因素 done 0
spine-1549 解决方案 done 1
spine-1550 结果 done 0
spine-1551 分析 done 0
spine-1552 变种 done 2
spine-1553 二叉查找树 done 1
spine-1554 使用环境 done 0
spine-1555 驱动因素 done 1
spine-1556 解决方案 done 1
spine-1557 结论 done 0
spine-1558 分析 done 0
spine-1559 变种 done 1
spine-1560 参考文献 done 0
spine-1561 第6章 图算法 done 3
spine-1562 存储问题 done 0
spine-1563 图分析 done 1
spine-1564 数据结构设计 done 0
spine-1565 问题 done 0
spine-1566 深度优先搜索 done 1
spine-1567 使用环境 done 0
spine-1568 解决方案 done 1
spine-1569 分析 done 0
spine-1570 广度优先搜索 done 1
spine-1571 使用环境 done 0
spine-1572 解决方案 done 0
spine-1573 分析 done 0
spine-1574 单源最短路径 done 2
spine-1575 解决方案 done 0
spine-1576 结论 done 0
spine-1577 分析 done 0
spine-1578 变种 done 2
spine-1579 比较 done 0
spine-1580 所有点对最短路径 done 1
spine-1581 解决方案 done 0
spine-1582 分析 done 0
spine-1583 最小生成树算法 done 1
spine-1584 结论 done 0
spine-1585 分析 done 0
spine-1586 变种 done 1
spine-1587 参考文献 done 0
spine-1588 第7章 人工智能中的寻路 done 2
spine-1589 搜索树 done 0
spine-1590 关键思想 done 1
spine-1591 假设 done 0
spine-1592 深度优先搜索 done 1
spine-1593 使用环境 done 0
spine-1594 解决方案 done 0
spine-1595 结论 done 0
spine-1596 分析 done 0
spine-1597 广度优先搜索 done 0
spine-1598 使用环境 done 0
spine-1599 解决方案 done 0
spine-1600 结论 done 0
spine-1601 分析 done 0
spine-1602 A*搜索 done 1
spine-1603 使用环境 done 0
spine-1604 解决方案 done 1
spine-1605 结论 done 0
spine-1606 驱动因素 done 0
spine-1607 分析 done 0
spine-1608 变种 done 1
spine-1609 相关算法 done 0
spine-1610 比较 done 0
spine-1611 Minimax done 1
spine-1612 使用环境 done 0
spine-1613 解决方案 done 0
spine-1614 结论 done 0
spine-1615 分析 done 0
spine-1616 变种 done 0
spine-1617 NegMax done 1
spine-1618 使用环境 done 0
spine-1619 解决方案 done 0
spine-1620 结论 done 1
spine-1621 分析 done 0
spine-1622 AlphaBeta done 1
spine-1623 解决方案 done 0
spine-1624 结论 done 0
spine-1625 分析 done 0
spine-1626 参考文献 done 0
spine-1627 第8章 网络流算法 done 2
spine-1628 最大流 done 1
spine-1629 解决方案 done 0
spine-1630 结论 done 1
spine-1631 分析 done 0
spine-1632 优化 done 0
spine-1633 相关算法 done 1
spine-1634 二部图匹配 done 1
spine-1635 解决方案 done 0
spine-1636 分析 done 0
spine-1637 在增广路上的深入思考 done 1
spine-1638 最小开销流 done 1
spine-1639 转运问题 done 0
spine-1640 运输问题 done 0
spine-1641 任务分配问题 done 0
spine-1642 线性编程 done 1
spine-1643 参考文献 done 0
spine-1644 第9章 计算几何 done 1
spine-1645 假设 done 1
spine-1646 计算几何经典问题 done 1
spine-1647 凸包扫描 done 1
spine-1648 使用环境 done 0
spine-1649 驱动因素 done 0
spine-1650 解决方案 done 0
spine-1651 结论 done 0
spine-1652 分析 done 0
spine-1653 变种 done 0
spine-1654 相关算法 done 0
spine-1655 线段扫描 done 1
spine-1656 使用环境 done 0
spine-1657 驱动因素 done 0
spine-1658 解决方案 done 0
spine-1659 结论 done 0
spine-1660 分析 done 0
spine-1661 变种 done 0
spine-1662 最近点查询 done 1
spine-1663 使用环境 done 0
spine-1664 驱动因素 done 0
spine-1665 解决方案 done 0
spine-1666 结论 done 0
spine-1667 分析 done 0
spine-1668 变种 done 0
spine-1669 范围查询 done 1
spine-1670 使用环境 done 0
spine-1671 驱动因素 done 0
spine-1672 解决方案 done 0
spine-1673 分析 done 0
spine-1674 参考文献 done 0
spine-1675 第三部分 done 0
spine-1676 第10章 最后的招数 done 1
spine-1677 近似算法 done 1
spine-1678 离线算法 done 1
spine-1679 并行算法 done 0
spine-1680 随机算法 done 1
spine-1681 估算搜索树的大小 done 1
spine-1682 结果可能出错却可以衰减错误率的算法 done 1
spine-1683 零知识证明 done 1
spine-1684 参考文献 done 0
spine-1685 第11章 尾声 done 0
spine-1686 原则:了解数据 done 0
spine-1687 原则:将问题分解至更小的问题 done 1
spine-1688 原则:选择正确的数据结构 done 0
spine-1689 原则:空间换时间 done 1
spine-1690 原则:如果没有显而易见的解法,使用搜索 done 0
spine-1691 原则:如果没有显而易见的解法,将问题归约为另一个有解的问题 done 1
spine-1692 原则:编写算法难,测试算法更难 done 1
spine-1693 第四部分 done 0
spine-1694 附录 基准测试 done 2
spine-1695 硬件 done 0
spine-1696 例子 done 0
spine-1697 Java基准测试解决方案 done 1
spine-1698 Linux基准测试解决方案 done 0
spine-1699 Scheme基准测试解决方案 done 0
spine-1700 报告 done 0
spine-1701 精度 done 0
spine-1702 作者简介 done 0
spine-1703 封面介绍 done 0
非正文排除
spine项 类型 排除理由
1437 封面 封面已实际看图,身份信息,不含算法正文。
1438 书名与版权页 版权页全文已读,用于出版元数据,不作为正文单元。
1439 纯目录 纯目录全文读完,用于计划导航,无实质算法解释。
待关联术语
术语名 出现章节 一句话语境
引用文献
标题 类型(书/论文/框架/源码项目) 出现章节 一句话语境
Floating Point Arithmetic 文章 第3章 Java浮点表示背景参考。
The Algorithm Design Manual 书 第3章 算法领域分类参考。
What Every Computer Scientist Should Know About Floating-Point Arithmetic 论文 第3章 浮点误差背景参考。
Design Patterns 书 第3章 软件设计模式参考。
A Pattern Language 书 第3章 建筑模式语言的历史参考。
IEEE 754 标准 第3章 原文介绍浮点计算标准;具体格式和舍入将在后续章节处理。
More on Squaring and Multiplying Large Integers 论文 第2章 作者用于大整数乘法的参考,未读论文全文。
Engineering a Sort Function 论文 第2章 作者用于排序实现和优化的参考,未读论文全文。
计算机程序设计艺术 书 前言 作者推荐作深入数据结构与算法分析的参考,本次未读该书。
算法导论 书 前言 作者建议需要算法证明时查阅;当前未读取该书。
资金安全问题案例
问题标题 问题卡 解决方案卡(如有) 出现章节 一句话说明
实践卡进度
序号 实践标题 实践方式 状态(pending/done) 关联章节 产出
1 追踪堆队列的构建与维护 实现深读 done 第4章 ideas/idea-001-追踪堆队列的构建与维护.md(固定提交入口与初步映射)
2 追踪最短路径的候选队列 实现深读 done 第6章 ideas/idea-002-追踪最短路径的候选队列.md(固定提交入口与初步映射)

实践候选筛选:done;优先选择堆与最短路径两项成熟实现深读。计数排序与扫描线实验暂未采用:现有两项已覆盖数据结构与算法主链路,额外候选需先限定实际问题;概率认证示例暂不实践,书中协议安全条件不足。两项均为计划和首轮映射,完整阅读及测试尚未执行。

整书笔记是本轮内容和原文定位真源,已基于全文完成章节讲解和全书收束。

相关主题

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

暂无公开主题。