守株阁

第10篇并查集只保存连通分量划分。加入边可以合并集合，删除边却不能直接拆开集合：被删边可能是唯一通路，也可能还有其他路径。若全部操作预先已知，可以改变处理顺序，让每段递归只做合并，在离开时撤销这些合并。 本篇实现回滚并查集与时间线段树，回答一般无向图的离线加边、删边与连通查询。它不依赖第13篇运行程序，也不提供在线到达即回答的接口。 图边与代表元指针不是同一回事 输入有n个固定顶点，编号0到n−1，以及q个操作。每个操作为add(u,v)、remove(u,v)或query(u,v)，结果按query出现顺序返回布尔列表。所有端点先检查，越界抛IndexError；n为负、未知操作、重复添加已存在的边或删除不存在的边抛ValueError。 无向边统一为(min(u,v),max(u,v))，同一对端点同时最多存在一条边。允许自环，但自环不会改变连通性；删除后可以重新添加，形成新的生命区间。这里没有平行边引用计数，不能把重复add当作第二条独立边。 并查集的parent指针是分区表示，不要求它对应输入图中的某条边。删除图边(u,v)不能解释成“把parent[v]设回v”。例如三...

“每个位为1的概率算对了，把它乘k次就得到精确误报率”是一个可以检验的判断。第33篇已经给出小反例，本篇把它整理成一个完整复现项目：明确概率空间，用两个独立方法计算有限实例，保存原始结果，再说明哪个判断被否定、哪个一般结论需要证明。 研究对象是理想Bloom模型的公式，不是本系列仿射散列教学实现的实际误报率。38篇区分精确结果与测量精度，这里更进一步：全程使用有理数，不让浮点舍入成为公式差异的解释。 先写出概率空间 位数组有m个位置，m≥1，初始全为0。插入n个不同键，n≥0，每个键使用k个哈希位置，k≥1。所有kn个位置独立、均匀地取自0到m−1，允许一个键的多个位置相同。 随后查询一个固定的未插入键，它的k个位置也独立均匀，并独立于插入阶段。若查询的所有位置都已置1，就发生误报。n计不同键；重复插入同一个键会重用哈希值，不能按新的一组独立投球计算。 这个模型不自动覆盖双重散列、同一键无放回选择k个位置，或看过位数组再挑查询的对手。代码不会调用33篇的仿射Bloom来伪装这个完全独立模型；二者的随机假设不同。 精确式在条件概率之后取平均 令X为插入结束后的置位数。给定完整位数组...

第36篇的两个榜单实现回答相同查询，却把成本放在不同位置。VersionedBoard维护AVL和路径复制树，SnapshotBoard复制完整字典并扫描或排序。对数复杂度并不能直接回答“小数据上哪个Python实现更快”，一次本机测量也不能回答“所有负载都该选哪个”。 实验先固定语义，再改变输入规模、分数分布、更新比例与整数位长。近似算法允许不同输出质量，应另外报告质量，不能让它与精确实现只比一个耗时数字。 同一语义的比较需要固定什么 榜单实验沿用36篇契约：ID稳定、排名按(-score,id)、范围按ID半开区间、历史查询指向明确版本。两种实现从相同初始分数开始，执行完全相同的更新与查询，保留全部历史版本。 输入规模n取16、64、256；分布包含重复分数多的tied与较分散的uniform；更新比例取0.1、0.8。每条操作流长度256，查询按rank、select、当前随机范围和、历史全域和轮换。历史全域查询在持久化树上可直接读取根摘要，不代表任意历史子区间都只访问根。更新率是生成概率，实际更新数另记。输入在计时外生成并保存散列，结果校验和相等是进入比较的条件，不是“答...

“安排合适的人完成任务”和“用最低成本覆盖全部目标”都包含选择，但它们选择的对象、限制和目标不同。二分图匹配的最优证书，不能替一个集合覆盖方案证明成本最优；覆盖了所有目标，也不代表有足够人员执行选中的方案。 本篇复用27篇的二分图匹配和30篇的加权集合覆盖贪心。两种输出分别验收，只有明确增加联合模型后，才能讨论联合方案的可行性与最优性。 资格分配：每个人和任务最多出现一次 输入是a名人员、b个任务，以及m条资格边。边(u,v)表示人员u可以执行任务v，左右编号属于两个独立集合。每个人至多承担一个任务，每个任务至多由一人承担；所有任务价值相同，目标是最大化被分配任务数。 输出包括匹配边的原始编号，以及由左侧人员和右侧任务组成的点覆盖。点覆盖必须接触每条资格边，不能把集合覆盖中的“覆盖所有目标”直接套到这里：这里覆盖的是图的边。 验证先检查匹配边都在输入中，左右端点没有重复，再检查点覆盖接触所有资格边。如果匹配大小等于点覆盖大小，就得到最优证书。理由是任何匹配的边两两不共享端点，而点覆盖必须为每条匹配边提供至少一个端点，所以任意匹配大小都不超过任意点覆盖大小。 当两者相等时，下界与上...

同一份记录可以按分数排名，也可以按记录编号查询区间总分。这是两种顺序：排名位置会随分数改变，记录编号却不能跟着移动。再加入历史查询，就必须说明每个结果属于哪个版本。 本篇组合06篇的AVL顺序统计树与14篇的持久化区间和，沿用00篇的记录接口。当前排名可以更新，历史只查询按编号划分的范围总分，不承诺历史排名，也不把本地单线程程序称为完整多索引MVCC系统。 身份、排序与范围各用什么键 构造时指定非负容量C，表示整个运行最多创建C条记录。记录ID从0开始单调增加，删除后不复用；达到C次插入后，即使当前记录很少，也拒绝继续插入。这个固定上限来自所复用的持久化树定义域，不代表动态榜单必须天然拥有固定容量。 当前记录由字典保存id到score的映射，score为整数，允许负分和重复分数。AVL中的键为(-score,id)，所以高分靠前，同分时较小ID靠前；唯一ID让不同记录不会因分数相同被合并。 区间聚合使用记录ID，不使用排名。sum(l,r)表示所有仍存在且满足l≤id<r的记录分数之和，合法边界为0≤l≤r≤C。尚未分配或已经删除的位置贡献0，空区间返回0。 例如ID0分数...

一个算法已经做到O(n log n)，不代表所有模型都不可能更快。下界必须说明算法能观察什么、存储多少信息、允许哪些操作，以及成本怎样计量。删掉这些条件，下界很容易变成错误的性能承诺。 本篇完整推导比较排序的基础下界，再把整数前驱与单遍流放回各自模型中。29篇的NP困难性依赖归约与尚未解决的类别关系；下面的比较决策树下界则可以直接从信息量证明。两种论证不能混为一谈。 比较排序必须分辨n!种次序 输入为n个互异键，算法需要输出它们的升序排列。模型只允许通过两键比较获取次序信息，不能把键当数组下标、拆出整数位，或通过键的数值计算直接推断位置。其他搬移操作不计入下面的比较次数下界。 固定一个确定性算法，把每次比较视作一个内部节点。因为键互异，比较结果只有“小于”和“大于”两个分支。一次完整执行对应根到某个叶子的路径，路径长度就是该输入所做的比较次数。 n个带身份的输入位置共有n!种可能的严格大小次序。一个叶子固定了算法最后输出的位置排列；同一个输出排列不能同时正确处理两种不同的严格次序。因此正确算法的决策树至少需要n!个叶子。 深度至多h的二叉树最多有2^h个叶子，所以最坏输入的比较数...

03篇把一次操作的昂贵成本放进整个序列分析，16篇比较了缓存替换策略。在线分析再加一个信息限制：处理当前请求时，算法看不到未来请求，却要与知道完整序列的离线最优作比较。 比较必须固定同一个输入序列、同样的资源和成本口径。若在线算法只有两个缓存页，参照却有无限容量，所得差距不能直接叫作同容量竞争比；若只报告某条轨迹的平均命中率，也没有得到对所有序列成立的保证。 租到哪天才买 每天租用成本为1，一次购买成本为整数B≥1，买后无需再付租金。总使用天数T是非负整数，每天开始时知道当天要使用，但不知道以后还要用多少天。当天选择购买就不再同时付租金。 离线算法知道T，最优成本为OPT(T)=min(T,B)。在线策略先租B−1天；若第B天仍需使用，就当天购买。T=0时不做任何操作，成本0。 若T<B，在线成本也是T，与离线相同。若T≥B，在线总成本是B−1+B=2B−1，而离线成本是B。因此对每个T都满足ALG(T)≤(2−1/B)OPT(T)。B=1时第一天直接购买，因子恰为1；T=0不需要计算0/0。 这里给的是纯乘法保证，没有加法常数。固定B后，若允许任意依赖B的加法常数，就能把...

精确集合保留每个键，精确计数器保留每个键的频率。只能单遍处理输入、又不愿为所有键保存完整记录时，可以接受受条件约束的误差，但必须先说明查询什么，以及哪一种错误不会发生。 Bloom Filter回答某个键是否可能出现过；Count-Min Sketch估计某个键累计出现的次数。前者不是精确集合，后者不是直接列举高频键的完整方案。本篇沿04篇的哈希碰撞模型与32篇的失败概率分析，分别核对它们的保证。 Bloom的确定性保证从哪里来 维护m个位和k个固定哈希函数。插入键x时，把h_1(x)到h_k(x)对应的位全部置1；查询时若有任一位为0，就回答不存在，否则回答可能存在。 只要插入与查询使用同一组哈希函数、位数组没有丢失或被清零，每个已插入键查询到的位置就都为1。因此无假阴性是操作不变量，不依赖哈希分布足够随机。对一个未插入键，这些位置可能已经被其他键置1，产生假阳性。 普通精确哈希表并不因为哈希冲突就返回假阳性：它还会比较完整键，冲突影响查找成本。Bloom没有保存足够的完整键来消除这种歧义，不能把两种数据结构的结果保证混用。 标准Bloom不能通过清除某个键对应的位来删除它，因...

04篇把随机性放在算法内部，要求固定输入后再谈期望。现在比较两种不同承诺：随机选择无论抽到什么主元都会返回正确答案，但耗时变化；随机收缩总会返回一个合法割，却可能错过最小割。 这两种随机性不能用一句“期望表现不错”概括。需要分别回答输出是否一定正确、成本对谁取期望，以及重复执行改善的是哪一项。 随机选择的答案始终正确 输入是长度n的整数数组和从0开始的秩k，要求0≤k<n；输出排序后第k个值，允许重复元素。每轮均匀选取当前数组的一个位置，把元素分为小于、等于、大于主元三组。 若k小于左组长度，继续在左组找同一秩；若k落在等值组，直接返回主元；否则在右组寻找k减去左组与等值组长度后的秩。三路划分把重复元素一次处理完，避免所有元素相等时仍每轮只移走一个。 正确性只依赖三组的大小和顺序关系，与主元是否幸运无关。每轮保留的子问题严格缩小，空输入或越界秩应在入口拒绝。这是Las Vegas型保证：结果一定正确，运行成本是随机变量。 对任意固定输入，至少一半的位置落在按秩划分的中间一半。选到这样的主元，下一轮待查部分至多约3n/4；重复值只会扩大可直接结束的等值组。每轮遇到这种缩小的概...

30篇的无权点覆盖算法把一条未覆盖边的两个端点都选入答案，依靠不相交边数提供下界。加上权重后，这个规则会失效：单条边两端成本1和K，直接全选会付出K+1，最优却只需1。 加权问题仍能得到2近似，但下界必须反映权重。28篇的线性规划对偶为此提供一组可核对的不等式；先从整数约束放宽到分数解，再说明怎样产生整数覆盖。 松弛保留什么约束 输入是无向无自环图G=(V,E)，每个顶点有非负权重w_v。输出点覆盖C，使每条边至少有一个端点被选中，目标最小化Σ_{v∈C}w_v。教学实现用整数权重；下面的证明同样适用于精确的非负有理数。 整数规划为每个顶点设置变量x_v∈{0,1}，每条边uv要求x_u+x_v≥1。把整数限制放宽成x_v≥0，得到 min⁡∑vwvxv,xu+xv≥1 (uv∈E),xv≥0.\min\sum_v w_vx_v,\qquad x_u+x_v\ge1\ (uv\in E),\quad x_v\ge0. minv∑​wv​xv​,xu​+xv​≥1 (uv∈E),xv​≥0. 不必额外写x_v≤1：非负权下把大于1的坐标截成1，仍然可行，且不会增加目标值。记该松弛最...