几何、排序与在线算法补缺

• 各结构的操作复杂度
• 内存布局与缓存
• 现实场景选型

栈（LIFO）与队列（FIFO）是访问受限的线性结构，适合函数调用、括号匹配、BFS 等；链表支持 O(1) 插入删除但缓存不友好，适合频繁增删且不随机访问的场景；散列表提供摊还 O(1) 的插入/查找/删除，是无序 K-V 查询的主力，但需处理冲突、扩容与哈希函数；二叉搜索树（及平衡树）提供有序性与 O(log n) 的查询/前驱后继/范围查询，适合需要有序遍历的场景。工程取舍围绕"访问模式"与"缓存局部性"：数组/栈/队列缓存友好，链表与散列表指针跳跃多，树结构介于其间。

数据结构的选型取决于操作的复杂度需求与内存布局。散列表以无序换取常数时间，树以系数换取有序性，链表以指针跳跃换取灵活增删，是工程取舍的典型代表。

• 比较型 vs 非比较型
• 稳定性与缓存局部性
• 工程实现细节

快排（如内省排序 introsort）在工业库中普遍采用，结合三路划分、随机/中位数基准与插入排序小段优化，平均 O(n log n) 且缓存友好；堆排最坏 O(n log n) 但常数大、缓存不友好，仅用于 introsort 的退化兜底；归并稳定、适合外部排序与链表，但需额外内存；计数、桶、基数是非比较型，其中基数排序按位多趟处理，适合整数/字符串，工程上用 LSD 与 MSD 变体，配合 SIMD 优化达高吞吐。变体取舍围绕稳定性、缓存、内存与最坏情况保证。

工业排序追求"平均高效 + 缓存友好 + 最坏可控"。快排以其缓存局部性成为默认，introsort 用堆排兜底，基数用键域换时间，体现了理论与实现的结合。

• 各方法的适用前提
• 最优子结构
• 摊还分析的场景

动态规划依赖最优子结构与重叠子问题，用状态转移表避免重复计算，适合最优化与计数问题（如序列 DP、背包、树形 DP）；贪心依赖贪心选择性质，局部最优推出全局最优，适合区间调度、哈夫曼编码等；分治把问题递归分解，适合归并、快排、最近点对等；摊还分析用于分析一系列操作的平均代价（如动态数组扩容、splay 树、势能法），说明为什么某些"偶发昂贵"操作整体摊还便宜。工程上，这些方法被广泛用于路径规划、资源调度、压缩编码与数据结构设计。

四种方法各有清晰的适用前提：DP 需最优子结构+重叠子问题，贪心需贪心选择性质，分治需可合并子解，摊还分析用于验证均摊复杂度。正确识别问题类型是工程应用的前提。

• B 树与磁盘 IO
• 斐波那契堆的理论 vs 实际
• van Emde Boas 的整数域

B 树（及 B+ 树）通过高扇出降低磁盘 IO 次数，是数据库与文件系统索引的核心，工程成熟度高；斐波那契堆理论上支持 O(log n) 减键、O(1) 插入，适合图算法（如 Dijkstra、Prim）的理论分析，但因常数大、实现复杂、链表内存开销高，实际工程中常被二叉堆或配对堆取代；van Emde Boas 树在整数域上实现 O(log log u) 的前驱/后继与插入删除，适合整数密集键的极低延迟场景，但因内存开销大（约 O(u)）不适合通用场景。工程取舍围绕 IO 次数、常数因子与实现复杂度。

高级结构常在理论复杂度与工程适用性间取舍。B 树以扇出换取 IO 效率，斐波那契堆与 van Emde Boas 因常数/内存代价在工程中较少直接使用，但支撑理论分析。

• 基数排序的键域分桶
• 缓存友好分桶
• 数据库连接优化

数据库的哈希连接（hash join）中，Radix Partition Join 用基数分桶（radix partition）把数据按哈希键高位分到多个桶，桶内再哈希，减少内存占用与缓存缺失，提升连接性能。Radix Sort 也用于排序算子的工程化：按位分桶后桶内排序，利用缓存局部性与顺序 IO 实现高吞吐排序。其优势在于避免比较操作、顺序访问内存、并行化友好，尤其适合大整数与长键；代价是需预分配桶与访存桶计数，对内存带宽敏感。

Radix Partition 通过"多趟高位分桶"把连接/排序的访问模式变为缓存友好的顺序访问，减少随机 IO 与冲突，是数据库引擎优化连接与排序的关键手段。

• 在线问题的竞争比
• deterministic 与 randomized 下界
• 场景匹配

在线顶点覆盖中，顶点逐个到达，算法需立即决定是否覆盖，且边界不可回溯。确定性算法存在竞争比下界 2（即不能优于 2 竞争比），经典贪心（到达即覆盖若非已覆盖）可达到竞争比 2。随机化算法在对抗性输入下可突破确定性下界，达到更小的竞争比（如 1.5 或更优），但依赖随机化与概率分析。竞争比衡量在线算法的最坏代价与离线最优的比值。工程上，若输入可预测用确定性简化，若对抗性强则用随机化降低最坏竞争比。

竞争比分析刻画在线算法相对离线最优的损失。确定性在线顶点覆盖有 2 下界，随机化引入概率打破该下界，体现"随机化在对抗性在线问题中的优势"。

• 旋转卡壳算法
• 对踵点对
• 单调指针推进

旋转卡壳（rotating calipers）在给定凸多边形上，用两根"卡尺"沿边旋转，逐一求出对踵点对（antipodal pairs）。由于对踵点随边旋转单调推进，可用双指针（two-pointer）在 O(n) 内遍历所有对踵点，其中每个顶点作为端点被访问常数次。基于对踵点可求凸多边形直径、最小外接宽度、最近点对等。O(n) 的推导依赖"对踵点索引随旋转单调递增"的性质，使整体线性。

旋转卡壳把"遍历所有对踵点"转化为"单调指针推进"，每个指针最多移动 O(n) 次，故总复杂度 O(n)。其前提是凸性与对踵点的单调性。

• 在线广告分配
• budget 约束
• 竞争比

Adwords 算法解决在线广告分配问题：广告主有预算，广告展示按关键词匹配，目标是最大化收益同时不超预算。基础版本达到 1-1/e 竞争比；广义版本（adwords，采用 scale factor 与随机化）处理不同预算与报价，保证在预算约束下的竞争比。工程实现中，常用贪心+随机化（如按报价比例分配剩余预算）、预算分流与流量控制来实时决策，并在预算接近耗尽时降低出价。算法需在在线到达、预算约束与收益最大化间权衡，达到竞争比保证。

adwords 是"在线匹配 + 预算约束"的经典问题，用随机化与缩放因子逼近最优竞争比 1-1/e。工程实现强调实时分配与预算控制。

• 方差缩减的动机
• 各技术的原理
• 工程应用

蒙特卡洛模拟中，方差缩减技术降低估计的方差、提高精度。Antithetic Variates（对偶变量）：配对使用负相关样本（如 U 与 1-U），抵消随机波动，方差可减半；Control Variates（控制变量）：用已知期望的相关变量作为对照，调整估计量以消除相关性噪声；Rao-Blackwellization（Rao-Blackwell 化）：用条件期望替代原始估计，因条件期望方差更小，是统计上"方差不为增"的经典技巧。工程上用于金融定价、统计推断、粒子滤波等，需权衡计算开销与方差收益。

三种技术都以"引入结构信息/相关性"来消除随机噪声。对偶变量用负相关，控制变量用已知变量，Rao-Blackwell 化用条件期望，共同目标是在相同样本量下降低方差。

• 鞅差序列定义
• 集中不等式
• 随机分析应用

Azuma-Hoeffding 不等式给出鞅差序列部分和的尾概率界：若鞅差序列每一差有界，则部分和偏离其均值超过 t 的概率以指数形式衰减。它用于分析依赖随机过程（如随机图演化、随机游走、在线学习中的累积误差）的收敛性。工程上用于证明随机算法（如随机化贪心、随机搜索）的近似保证、在线学习遗憾界的推导，以及随机二分/随机制造过程中的误差控制。其价值在于即使过程是依赖的，只要每次变化有界，就能获得集中界。

Azuma-Hoeffding 把"独立同分布"的集中分析推广到"鞅差"这一依赖但期望为 0 的序列，大大扩展了随机分析的适用面，是随机算法与在线学习分析的基础工具。

• 平面分割与空间分裂
• 遍历与剪枝
• 工程应用

BSP 树用平面递归二分空间，把物体/多边形组织到左右子树。光线追踪中，BSP 树按空间顺序遍历平面，沿光线方向剪枝被遮挡/反面区域，减少相交测试；碰撞检测中，用 BSP 分割空间快速定位候选物体集合，配合 AABB 进行粗筛。BSP 支持静态场景的预构建与高效遍历，但构建与平衡较复杂，动态场景需增量更新。其优势是空间分割适应场景几何，但相比 KD-Tree/Octree 在静态渲染中更常用。

BSP 树的核心价值是"用平面分割实现空间排序，支持沿光线/查询方向剪枝"。工程上需权衡构建复杂度与遍历效率，适合静态场景。

• 探索-利用权衡
• 各算法的适用场景
• 工程实现考量

UCB1 用上置信界选择动作，理论上达到最优累积遗憾，适合静止环境的确定性探索；Thompson Sampling 用贝叶斯后验采样，实现简单、表现稳健，适合非平稳与复杂环境；Contextual Bandits 引入上下文特征，用上下文感知选择动作，适合个性化推荐等场景；EXP3 面向对抗性环境，用指数权重保持竞争比，适合对手可能改变的环境。工程取舍围绕环境的平稳性、上下文可得性与遗憾保证：平稳用 UCB1/汤普森，有上下文用 Contextual，对抗性用 EXP3。

多臂老虎机算法在探索与利用间权衡，不同算法适配不同环境假设：UCB1 与 EXP3 理论清晰，Thompson Sampling 实现与稳健性俱佳，Contextual 结合特征。选型取决于环境性质与业务约束。

• Delaunay 三角剖分
• 约束边处理
• 工程应用

CDT 在 Delaunay 三角剖分基础上强制保留用户指定的约束线段（如地形中的断裂线、河流边界）。算法通过插入约束边、局部翻转（Flip）与恢复边（edge recovery）操作，在满足 Delaunay 准则（空圆性质）的前提下使约束边成为剖分的一部分。工程上用于地形建模、网格生成、有限元分析，需处理约束边相交、退化与退化 case。CDT 保证不改变约束边，且尽量满足 Delaunay 性质，用于创建符合几何约束的网格。

CDT 的精髓是"在 Delaunay 空圆性质与强制约束边之间取得平衡"，通过边恢复与局部翻转保留约束。它使网格既符合几何约束又具备良好的三角质量。

• 渐近记号与复杂度
• Master 定理
• 概率分析与势能法

CLRS Part I 建立算法分析的基础：用大 O/Ω/Θ 渐近记号描述复杂度增长；Master 定理求解分治递推式 T(n)=aT(n/b)+f(n) 的渐近界；概率分析用于随机算法与随机输入的平均时间复杂度；势能法（potential method）通过定义势函数分析摊还复杂度。工程语义是：用渐近记号衡量算法规模的扩展性，用 Master 定理快速求解递推，用概率分析评估随机化算法的期望行为，用势能法理解数据结构摊还操作的长期成本。这些工具是算法设计与复杂度论证的基础。

这些基础工具把"算法复杂度"从直觉提升为严格的数学论证。Master 定理免去递推求解，势能法统一解释摊还代价，概率分析处理随机性，共同构成算法分析的基石。

• CLT 的陈述
• 样本均值近似正态
• 置信区间与误差估计

中心极限定理指出：大量独立同分布随机变量的样本均值，其标准化形式近似服从正态分布，无论原分布如何。工程上，CLT 用于近似估计样本均值的分布、构造置信区间、评估蒙特卡洛模拟的误差（误差随 1/√n 衰减）、以及 A/B 测试中判断均值差异的显著性。它允许用正态近似处理任意分布的样本均值，从而简化统计推断。工程上需注意样本量足够大、样本独立同分布的前提。

CLT 的价值在于"无论原分布如何，样本均值收敛到正态"，使统计推断与误差估计可统一用正态工具。它是白盒统计、随机模拟与实验分析的基础。

• Chebyshev 不等式
• 弱大数律
• 概率界

Chebyshev 不等式给出随机变量偏离其均值超过 t 的概率上界：P(|X-E[X]|≥t) ≤ Var(X)/t²。它不要求分布假设，只需方差有限。结合样本均值，可证明弱大数律：样本均值依概率收敛于总体均值，因为样本均值方差随 n 减半，Chebyshev 界随 n 增大趋于 0。工程上用于粗略概率界、依赖宽松假设的收敛性证明、以及蒙特卡洛模拟中样本量选择与误差估计，是比 CLT 更宽松但更保守的工具。

Chebyshev 不等式因只需方差、无需分布假设而普适，是证明弱大数律与均值收敛的通用工具。其界较保守（二次衰减），但适用面广。

• 集中不等式的类型
• 尾概率界
• 随机算法的保证

集中不等式（如 Chernoff、Hoeffding、Azuma、McDiarmid）给出随机变量偏离其期望的指数衰减概率界，是分析随机算法性能的关键。工程上，用于证明随机化算法（如随机 MinHash、随机投影、随机采样）以高概率达到近似保证，估计随机算法的误差/失败率，以及在大规模数据中平衡精度与样本量。Chernoff 适合独立伯努利/泊松和，Hoeffding 适合有界独立变量，McDiarmid 适合依赖但有界差异的函数。它们让"高概率"的保证成为可量化的工程承诺。

集中不等式把"随机算法大概率正确"转化为可验证的指数界。选对不等式（独立/依赖、有界/无界）是给出 tight 保证的关键，是概率算法工程分析的基础。

• 点云采样
• 邻接构造
• 曲线重建算法

曲线重建从无序点云恢复原始曲线（如手绘轮廓、道路、骨架）。基本流程：用 Delaunay/ε 邻近等构造点间邻接，去除噪声与离群点，按局部方向/曲率连接点形成折线，保证连通与无自交。经典算法包括基于 Delaunay 三角剖分的 NN-Crust、基于最小生成树/局部邻接的贪心连接、以及基于局部计数的 marching 方法。工程上需处理采样密度不均、噪声、分支与端点，用参数化与平滑（如 B-spline）得到可用的曲线表示。

曲线重建的核心是"从离散点推断连续拓扑"：构造合理的邻接关系，再按几何特征连接。算法需在抗噪声与保真细节间权衡，是点云处理与几何重建的基础。

• 位宽与桶数
• 缓存与内存带宽
• 向量化

工程化的基数排序针对 32/64-bit 整数优化：按位分桶（如每趟 8/11 bit，32-bit 需 4 趟、64-bit 需 8 趟），桶计数用直方图统计，用前缀和定位写入位置，实现稳定排序。高吞吐优化包括：用多次小桶而非一次大桶以控制缓存、顺序访问内存提高带宽利用率、用 SIMD（如 AVX-512）向量化直方图与搬移、多线程并行分桶。64-bit 可采用 MSD/LSD 混合与多趟策略平衡趟数与访存。其吞吐优势来自非比较、顺序访问与向量化。

整数基数排序的高吞吐来自"非比较 + 顺序内存访问 + 向量化/并行"。工程实现的关键是缓存友好、桶数选择与 SIMD/多线程，以最大化内存带宽利用率。

• 专家权重更新
• 遗憾界
• 随机化选择

这些算法处理在线决策问题：维护一组专家/动作的权重，按观测到的损失用指数权重更新（权重乘以 exp(-η·loss)），再归一化。Randomized Weighted Majority 面向零和/对抗性损失，按权重比例随机选择动作，Hedge 是其对损失归一化的推广，Exponential Weights（EWA）是通用框架。它们保证遗憾界 O(√T)（随时间 T 的平方根增长），即累积损失接近最优专家的损失。工程上用于在线广告、预测、博弈与最优学习，需选择学习率 η 与处理损失尺度。

指数权重算法用"按损失衰减权重 + 随机按权重选择"实现探索-利用与对抗性保障，遗憾界 O(√T) 是其核心保证。工程实现的关键是学习率与权重归一化。

• GP 先验与后验
• 采样函数
• 贝叶斯优化流程

高斯过程是定义在函数空间上的随机过程，用均值函数与核函数（协方差）刻画面函数，给定观测后通过条件分布得到后验均值与方差。贝叶斯优化用 GP 作为代理模型，通过采集函数（acquisition function，如 EI、UCB、PI）在探索（方差大处）与利用（均值高处）间权衡，选择下一个采样点，逐步逼近全局最优。工程上需选择核函数（RBF、Matern）、处理超参数、管理协方差矩阵求逆的计算开销，并处理噪声观测。适用于低维黑盒优化（超参调优、实验设计）。

GP 提供"预测 + 不确定性"两者的后验，是贝叶斯优化的核心。采集函数把不确定性转化为采样决策，实现样本高效的全局优化，是黑盒优化的标准工具。

• Hoeffding 不等式
• PAC 学习模型
• 样本复杂度

Hoeffding 不等式给出有界独立随机变量和的尾概率界。在 PAC 学习中，用它推导样本复杂度：为保证学习器经验误差与真实误差之差不超过 ε 的概率至少 1-δ，需要的样本数 m 满足 m ≥ O((ln(1/δ))/ε²)。工程上，Hoeffding 界用于确定最小样本量、评估模型泛化误差的置信区间、以及设计主动学习/在线学习中的采样策略。它提供"样本越多误差越小"的定量刻画，是统计学习理论的基础。

Hoeffding 界把"样本量 → 泛化误差保证"转化为可计算的公式，是 PAC 学习样本复杂度的核心工具。工程上它指导采样规模与误差置信保证。

• Markov 不等式
• 期望与概率
• 粗略界

Markov 不等式：对非负随机变量 X，P(X ≥ a) ≤ E[X]/a。它只需期望信息，无需分布或方差假设，给出粗略但普适的概率上界。工程上用于在信息不足时快速估计随机变量的"了不起事件"概率、作为推导更精细不等式（Chebyshev、Chernoff）的基础、以及蒙特卡洛模拟中的粗估计。其界较保守（线性衰减），但只要有期望就能用，是概率分析的起点。

Markov 不等式是最基础的集中工具，只需期望即可给出线性概率界。它常作为复杂不等式的起点，工程上用于快速粗糙估计与理论推导的基元。

• MTS 定义
• 竞争比
• k-server 与 MTS 的关系

Metrical Task System（MTS）是统一在线优化问题的框架：系统状态在度量空间移动，任务到达后需选择状态以最小化移动代价与任务代价之和。k-server 问题是 MTS 的特例：状态对应 k 个服务器位置，任务对应请求某点。MTS 的竞争比上界由度量空间维度决定（如 d 维有 O(d) 竞争比算法），k-server 问题在确定 k 时竞争比为 k。该框架统一了缓存、页面置换、k-server 等在线问题的分析，通过工作函数/势函数方法给出竞争比保证。

MTS 把"状态空间 + 移动代价 + 任务代价"抽象为统一框架，k-server 是其特例。利用该框架可迁移状态转移与势函数分析，得到竞争比上界。

• Minkowski Sum 定义
• 配置空间
• 碰撞检测

Minkowski Sum 定义为 A ⊞ B = {a+b : a∈A, b∈B}。在机器人运动规划中，机器人几何与障碍物的 Minkowski Sum 构成"配置空间障碍"（C-obstacle）：机器人位于 p 时与障碍物碰撞当且仅当 p 落在 Minkowski Sum 内。通过把机器人缩为点、障碍物膨胀为 Minkowski Sum，碰撞检测简化为"点是否在膨胀区域内"。工程上用于计算 C-space、碰撞检测（如 GJK 算法用 Minkowski 差判定相交）、以及路径规划中的自由空间构建。Minkowski Sum 的凸多边形计算可达 O(n+m) 或 O(n log n)。

Minkowski Sum 把"机器人-障碍物碰撞"转化为"点-膨胀区域包含"，是运动规划与碰撞检测的几何基础。其凸性使计算可高效完成。

• Algorithm R 的均匀性
• Algorithm Z 的跳过优化
• 流式大规模动机

Reservoir Sampling 从未知大小的流中均匀采样 k 个元素。Algorithm R 是基础版本：维护大小为 k 的样本池，对第 i 个元素以 k/i 概率替换池中随机元素，保证均匀性，但每个元素都要生成随机数并比较，开销大。Algorithm Z 采用指数跳过（exponential jumps）技术，用随机变量直接跳跃跳过大量无需替换的元素，减少随机数生成次数，大幅降低 CPU 开销，适合大规模流。Algorithm R 简单直观，Algorithm Z 高效，适用于超长流。

Algorithm Z 用"跳跃到下一个被替换元素"替代逐元素判断，保留均匀性同时减少随机数调用，是工程上对大规模（尤其大数据集）流式采样的关键优化。

• SIMD 处理直方图与搬移
• VPSHUFB 查表
• 向量化分桶

SIMD Radix Sort 用向量指令并行化基数排序的直方图统计与数据搬移。AVX-512 提供 512-bit 向量，可一次处理多个 key 的位提取与桶计数；VPSHUFB（byte shuffle）作为查找表，可在一趟内对字节做映射/桶定位，加速分桶。向量化使直方图计算、前缀和与重排（partition）大量并行，减少指令数与内存往返。工程上需处理末位余数、跨向量边界与桶间依赖，配合 AVX-512 的 gather 实现高效重排。SIMD 基数排序在整数排序吞吐上接近内存带宽上限。

SIMD 基础排序的关键是"向量化位提取、直方图与重排"，用 VPSHUFB 做并行查表、AVX-512 做宽的并行处理，把内存带宽转化为实际吞吐。

• MinHash 与 Jaccard
• SimHash 与余弦
• 误差界

MinHash 估计集合的 Jaccard 相似度：对集合中元素做随机排列，取最小哈希值，两个集合的最小哈希相等概率恰为 Jaccard 相似度，通过 k 个独立哈希取平均得到无偏估计，误差随 k 减小（标准差 ~1/√k）。SimHash 估计余弦相似度：用随机超平面把向量投影到符号，两个向量符号相同的概率与余弦角度相关，多个随机投影的汉明距离反映余弦相似度。两者都用"随机投影 + 平均"获得近似估计，误差界由投影数量 k 决定，配合集中不等式给出高概率保证。

MinHash 与 SimHash 都利用"随机变换下相似度与投影相等概率的等价关系"，用 k 个独立投影估计相似度，误差随 k 衰减。这是大规模近似相似度检索的基础。

• k-server 竞争比
• work function 定义
• 势函数分析

k-server 问题中，k 个服务器在度量空间移动以服务请求，目标是总移动距离最小。确定性算法有竞争比下界 k，最优确定性算法（如 work function algorithm）达到 2k-1 竞争比。work function 定义为"在满足服务历史的前提下，将服务器配置到某状态的最小代价"，以其为势函数可证明算法在线代价不超过常数倍最优代价。工程上，work function 需在每次请求后更新，复杂度高，实际常用近似（如 double coverage）平衡。竞争比保证算法在线损失相对离线最优有界。

work function 以"最优离线状态的最小代价"为势函数，结合势函数论证给出确定性上界 2k-1。它把在线问题与离线最优联系起来，是 k-server 分析的核心工具。