高级数据结构与在线算法

• word RAM 模型与比较模型的区别
• 基数排序/前缀排序突破比较下界
• 整数排序的下界与字符串排序

比较排序的 Ω(n log n) 下界建立在“只能比较元素”的模型上。字符串在 word RAM 模型下可按字符/字节做基数排序、前缀排序（如后缀数组的排序、快速傅里叶或后缀排序），利用字的位运算并行处理多个字符，从而突破比较下界。整数排序在 word RAM 下可达到 O(n√log log n)（Han 等），字符串可利用其作为子程序对后缀/前缀排序，得到同样界。字符串排序不用比较模型，而是把字符放入字中并行处理，因此下界不再适用。

关键区别是“比较模型”与“word RAM 算术模型”。word RAM 的字长 w=Θ(log n) 允许用位运算同时处理多个字符，把排序降为整数操作，从而获得比 Ω(n log n) 更低的界。

• 会计法的平摊分配
• 用 credit 预存扩容成本
• 平摊分析步骤

会计法给每个操作分配平摊代价，其中一部分“存起来”作为 credit 供未来操作使用。对动态数组：每次 push_back 分配 3 个币（1 个用于本次插入，2 个存为 credit）。扩容时（数组满，倍增到 2 倍），需要复制 n 个元素，正好用之前累积的 credit 支付（每次插入存 2 个，扩容前元素数 n/2 时已有 n 个 credit）。因为每次 push 只分配常量 3，总平摊代价 O(1)，总 credit 非负（不欠费），故每次 push_back 平摊 O(1)。

会计法关键是“预存费用覆盖未来昂贵操作”。扩容成本 O(n) 被前 n/2 次插入各存 2 币覆盖，保证每次 push 平摊 O(1)，且 credit 永不为负，证明合法。

• 按秩合并与路径压缩
• α(n) 的定义
• 平摊分析的复杂性

并查集用两个优化：按秩合并（union 时把秩小的根挂到秩大的根下，树高 O(log n)）与路径压缩（find 时把路径上所有节点直接挂到根）。联合后，m 次操作的时间为 O(m·α(n))，其中 α 是 Ackermann 反函数（超慢增长，n 小于 2^65536 时 α≤4），近似常数。证明复杂：用“秩的分层”与“节点被压缩的次数”分摊，路径压缩使节点在多次 find 中只被压缩有限次，且压缩次数按秩的指数塔分层受限。因此近似 O(1)。

α(n) 来自 Ackermann 函数的反函数，其增长速度极慢，使并查集实际可视为常数。时间来自“秩层级 + 压缩次数”的精细分摊，是平摊分析中最难的经典证明之一。

• 平摊分析三工具（会计/势能/聚合）
• 各种数据结构平摊操作
• 动态树

平摊分析主要在聚合分析、会计法、势能法三类。栈：push/pop 平摊 O(1)（势能=栈大小）。队列用两个栈实现时，转移用平摊 O(1)。双端队列（deque）可用环形数组或两 stack 分摊。计数器：二进制计数器 increment 平摊 O(1)（势能=1 的个数）；双向计数器支持 inc/dec 时平摊 O(1) 但需更多分析。动态树（splay tree、link-cut tree）的查询/修改平摊 O(log n)，用势能法（势能=树的对数秩和）证明。Karp 的 17 个结构集中展示了平摊分析在“看似昂贵单一操作”上的应用。

平摊分析把“个别昂贵操作”摊到一系列操作上。栈/计数器用简单势能，动态树用复杂势能（秩），体现不同结构对势能函数的选择差异。

• FWF（flush when full）标记算法
• LRU 的最近最少使用
• 等价性论证

FWF（Flush-When-Full，标记算法）在每个阶段（自上次全清空以来）标记访问过的页，当缓存满时清空所有未标记页再全换入。LRU 在每个阶段淘汰“最近最少使用”的页面。两者等价性的论证：在访问序列上，FWF 与 LRU 选择淘汰的页面集合相同（LRU 淘汰的是上个阶段未访问的页，FWF 也淘汰未标记页），且都能保持相同的缓存内容集。因此 FWF 与 LRU 在相同访问序列下产生相同的命中/缺失，竞争比相同（都是 k-competitive，k 为缓存大小）。

marking（标记）算法与 LRU 在“淘汰未访问页”上一致：FWF 按阶段标记-清空，LRU 按最近访问淘汰，两者对同一序列的缺失相同，故等价且竞争比相同。

• OPT 的 Belady 最优规则
• LRU 与 FIFO 的竞争比
• 缓存大小 k 的竞争比

Belady's MIN（OPT）是离线最优：淘汰“未来最远才被访问”的页，达到最小缺失数，是下界。LRU 与 FIFO 的竞争比都是 k（缓存大小 k 时，在线算法缺失 ≤ k×OPT 缺失 + k），即 k-competitive。证明：LRU 在 k 个页的窗口内，若 OPT 缺失则 LRU 必有命中，建立 on/off 缺失的对应。FIFO 同样 k-competitive。竞争比 k 表示在线算法最坏多换入 k 倍，无法再改进（k 是下界）。

OPT 用“未来最远”作为 oracle，LRU/FIFO 用“过去信息”近似，竞争比 k 反映有限信息下在线算法的理论代价。OPT 给出最优下界，LRU/FIFO 达到 k-competitive。

• 各类竞争比
• LRU 的 k-competitive
• FIFO/LFU 的竞争比

经典结论：LRU 与 FIFO 都是 k-competitive（k 为缓存大小），是最优在线竞争比（下界 k）。LFU（淘汰最不频繁使用）不是 k-competitive，最坏竞争比可以任意大（因为 LFU 基于历史频率，可能保留不再使用的页）。题目中“FIFO 4-competitive”可能是特定上下文（如 k=4 或某种变体/受限分析），但一般结论是 FIFO 与 LRU 同为 k-competitive。LFU 常因频率信息误导而竞争比无界。竞争比 k 已是最优（Fiat，任何确定性在线算法 ≥ k）。

LRU/FIFO 用“近期/顺序”信息，达到 k-competitive 最优；LFU 用“频率”信息，在访问模式变化时失败，竞争比无界。竞争比下界 k 说明有限信息下无法更强。

• 秘书问题的最优策略
• 1/e 的采样阈值
• 工程语义

Secretary Problem：n 个候选人依次到达，拒后不可再选，需选最优。最优策略是跳过前 n/e 个（约 37%）只观察记录其最大值，之后选第一个超过该最大值的候选人。该策略选中全局最优的概率为 1/e ≈ 0.368。工程语义：在无法回头、信息未知的决策中，用“先学习后行动”的阈值分割，把最优概率最大化。应用：招聘（先观察一批再录）、广告投放、股票择时、在线拍卖。

1/e 是“探索-利用”的平衡点：前 37% 用于学习分布，后续用阈值决策。这是在线决策的经典最优策略，后来拓展到租售、拍卖、在线广告等。

• 最优停止的动态规划
• indicator variable 的期望
• 1/e 证明

用动态规划建模：设 f(t) 为“已观察到 t 个时继续决策”的最优期望，递推比较“选择当前”与“继续”的期望。最优策略是阈值式：前 t 个跳过，之后若当前候选人优于之前所有则接受。用 indicator variable 证明概率：设阈值 k=⌊n/e⌋，若全局最优位置在 k+1..n 且其位置前的候选都小于它，则选中。对每个可能的最优位置 t，计算选中概率，求和得 ≈1/e。动态规划给出最优性，indicator 给出精确概率，两者互补。

DP 保证最优策略结构（阈值），indicator 变量把“选中最优”的概率分解为各位置的条件概率，乘积求和得 1/e，是证明的标准方法。

• 比较下界 vs 算术下界
• 可计算函数族的计数下界
• w=Θ(log n) 的特殊性

比较排序的 Ω(n log n) 下界来自决策树（比较模型）。在 word RAM（字长 w=Θ(log n)）下，排序可通过位运算、基数排序达到更小（如 O(n√log log n) 或 O(n log log n)），故比较下界不成立。但存在“代数/计数下界”：对可计算函数族，若函数输出需区分 n! 种排列，则需至少 log(n!) = Ω(n log n) 位，即信息论下界在小字长下仍约束。边界在：w 足够大时（w≥n log n）可用位并行突破；w=Θ(log n) 时靠算术/桶突破比较下界但受信息论码长限制。决策树（比较）下界与可计算函数（信息论）下界是不同来源。

关键在于“比较下界”与“信息论下界”不同。word RAM 用算术绕过比较下界，但 Ω(n log n) 位的信息论下界在小字长下仍存在（除非字长足够大支持位并行）。这就是为什么排序下界与模型强相关。

• rank/select 的块划分
• 预计算表（lookup table）
• 表大小与 O(1) 的关系

在 bitvector 上求 rank（某位前 1 的个数）、select（第 k 个 1 的位置），O(1) 需要预计算：把 bitvector 分成两级块（大块 + 小块），对每块预存 rank 累加值；小块内用预计算查找表（lookup table）按“块内容 + 位置”查 rank。表大小依赖块大小。若块大小 w（字长），则块内子模式数量最多 2^w，查找表需 N=2^w 项（对每个可能的块掩码和位置），故 O(1) 依赖 N=2^w 的预计算表。字长 w 内 O(1) 查表，块外累加。这是“空间换时间”的经典，表大小与块大小决定空间。

rank/select 的 O(1) 建立在“分块预计算 + 块内查表”。块内可能的子模式数是 2^w，因此查表需 2^w 项，这就是依赖 N=2^w 预计算的原因。块大小选择权衡表大小与扫描长度。

• 内点法对线性规划
• 平滑复杂度概念
• ILP 实测

Karmarkar 内点法在多项式时间内求解线性规划（LP），其复杂度在理论上是多项式但常数依赖矩阵规模。对 ILP（整数线性规划），内点法通常用作松弛（LP 松弛）后配合分支定界。平滑复杂度（smoothed complexity）分析：真实数据的小扰动使算法平均表现远好于最坏；在 ILP benchmark 上，内点法迭代次数通常很少（几十次），几乎与问题规模无关，分布集中在较小值，远优于最坏上界。这印证了“平滑数据下内点法很快”的实测现象。

内点法理论最坏是多项式但常数大，实测在 benchmark 上收敛快（迭代次数少且分布集中）。平滑复杂度解释了“最坏 vs 平均”的差距，是分析与实测结合的例子。

• 线段树的一维结构
• 二维范围树（每节点内嵌一维树）
• O(log² n) 查询

Range Tree（二维正交范围树）在第一维上用线段树（按 x 排序），每个节点存储该 x 区间内点的 y 值构成的一维线段树/平衡树。构造：先建 x 维线段树，每个节点收集其区间内点并建 y 维树，总 O(n log n) 空间。查询二维矩形 [x1,x2]×[y1,y2]：先在 x 维上找到覆盖 [x1,x2] 的 O(log n) 个节点，对每个节点在其 y 维树上做 [y1,y2] 计数/查询，每步 O(log n)，总 O(log² n)。这是二维正交查询的标准结构。

二维范围树用“两维嵌套线段树”，把二维查询分解为 x 维 O(log n) 个节点 × y 维 O(log n) 查询，得 O(log² n)。空间 O(n log n) 是嵌套的代价。

• 在线决策的阈值策略
• 各场景的建模
• 1/e 的适用

Secretary Problem 的“先观察后决策”阈值思想在工程中广泛复用：广告投放——在有限预算内先观察广告点击率分布，再决定投放策略；招聘——先面试一批建立标准，再择优录用；股票择时——观察价格走势后选择买入点；Job scheduling——在线任务到达时选择最优任务处理。共同点是“不可回退、信息未知、需最大化最优选择概率”，用 1/e 阈值做探索-利用平衡。工程上常把 n 视为未知或动态，扩展为“启发式阈值”或“随时间衰减的接受概率”。

核心是“探索-利用”的在线决策框架。1/e 阈值是教科书最优，工程上针对未知 n、异质价值做变体（如设置接受概率随经验递减），但保留了“先学后择”的结构。

• Z 函数做周期判定
• Duval 最小表示
• 工程取舍

Z-function 可判定字符串周期：若 n 是 k 的倍数且 Z[k] ≥ n−k，则 k 是周期。用 Z 数组 O(n) 判断，比枚举快。Duval 算法求最小表示（最小旋转）与 Lyndon 分解，O(n)。工程取舍：Z 函数简单、易实现、适合判周期与匹配；Duval 最小表示实现稍复杂但线性、无哈希碰撞，适合求循环同构最小者。若需哈希的快速或确定性无碰撞，Z/Duval 更稳；若需常数小且允许哈希，可用滚动哈希。工程上：判周期用 Z，最小表示用 Duval，二者都确定性线性。

Z 与 Duval 都确定性、线性、无碰撞，适合需要精确结果的场景。取舍在实现复杂度与适用场景：Z 判周期直观，Duval 求最小旋转专用，哈希仅作快速替代。

• fusion tree 的排序数组分块
• sketching 与位并行
• O(log n / log w) 复杂度

fusion tree 用排序数组 + 每块 w 个字的“sketch”实现子线性搜索。它对每个节点内的 w 个关键字做“位压缩”（sketching），把关键字映射到少量关键位，用位并行指令（如 LDL/bit select）在 O(1) 内比较多个关键字，从而找到分叉点。每个节点有 O(w) 个关键字，树深度 O(log_w n) = O(log n / log w)。64-bit 字长下 w=64，深度 O(log n / 6)，搜索 O(log n / log w)。实现细节：用位图/位操作在常数时间做“多少关键字小于 x”的 rank 查询，配合 sketch 压缩关键字宽度。

fusion tree 的突破是用“位并行比较多个关键字”把每个节点的分支数从常数提到 w，从而把树降为 O(log_w n)。sketch 压缩关键字 + 位操作 rank 是核心。

• vEB 树的递归结构
• O(log log u) 复杂度的来源
• 与探针下界的关系

vEB 树按字长 u 递归分成 sqrt(u) 个簇，每个簇存一层，加上一个高层汇总，实现插入/删除/查找 O(log log u)。复杂度来自递归深度 log log u（每次把 u 开方）。它与探针下界的联系：在“单元字长”模型下，惰性/非平衡方案的探针下界是 Ω(log log u)，vEB 树达到该下界。字典树（trie）按位分叉的深度是 log u，vEB 通过“高位表 + 低位簇”把结构层次压缩到 log log u，哈希则用 O(1) 期望但失去最坏保证。vEB 是理论最优的“搜索位”结构。

vEB 的 O(log log u) 来自“分簇递归”把 u 逐层开方，形成 log log u 层。它达位探针下界，而字典树是 log u，哈希是随机 O(1)。三者是“结构递归 vs 位分叉 vs 哈希”的对比。

• 懒标记的延迟更新
• 区间更新/查询复杂度
• 实现要点

懒标记（lazy propagation）让区间更新不立即下推到叶子，而是记录在节点上（挂 lazy 标记），只有需要访问子节点时才下推。这样区间更新/查询都是 O(log n)（只覆盖完整节点）。实现要点：1) 更新时若当前节点区间完全被覆盖则直接更新节点值并打标记，立即返回；2) 否则需先 push 下推标记给子节点，再递归更新不完整区间；3) 查询时同样先 push 再合并。标记表示“该区间待执行的统一更新”，保证子节点在使用前已应用。

懒标记把“多次叶更新”合并为“节点级延迟更新”，使区间更新与查询同为 O(log n)。关键在 push 的时机（访问子节点前）与覆盖判断，避免重复下推。

• 树状数组的区间求和/更新
• 区间最值
• 区间加+区间和

树状数组（Fenwick）支持单点更新 + 前缀/区间和查询 O(log n)，也支持区间加 + 单点查（差分）或区间加 + 区间和（两个 BIT）。但区间最值（RMQ）与“区间加 + 区间最值”等需要懒标记的操作，树状数组难以实现（BIT 只累积前缀，无法懒更新区间），需用线段树（支持懒标记）。线段树通用性强，支持区间加/赋值 + 区间求和/最值/最大子段等，但常数与空间更大。结论：区间最值、区间修改（区间加/赋值）通常只能用线段树（或分块/平衡树）。

树状数组依赖前缀可加性，适合“和/异或”类操作；线段树靠节点结构支持区间聚合与懒标记，适合“最值/区间修改”等不可逆差分的操作。选型看操作类型。

• Manacher 的奇偶回文半径
• 回文树（Eertree）
• 工程取舍

Manacher 用中心扩展+对称复用求每个中心的最长回文半径（奇 d1、偶 d2），O(n)，适合求最长回文子串、回文半径数组。回文树（Eertree/PAM）用两棵树（奇偶根）在线构建回文子串的自动机，O(nα) 或 O(n)，能统计每个回文子串的出现次数、本质不同回文子串数。工程取舍：Manacher 简单、常数小、适合求半径/最长回文；回文树功能更强（统计、在线、可查询所有回文），但实现复杂、常数大。需求是“最长回文”用 Manacher，需求是“回文子串统计/枚举”用 PAM。

Manacher 专注于“半径”，PAM 专注于“回文子串集合”。Manacher 轻量、PAM 功能全，取舍在功能需求与实现/常数成本之间。

• SAM 的 len、link、转移数组
• 状态上界 2n−1
• 工程语义

SAM 每个状态维护：len（该状态代表子串的最大长度）、link（指向最长真后缀所在状态）、转移（读字符后到达的状态）。这些数组支撑“子串匹配、出现次数、最长公共子串”等查询。状态上界 2n−1：因为每个新字符插入时最多新增 2 个状态（一个字符串状态 + 一个分裂状态），所以总状态 ≤2n−1，转移 ≤3n−4。工程语义：上界保证 SAM 内存 O(n)，可安全分配 2n 数组；link 树（parent 树）结构便于统计 endpos 与出现次数。这是 SAM 线性性与工程实现的基石。

len/link/转移构成 SAM 的完备结构，2n−1 上界来自“每次插入至多分裂一次”，保证线性内存。工程上用 len 数组滚动、link 树后序统计，是其高效实现的关键。

• 回文树的奇偶根
• addChar 在线插入
• 状态上界 O(n)

回文树（Eertree/PAM）用两个根分别表示“空串”（偶长度根）与“单字符”（奇长度根），支撑奇偶回文的统一构建。addChar 在线读入字符，沿 fail 链找到最长回文后缀，尝试扩展成新回文，若出现新回文则新建状态并连 fail。最多 n 个不同回文子串（本质不同回文子串数 ≤n），故状态上界 O(n)。工程价值：在线构建、O(n) 内存、可统计每个回文的出现次数与长度，是回文问题的高效工具。

双根让奇偶回文统一处理，alphabet 转移构造回文森林，fail 链保证在线扩展。状态数 ≤n 保证空间线性，工程上可分配 2n 数组。

• labelled 用 EGF、unlabelled 用 OGF
• 集合/循环/序列的组合构造
• 指数/幂级数运算

labelled 结构（元素有标号）用指数生成函数（EGF），其集合/循环/序列操作对应 exp、log、1/(1−·) 的指数形式；unlabelled 结构（无标号）用普通生成函数（OGF），组合操作对应普通的幂级数（MSET/SEQ/CYC 用乘积、重复组合）。差异：labelled 的“集合”用 EGF exp，unlabelled 的“集合”用 MSET 构造（含重复计数）；循环 labelled 用 log，unlabelled 用 CYC 的 phi 项。工程上用于计数组合对象（树、排列、图）。

EGF 与 OGF 的选择取决于元素是否带标号，其组合操作（集合/循环/序列）的生成函数算符不同。labelled 用 exp/log/封闭形式，unlabelled 用幂级数/Φ 项，是解析组合学的核心。

• 外部排序的输入分布
• 构造最坏退化输入
• black-box 基准设计

外部排序库的最坏退化通常来自：输入几乎有序/逆序（触发融合退化）、重复键、特定块大小导致的分块退化。设计 black-box benchmark：1) 生成多种输入（随机、逆序、几乎有序、全同、周期、大块偏序）；2) 对每种输入测量排序时间与 I/O 次数；3) 对比库输出的时间-输入规模曲线，检测是否出现超线性退化（如 O(n²)）；4) 用不同块大小/内存限制重复以暴露参数敏感性。以“不知道分布”的视角，用代表性与极端输入覆盖可能的最坏情况，识别退化。

最坏退化测试需构造能触发库内部算法（归并、替换选择、基数）失效的输入分布。通过多分布+规模缩放+参数扫描，black-box 识别退化而无需知道库内部实现。

• AC0 电路定义
• PARITY 不在 AC0
• Furst-Saxe-Sipser 思路

AC0 是常数深度、多项式规模、AND/OR/NOT 门电路类。Furst-Saxe-Sipser 证明 PARITY（奇偶）不在 AC0：思路是用随机限制（random restriction）把 AC0 电路化简为退化电路。对每个输入位随机固定为 0/1（或保持），常数深度电路在随机限制后，每层门被化简，电路深度降低，最终收缩为常数/简单函数；而 PARITY 在随机限制后仍保持“非退化”结构（不可能被常数函数逼近）。因此 AC0 无法计算 PARITY。这也揭示 AC0 与 AC0[p]（带模门的深度）的分离。

随机限制是证明 AC0 不能算 PARITY 的核心：限制自变量后，AC0 电路被“拉平”成常数函数，而 PARITY 保持依赖，矛盾。这是电路复杂度的经典下界证明。

• OPT 的淘汰规则
• 最优性上界
• offline 性质

Belady's MIN（OPT）淘汰“未来最远才被访问”的页，是离线最优，给出最小缺失数，是所有在线算法的下界（oracle）。它是最优的：证明交换论证（对未来某页，若 OPT 淘汰非最远页，可交换不增加缺失）。OPT 的上界即“最少可能缺失数”，在线算法无法优于它。工程上 OPT 用于计算当下界、评估在线算法（LRU/FIFO）的竞争比，虽不可在线实现但在分析中作 oracle。

OPT 用“未来信息”作 oracle，是离线最优，其缺失数是最小可达值。在线算法竞争比以 OPT 为基准，反映有限信息的代价。

• Conservative 类（LRU/FIFO）
• 随机化 Paging
• 竞争比

Conservative Paging（LRU、FIFO 等）是确定性在线算法，竞争比 k（k-competitive），达到确定性最优。随机化 Paging 算法（如 RANDOM、随机标记）可用随机化提高竞争比，但下界：任何随机化算法竞争比 ≥ H_k（第 k 个调和数，约 ln k），比确定性 k 好。Aequo-Optimal 指“等最优”类，即达到该类最优竞争比的算法。结论：确定性（conservative）竞争比 k，随机化可到 H_k（下界），随机化优于确定性但无法任意好。

确定性 best = k，随机化 best = H_k ≈ ln k，随机化通过概率降低最坏缺失。Aequo-optimal 是达到该下界的算法，体现确定性 vs 随机化的竞争比差异。

• rank-r 选择
• matroid secretary
• 竞争比/概率

经典秘书问题选“最优”，推广到选“前 r 名最优”（rank-r selection），或选“满足 matroid 约束的集合”中的最优（matroid secretary problem）。rank-r 版本优化的目标是选中 r 个中尽量多的高排位者。matroid secretary 要求选出的集合独立（如每条边至多选一个 = 匹配 secretary），用随机化阈值/采样算法，竞争比通常为 O(log r) 或常数（取决于 matroid 类型）。这些扩展把“单一最优”的 1/e 扩展到“多选+约束”场景，用于在线拍卖、资源分配。

推广把“选一个最优”变为“选多个满足约束的最优集合”，需结合 sampling + 阈值 + matroid 结构。竞争比与选择集合的约束复杂度相关，是主流在线算法研究。

• 重要性采样原理
• 方差缩减
• 工程实现

重要性采样（importance sampling）估计期望 E[f(X)] 时，用更“匹配被积函数”的分布 Q 采样，权重 w(X)=p(X)/q(X)，得 E_Q[f(X)w(X)]。选择 Q 在 f 贡献大的区域多采样，可显著降低方差（方差缩减）。工程：自适应调整 Q（如用均值/方差估计）、用分层/控制变量减少方差、谨慎处理权重过大（防数值不稳定）。在罕见事件估计、蒙特卡洛优化、强化学习（off-policy）中广泛使用。

方差缩减的关键是选 Q 使重要性权重 w 的方差小，即 Q 与 |f|p 成比例。工程上通过估计最优 Q、分层、控制变量实现，权衡偏差与方差。

• KD-Tree 的维度轮换切分
• 中位点选择
• 范围/最近邻查询

KD-Tree 建树时按轮换维度（depth mod k）选择当前维度的中位点作为分割点，左右子树分别对应小于/大于该维的子集，用 nth_element（O(n) 中位数选择）保证平衡、树高 O(log n)。范围查询：递归检查节点是否与查询矩形相交，剪枝不相交子树，平均 O(√n + 输出)。最近邻：优先访问更近子树，用距离下界剪枝另一子树，平均 O(log n)（高维退化 O(n)）。维度轮换保证各维均匀分割。

中位点让每层平衡，维度轮换让各维共享切分。范围/最近邻用“空间剪枝”减少访问，平均高效、最坏退化（高维）。

• LCT 的 access/splay 操作
• 动态树维护
• 复杂度

Link-Cut Tree（LCT）维护动态树（加边、删边、路径查询/修改）。核心操作：access(v) 把 v 到根路径上的偏好路径打通，使其成为一条实路径（用 splay 维护）；splay(x) 把 x 旋转到所在 splay 的根；expose 即 access。路径查询/修改通过 access 后对路径 splay 处理。加边 link、删边 cut 各用 O(log n) 平摊。LCT 用“实路径偏爱剖分 + splay 森林”实现动态树的各种操作 O(log n) 平摊。

access 重排偏好路径，使路径成为单一 splay，查询/修改均在 splay 上作 O(log n)。splay 的平摊保证 LCT 总复杂度 O(log n)。

• Lyndon 分解
• 最小表示法
• 循环串匹配

Lyndon 分解把串分解为单调递减的 Lyndon 词，O(n)；最小表示法（Duval）求循环同构串的字典序最小者，O(n)。循环串匹配：若两个串互为循环移位，则它们的最小表示相同（规范化），可先求最小表示再做普通匹配，从而把“循环同构判定”化为“相等判定”。工程价值：循环消除（规范化）用于去重、旋转后匹配、环形结构比较，算法确定性线性、无碰撞。

最小表示是循环串的“规范形式”，两个循环同构串的最小表示相等，这是循环匹配的规范化技巧。Duval 线性实现，工程上可靠。

• 在线二部图匹配
• Ranking 算法
• 竞争比 1-1/e

在线二部图匹配中，左部点（或右部点）在线到达并匹配。Ranking 算法：给右部点随机赋一个 rank，左部点到达时匹配到其邻居中 rank 最高的未匹配右部点。它实现 1−1/e 的竞争比（期望匹配数 ≥ (1−1/e)×OPT），是随机化在线匹配的最优。工程价值：广告拍卖（在线广告商-广告位匹配）、在线任务分配、动态资源分配，用随机优先级保证近似最优，且实现简单、可扩展。

Ranking 用随机优先级避免贪心可能的最坏退化，1−1/e 是随机化在线匹配的最优竞争比（下界匹配）。工程上用于无法预知全部输入的大规模在线匹配。

• 切换引理内容
• 随机限制
• 常数深度下界

Håstad 切换引理：对常数深度电路做随机限制（随机固定部分输入），使 OR/AND 门可安全地“切换”成 AND/OR 或退化为小深度，从而把电路层数压缩。用它对 PARITY 的 AC0 电路反复做随机限制，方法是用切换引理把每层门化简，使电路深度下降、最终变为常数深度或常数函数；而 PARITY 在随机限制下仍保持高依赖（不能化简为常数函数），矛盾。因此 PARITY∉AC0。这是 AC0 下界的核心工具，也用于证明 AC0 无法计算多数函数等。

切换引理保证“随机限制后电路深度可降”，是用随机限制把 AC0 电路“拉平”而 PARITY 保持的关键。它把电路复杂度化为随机限制下的函数退化分析。

• 局部搜索算法
• 平滑分析框架
• k-median/k-means 的平滑界

局部搜索（如 k-median/k-means 的交换/移动聚类）通常最坏是局部最优（可能差），但平滑分析显示：在输入加高斯扰动后，局部搜索的收敛与质量接近最优。Pertesi 风格框架把“不良配置”集合的测度与扰动后落在其中的概率联合分析，证明扰动后局部最优的质量接近全局最优，且收敛步数多项式。工程意义：局部搜索在真实数据（带噪声）上表现稳定，平滑分析为“实测好用”提供理论依据。

平滑分析用“扰动后落到坏区域概率小”把最坏局部最优排除，证明 k-means/k-median 局部搜索在平滑数据上多项式时间且接近最优。这把经验上的“局部搜索好用”形式化。

• 群作用与等价类
• Pólya 定理与 cycle index
• 具体计数例子

Pólya 枚举定理：在群 G 作用下，用颜色集着色的不等价着色数 = cycle index polynomial 代入颜色数。Cycle index 是 G 中每个置换的循环类型的平均：Z(G) = (1/|G|)Σ ∏ x_i^{c_i}（c_i 为 i 循环数）。例：正方形 4 个顶点用 2 色（红/蓝）着色，D4 群（8 个置换）的 cycle index 代入 (2,2,2,2) 得不等价着色数 = (2^4 + 2·2^3 + 3·2^2 + 2·2^1)/8 = (16+16+12+4)/8 = 6。定理把等价类计数化为群置换的循环类型求和，避免逐类枚举。

Pólya 定理用 cycle index 汇总群的结构，把“等价类计数”降到“每个置换的循环分解”的求和。例证说明只需数各置换的循环数即可。

• ski rental 问题
• 随机化阈值 1+1/(e-1)=e/(e-1)
• 期望竞争比

Ski rental（滑雪租赁）：买滑雪板成本 B，租单次成本 1，未知要滑几次，需在“何时买”决策。确定性最优是“租 B 次后买”，竞争比 2（2-competitive）。随机化算法：随机选一个阈值 t（在 [1,B] 或指数分布），租到 t 次再买，期望竞争比 e/(e-1)≈1.58。工程价值：云 spot instance 购买 vs 按需、设备采购、软件订阅等“租 vs 买”决策，随机化阈值比确定性 2 更优，且实现简单（按随机阈值切换）。

随机化阈值把确定性的 2 降到 e/(e-1)≈1.58，且下界证明任何随机化算法 ≥ e/(e-1)。工程上以近似这个最优竞争比的随机化策略做租买决策。

• 两者都是在线决策
• 未知未来
• 最优决策时机

Ski rental 与 secretary problem 都是“先验未知、需在线决策时机”的问题：ski rental 未知要滑几次，决定何时买最划算；secretary 未知候选人分布，决定何时接受。共同点是“trade-off 探索与利用 / 现在 vs 未来”，都需在信息不足时选最优时机。ski rental 用阈值（确定性 2 或随机化 1.58），secretary 用 1/e 阈值。两者都是在线算法/最优停止的经典模型，刻画“何时行动”的决策结构。

两者都在“未知未来”下做“何时行动”决策，用阈值/停止规则平衡等待与行动。这是在线决策的一般范式，被广泛用于租买、招聘、择时。

• 云资源租 vs 买
• spot instance 的未知时长
• ski rental 决策

ski rental 模拟云资源决策：持续租用（按需付费）vs 买（预留/spot 实例）。若需求时长未知，持续租用可能在长任务下成本高，买在短任务下浪费。ski rental 的阈值策略：若预计持续超过阈值就买（预留），否则租。用随机化阈值（≈1.58 竞争比）或确定性 2 竞争比做决策，在未知任务时长下保证成本接近最优。工程上结合 spot 的时价波动做更复杂的扩展，但核心是“租 vs 买”的权衡。

云计费是 ski rental 的实例：按需=租，预留/spot=买，未知时长用阈值决策。竞争比保证成本逼近最优，工程上统筹 spot 价格与中断风险。

• 随机化竞争比下界
• 对抗性输入
• 1+1/e 证明

证明任何随机化 ski rental 算法竞争比 ≥ 1+1/e（即 e/(e-1)）：考虑对抗性输入分布，让“需求结束时间”服从随机分布（如几何分布），使算法无论何时买，期望成本都接近最优的 1+1/e 倍。用 Yao 的 minimax 或对随机化算法的“决策分布”分析：最优随机化策略的期望购买时间 t 满足期望成本 ≥ 最优的(1+1/e)。这证明随机化阈值 e/(e-1) 是最优，无法再改进。工程意义：确认用随机化阈值已达理论最优，无需追求更优。

下界用对抗分布 + 期望分析证明任何随机化算法 ≥ e/(e-1)。这保证随机化阈值策略是 tight 的，工程上可放心采用。

• 确定性 2-competitive
• 决策边界
• 租 B 次后买

Ski rental 确定性 2-competitive 算法：租 B 次（B 为购买成本）后，若仍需要则买。决策边界：累计租用成本达到 B（购买成本）时，从“继续租”切换到“购买”。若需求 ≤B 次，全程租，成本 = 需求 ≤ B = OPT；若需求 >B 次，租 B 次 + 买，成本 = B + B = 2B，而 OPT = B（直接买），故竞争比 ≤2。边界处“租成本 = 买成本”是等值切换点，保证最坏 2 倍。

2-competitive 的关键是“租到成本等于购买成本才买”，使最坏情况成本 ≤2×OPT。边界在租成本=B 时，决策从租切到买。

• 租天数与价格的比值
• 2-competitive 阈值
• 决策规则

若“租一天”成本为 1，“买”成本为 B，则确定性 2-competitive 算法是“租 B 天后再买”。把“买前租天数”写成“B/1 = B 天”，即“租天数 = 购买成本/单日租成本 = B/1”。若用“价格”表示购买成本，租 B 天（B=购买价格）后买，保证竞争比 2。边界：累计租成本达到购买成本时切换。这个“租天数=价格”的规则是 2-competitive 的决策边界。

“买前租天数 = 价格（B）”，即租成本累计到购买成本再买，保证最坏 2 倍。这是确定性 ski rental 的标准最优规则。

• 平滑复杂度的定义
• Simplex 的平滑复杂度
• k-means 的多项式平滑界

Spielman-Teng 平滑复杂度：对输入分布加高斯/自主扰动，定义问题在“扰动后”的期望最坏复杂度，通常为 max over 最坏解 + 高斯扰动的期望。Simplex 法在最坏输入下指数，但平滑分析显示其期望复杂度多项式（扰动后），解释 Simplex 实测高效。k-means 的局部搜索（Lloyd）在最坏下可能指数，平滑分析证明在高斯扰动下期望收敛多项式、质量接近最优。平滑复杂度把“最坏 vs 平均”统一，是分析数值算法（LP、k-means）的现代框架。

平滑复杂度 = 最坏解的扰动后期望代价，是“最坏”与“平均”的折中。Simplex 与 k-means 的平滑多项式界解释了它们在真实数据（带噪声）上高效的原因。

• TC0 加入阈值门
• MAJORITY 在 TC0
• PARITY 与 TC0

TC0 是常数深度、多项式规模、允许阈值门（如 MAJORITY）的电路类。MAJORITY 显然可用阈值门直接计算，故 MAJORITY∈TC0（而 MAJORITY∉AC0）。PARITY 也可用阈值门计算（比较 1 的个数奇偶），故 PARITY∈TC0；PARITY 不在 AC0，但 PARITY 在 TC0 中可算（用阈值门）。故边界：MAJORITY∈TC0\AC0，PARITY∈TC0\AC0，TC0 包含比 AC0 更多（能在阈值门/模门下计算）。

TC0 比 AC0 强：阈值门可算 MAJORITY、PARITY 等 AC0 不能算的函数。AC0⊂TC0，TC0 的阈值门扩展了常数深度电路的表达力。

• Treap 的随机优先级与树堆
• 期望 O(log n)
• split/merge 操作

Treap 是 BST + 堆（随机优先级是键，满足堆序），随机优先级使树高期望 O(log n)。split/merge 操作：split 按 pivot 把树分成两棵（≤ 和 >），merge 按优先级合并两棵树，均 O(log n) 期望。工程应用：支持区间操作（按序 split/merge 实现区间翻转、区间聚合）、灵活平衡树、可持久化（因无旋转）。Randomized BST 与之类似。Treap 的实现简单、无需旋转调整，适合动态集合与区间维护。

Treap 用随机优先级保证平衡，split/merge 是 O(log n) 的基本操作，把区间操作化为树的拼接。随机化使最坏（输入有序）不退化，工程上稳定。

• 侧信道攻击模型
• DPA 与 cache timing
• RSA 的密钥提取

grey-box 模型假设攻击者知道实现细节但无法直接读密钥。DPA 通过测量功耗差异关联密钥位（RSA 的模幂运算中依赖密钥位的分支/乘加），用统计相关分析提取密钥。cache timing 攻击利用 RSA 实现中查表（如预计算幂表）的 cache 命中/缺失时间差异，推断密钥位（如 Montgomery 乘法的访问模式）。工程路径：构造同一密钥的多次调用，测量功耗/时间，按密钥位分组做差分统计，相关峰指示密钥位。缓解：固定时间运算、常数时间查表、cache 隔离。

侧信道把“密钥位依赖的物理量”变成泄露。DPA 用差分统计，cache timing 用访问时间差异，两者都从多次观测聚合出密钥位。工程上需常数时间实现防御。

• 自动调参原理
• JIT 编译优化
• 实测加速

JIT 编译器需要为不同代码路径选择优化（内联、向量化、循环展开、分块等），选择不当会退化。autotuning 用“试探 + 实测反馈”自动选择最优参数：运行若干变体，测量性能，选最优。grey-box 利用已知的代码结构（如循环、访存模式）指导候选参数生成，减少探索。实测上，JIT/tuning 框架（如 PGO、ATLAS、OpenTuner）对数值/循环密集型代码可带来 1.5–5× 加速，因避免了固定参数在某些数据布局上的退化。

autotuning 用实测反馈替代固定启发式，grey-box 用结构信息缩小搜索空间。JIT 的优化空间大、参数敏感，自动调参显著提升性能。

• white-box 模型
• 密钥嵌入表
• key extraction 理论

white-box 加密把密钥嵌入实现（用查表取代轮运算），攻击者能看到全部代码与表。理论上，若攻击者能完全观察并执行实现，密钥可被提取（因为表结构含密钥信息，可用代数/统计分析还原）。已知 white-box AES 方案（如 Chow 等）都被攻破（key extraction），因为表的多层编码可被逆向或差分分析。没有 white-box 方案能对“全知”攻击者保证密钥安全，因为攻击者可模拟并比较输入输出。理论抵抗需依赖“可观察性受限”或同态加密等，但纯 white-box 不可。

white-box 秘密全暴露，攻击者可任意分析表与执行，故 key extraction 在理论上不可防。它是“混淆（obfuscation）不可达”的具体体现，工程上只能提高提取成本。

• 平滑复杂度与最坏复杂度
• 为什么不能推出 P=NP
• 作为分析工具

平滑复杂度分析的是“扰动后输入”的期望复杂度，不是最坏情况。P=NP 需要“所有实例多项式可解”，而平滑复杂度只证明“绝大多数/扰动后实例快”，不能覆盖最坏实例（如 SAT 的构造反例）。因此平滑复杂度不能推出 P=NP。它作为分析工具的价值：解释为什么 Simplex、k-means 等在最坏指数但在真实（带噪声）数据上高效，量化“平均 vs 最坏”的差距，为算法设计提供“扰动后高效”的保证。

平滑复杂度是“平均”与“最坏”的折中，只保证扰动后高效，不覆盖最坏，故不蕴含 P=NP，但为解释实测性能、指导算法设计提供工具。

• OGF/EGF 定义
• Catalan 的组合分解
• 生成函数方程

OGF（普通生成函数）：A(z)=Σ a_n z^n；EGF（指数生成函数）：A(z)=Σ a_n z^n/n!。Catalan 数 C_n 计数 n 个节点的二叉括号/括号序列，其组合分解：空树（n=0）或“根 + 左子树 + 右子树”，即 C_{n+1} = Σ_{i+j=n} C_i C_j。用 OGF C(z)=Σ C_n z^n，分解得 C(z) = 1 + z·C(z)²（1 表示空树，zC² 表示根+左右子树）。故 C = 1 + z C²，解得 C(z) = (1−√(1−4z))/(2z)。

生成函数把“递归分解”翻译成方程。Catalan 的“根+左右子树”分解直接给出 C=1+zC²，解出封闭式并用拉格朗日反演得 C_n=(1/(n+1))C(2n,n)。

• 生日悖论与碰撞期望
• 生成函数/泊松化
• 渐近分析

把 n 个键放入 m 个桶的碰撞期望用泊松化/生成函数分析。碰撞数期望 ≈ 桶数 × 期望每桶内额外键数 = m × E[对 (k,2) 计数]。用 EGF 或泊松近似，碰撞期望 = m·(n/m)²/2·(1+O(1/n)) ≈ n²/(2m)。在 m ~ n² 时碰撞 O(1) 量级；若考虑“期望碰撞数”以 n 尺度，则碰撞概率 ~ n²/(2m)，当 m 与 n 相比，碰撞概率 O(1/√n) 时对应 m ~ n^{3/2} 或类似尺度。analytic combinatorics 用奇异分析（singularity analysis）或泊松生成函数给出碰撞分布的渐近，如碰撞概率 ~ 1−e^{−n²/2m}，在 m 与 n 的关系下得 O(1/√n) 类渐近。

碰撞用泊松化/生成函数把“桶内键数”转成泊松近似，奇异分析给出渐近。碰撞概率 ~ n²/(2m)，据此选 m 控制碰撞量级。

• 三种复杂度类型
• branch-and-bound 求解器
• 实测差异

branch-and-bound（B&B）求解整数规划/SAT：worst-case 是指数（构造病态实例），average-case 是对随机实例的平均（可能多项式但依赖分布），smoothed complexity 是对“最坏实例 + 扰动”的期望（介于两者）。实测：B&B 求解器在标准 benchmark 上通常 O(小型/多项式) 时间，远好于 worst-case 指数；对随机实例平均快，但对 adversarial 构造可指数；加扰动后（smoothed）表现稳定，接近平均。差异反映：最坏被构造实例放大，平均随机友好，平滑把最坏“扰动”回平均。

三种复杂度衡量不同输入模型：最坏（病态）、平均（随机分布）、平滑（最坏+扰动）。B&B 在真实数据（平滑）上远好于最坏，实测差异源于此。

• black-box 假设
• 3-SAT 复杂度下界
• 指数下界构造

在 black-box（或随机预言）假设下，3-SAT 的底层的复杂结构与 SAT 的困难性意味着不存在 sub-exponential 算法（2^o(n)），除非某些强假设（如 ETH）被推翻。black-box 下界构造：构造一个“oracle”化的 3-SAT 变体，其中求值需要查询 oracle 揭示的变量，证明任何算法需 2^Ω(n) 次查询。这类下界依赖“算法只看输入、不能访问结构”的 black-box 假设，证明 sub-exponential 不可能（在 oracle 模型下）。它支持 ETH（3SAT 无 2^o(n) 算法）。

black-box 下界构造 oracle 化实例，证明查询下界 2^Ω(n)，从而排除 sub-exponential（在 oracle 模型）。这为 ETH 提供条件性支持。

• 内存分配器
• 平摊分析
• 工程意义

内存分配器（jemalloc、dlmalloc）用平摊分析保证分配/释放的平摊 O(1)。分配器维护空闲块（free list）、大小类（size class）、合并（coalescing）。单次分配可能触发合并/拆分（O(n) 的块整理），但用平摊分析（势能=空闲块数/碎片）证明多次操作平均 O(1)。jemalloc 用 arena 分片、size class 缓存降低锁竞争；dlmalloc 用边界标记合并。平摊意义：保证分配器在高频分配下总时间近线性，避免单次昂贵操作被放大。

分配器的合并/缓存是“个别昂贵、整体平摊”的典型。平摊分析为分配器 O(1) 平均分配提供理论保证，工程上配合 arena 分片降低竞争。

• 指令调度问题
• 平滑分析
• 编译器应用

instruction scheduling（指令调度）在编译器中安排指令顺序以最大化流水线/寄存器利用，是 NP 难的（依赖图调度）。最坏实例可能指数，但真实程序（依赖图 + 延迟）来自编译器生成的代码、带噪声/结构，平滑分析显示在这种“扰动后”输入上调度算法接近最优且多项式。工业编译器（如 LLVM、GCC）用启发式调度（list scheduling），在真实程序上表现好，平滑分析为“启发式在真实代码上有效”提供理论依据。案例：依赖图加随机延迟扰动后，list scheduling 的退化被抑制。

指令调度最坏 NP 难，但真实代码依赖图带结构，平滑分析解释启发式（list scheduling）的实测有效，避免最坏退化。

• path-copy 持久化
• 版本控制
• 工程价值

持久化线段树用 path-copy：每次更新只复制从根到叶子的路径（O(log n) 新节点），其余节点共享，从而保留所有历史版本。查询任一版本 O(log n)，支持回退、区间历史查询。工程价值：如区间第 k 大（主席树）把每个位置建一个版本、用前缀版本的差分求第 k 大；支持可回退数据结构、版本化查询。空间 O(n log n)（每次更新 O(log n) 新节点），是持久化数据结构的经典实现。

path-copy 用“复制路径 + 共享其余”实现全持久化，O(log n) 更新、O(1) 版本切换。主席树是典型应用，把“历史前缀”变成版本差分。

• 卡型输入构造
• 1/n 扰动族
• 平滑复杂度降级

构造“卡型”输入（如 Simplex 的 Klee-Minty 立方体、k-means 的退化点），其在最坏下指数。对每个卡型输入施加 1/n 尺度的高斯扰动，定义扰动族（每个输入扰动 σ=1/n 的分布）。证明：扰动后，卡型输入被“破坏”（如 Klee-Minty 的路径被随机化预测），使算法（Simplex 的 pivot、k-means 的 Lloyd）期望的迭代次数/操作变为多项式。通过分析扰动后输入落入“坏区域”的概率小、或优化路径的期望长度，得到多项式平滑复杂度。这是 Spielman-Teng 对 Simplex 的核心论证。

1/n 扰动把“最坏实例”的退化结构破坏，使算法期望多项式。证明需分析扰动后最优路径/迭代的期望，把指数级最坏转成多项式平滑。

• Lagrange 反演
• 树的生成函数
• 度为 i 的节点计数

有标号树用 EGF C(z)=z e^{C(z)}（Cayley 树）。用 Lagrange 反演：若 C = z φ(C)，φ(u)=e^u，则 [z^n] C(z) = (1/n)[u^{n-1}] φ(u)^n。度为 i 的节点数：标记一个“特殊节点”并计数其度为 i。用 EGF 的“marking”技巧，度 i 的节点数 = [z^n] C(z) 中对该节点的度用变量标记。由 Lagrange 反演，带参数的计数可得 [z^n] = (n-1)!/(n!)·[u^{n-1}] e^{u n}·(u^i/i!) 等，求和得度 i 的节点总数 = n·C(n-2, i-1)·(n-1)^{n-i-1}（Cayley 公式的推广）。这是 Lagrange 反演在树计数中的标准应用。

Lagrange 反演解 C=zφ(C)，marking 技巧把“度 i 节点数”作为系数提取，得到闭式。工程上用于计数组合对象的参数分布。

• 势能函数选择
• splay 的 zig/zig-zig/zig-zag
• 平摊分析

splay 树用势能法证明每个操作平摊 O(log n)。势能函数 Φ = Σ log(size(x))（size(x) 为 x 子树大小，即秩的和）。分析三种旋转：zig 平摊 O(1+ΔΦ)，zig-zig 与 zig-zag 平摊 O(3(r'(x)−r(x))) 或 O(1+ΔΦ)，其中 ΔΦ 是秩变化。对 splay 的多次旋转求和，总势能变化 O(log n)（因为总秩和 ≤ n log n），故每次 splay 平摊 O(log n)。关键：zig-zig 的秩变化被势能函数“吸收”，使三次旋转的总平摊代价为 O(log n) 而非每次旋转 O(1)。

势能 = 秩和（log size），splay 旋转的秩变化恰好被势能函数控制，使平摊代价 O(log n)。这是势能法在动态树上的经典证明。

• 物理法（势能法）
• 计数器 increment
• 平摊分析

物理法（potential/physicist method）用势能函数 Φ。二进制计数器 increment 的势能 Φ = 当前 1 的个数。每次 increment：设从最低位起连续 t 个 1 变成 0（翻转 t 位），然后第 t+1 位变 1（若存在）。实际代价 = t+1（翻转的位数）。1 的个数变化 = 1 − t（因 t 个 1 变 0，1 个 0 变 1）。平摊代价 = 实际代价 + ΔΦ = (t+1) + (1−t) = 2 = O(1)。故每次 increment 平摊 O(1)，总 n 次 O(n)。

势能（1 的个数）使“连续翻转 t 位”的昂贵操作被 t 个 1 的消失抵消，平摊成本恒定 O(1)。这是物理法/势能法的标准例证。

• Fibonacci 生成函数
• 部分分式分解
• Binet 公式

Fibonacci 数 f_0=0, f_1=1, f_n=f_{n-1}+f_{n-2}。OGF F(z)=Σ f_n z^n。由递推：F(z) = z + z F(z) + z² F(z)，得 F(z) = z/(1−z−z²)。因式分解 1−z−z² = (1−φz)(1+ψz)（φ=(1+√5)/2, ψ=(1−√5)/2），部分分式 F(z) = (1/√5)(1/(1−φz) − 1/(1−ψz))。展开级数得 f_n = (φ^n − ψ^n)/√5 = (1/√5)((1+√5)/2)^n − ((1−√5)/2)^n，即 Binet 公式。

生成函数把递推转成有理函数，部分分式分解后逐项展开得闭式。Binet 公式是生成函数法的经典结果。

• NL 与 coNL
• 非确定空间的可互补性
• Immerman-Szelepcsényi 定理

Immerman-Szelepcsényi 证明 NL = coNL：对 STCON（s-t 连通性，NL 完全）的补问题（s 不连通 t）给出非确定性对数空间算法。思路：用非确定性算法“计数”从 s 可达的节点数（迭代 c_i = 从 s 出发 ≤i 步可达节点数），猜测 c_{i+1} 并验证；最后判定 t 是否在可达集合中（若 t 不可达则接受）。因为非确定性可“猜测并验证”计数，且空间对数，故补问题在 NL，即 coNL ⊆ NL，对称得 NL = coNL。这是非确定性空间类对补封闭的经典定理。

关键是用非确定性“计数可达集合并验证”，把 STCON 的补放入 NL。于是 NL 对补封闭，NL=coNL，是空间复杂度类的重要对称性。

• 平滑复杂度测试
• Gauss 扰动
• adversary 扰动

平滑复杂度单元测试应覆盖两类扰动：1) Gauss 扰动——对随机输入添加高斯噪声（σ=1/n 等），验证算法（如 Simplex、k-means）在扰动后的运行时间/迭代次数为多项式且结果正确；2) adversary 扰动——构造最坏/卡型输入（如 Klee-Minty、退化点集），加扰动后验证算法不退化（时间多项式、质量接近最优）。测试断言：扰动后时间随规模多项式增长、不出现指数退化、结果与无扰动近似一致。用多组随机种子与 σ 值覆盖分布。

测试覆盖“随机扰动”与“对抗扰动”两类，验证平滑复杂度（扰动后多项式）的实际表现。用规模缩放与 σ 扫描检测指数退化。

• succinct 数据结构
• bit RAM vs word RAM
• cache miss 与指令数

设计对比实验：用同一 succinct 结构（如 rank/select、LD 位向量）在 bit RAM（按位访问、需要位级操作）与 word RAM（按字访问、预计算表）下实现，测量：1) cache miss——用性能计数器（perf）或模拟器统计访问的缓存未命中次数；2) 指令数——统计执行指令数；3) 运行时间。预期：word RAM 用查表/字操作减少指令数与 cache miss（按字加载），bit RAM 位操作多、指令多、cache miss 高。用不同规模（n 从 2^10 到 2^30）与随机/重复访问模式对比，量化差异。

对比实验控制“算法同一、模型不同”，测量 cache miss 与指令数。word RAM 的查表/字对齐减少访存与指令，bit RAM 位操作开销大，定量对比揭示模型差异。

• L ⊆ NL ⊆ P
• Reingold 结果
• 无向 STCON 的对数空间

L ⊆ NL ⊆ P：L（对数空间可判）⊆ NL（对数空间非确定可判），因为非确定包含确定；NL ⊆ P 因为非确定对数空间可被多项式时间（模拟 2^O(log n) 状态）枚举，且 STCON 多项式可解。Reingold 证明无向 STCON 在对数空间（L）内：用“图的幂（squaring）+ 膨胀 + 降维”构造正则展开图，反复对图取平方（使连通性保持且度数/大小可控）再降回常数度，用对数空间迭代，最后在常数度图上判连通。这证明无向连通性在对数空间可解，是 L 与 NL 分离的重要一步（有向 STCON 是 NL 完全）。

L⊆NL⊆P 是基本包含。Reingold 用“图幂 + 膨胀 + 降维”把无向连通性压缩到对数空间，证明 USTCON∈L，是空间复杂度的重要突破。

• STCON 在 NL
• NL 完全性
• 归约与验证者

STCON（有向图 s-t 连通性）是 NL 完全：1) STCON ∈ NL：非确定性算法从 s 出发，每次非确定地猜一条出边，猜到 t 则接受（路径长度 ≤n，用计数器保证 ≤n 步），空间 O(log n)。2) NL 完全：任意 NL 语言 L 的多项式对数空间归约到 STCON——(决定性) 对 NL 机器 M 和输入 x，构造图 G(M,x)，节点为 M 的配置（机器状态+带头位置，O(log n) 个配置），边为配置转移，则 M 接受 x ⇔ 存在从起始配置到接受配置的路径。因配置数多项式、每条边可由 M 的转移在 log 空间判定，故归约成立。验证者交互：NL 的验证者可提供“路径”作为证书，机器在 log 空间验证。

关键是把“NL 机器计算”编码为“配置图上的 s-t 路径”，用配置图归约。配置数 = 2^O(log n) 多项式，转移可在 log 空间列枚，故 STCON 是 NL 完全。

• 竞争比定义
• 在线缓存竞争比
• 在线调度竞争比

竞争比 = 在线算法代价 / 最优离线代价（最坏情形）。在线缓存：LRU 与 FIFO 是 k-competitive（k 为缓存大小），OPT（Belady）是最优离线，下界 k。在线调度（如单机在线作业、在线列表调度）：list scheduling 是 2-competitive（负载均衡），在线装箱是 1.7-competitive 等。不同问题竞争比不同：缓存 k-competitive，调度 2-competitive，反映问题结构与未知信息的代价。竞争比刻画在线算法相对离线最优的差距。

竞争比统一量化在线算法在未知输入下的性能损失。缓存与调度分别用 k 与 2 等竞争比，体现各问题的“信息代价”与最优下界。