守株阁

一个算法已经做到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，仍然可行，且不会增加目标值。记该松弛最...

29篇区分了求解、验证和困难性。遇到难以精确求解的优化问题，一种选择是保留可行性，允许目标值偏离最优，但为偏离程度给出对所有合法输入成立的保证。 对于目标非负的最小化问题，记算法返回值为ALG、最优值为OPT。ρ近似要求ALG≤ρOPT，同时算法在输入编码长度的多项式时间内结束。直接写不等式可以覆盖OPT=0；写ALG/OPT时还得处理分母为零。下面两个保证是确定性的最坏情况保证，不是随机输入上的平均表现，也不是运行时间的摊还界。 点覆盖中的一组不相交边 输入是n个顶点、m条边的无向简单图。点覆盖是一组顶点C，使每条边至少有一个端点属于C；无权版本要求最小化|C|。这与27篇的匹配不同：匹配选择边，要求边不共享端点；覆盖选择顶点，要求所有边得到覆盖。 顺序扫描边。如果当前边的两个端点都没有被选过，把这条边加入M，并把两个端点加入C。扫描结束，输出C。 M是一组匹配，因为加入新边时两端都未使用。它还是极大匹配：若有一条边与M完全不相交，这条边在被扫描时两端也必定未使用，就应该被加入，矛盾。极大只表示不能继续加边，不表示边数最大；不需要运行27篇的最大匹配算法，也不要求图是二分图。 ...

一段程序跑得慢，只能说明这段程序在当前输入上的表现，不能证明问题本身必须如此。计算复杂性需要先固定问题、编码与计算模型，再说明算法能做到什么，或者一个已知困难问题怎样转换成它。 本篇用3SAT到CLIQUE的具体转换说明归约方向和双向证明，再用0/1背包解释为什么O(nW)的动态规划不一定是关于输入长度的多项式算法。27篇的二分图匹配依然可以高效求解；不能因为另一个图问题困难，就把困难性迁移到所有图算法。 P与NP先讨论判定问题 判定问题对每个合法输入只回答是或否。例如，CLIQUE问“给定无向简单图G和整数k，是否存在至少k个两两相邻的顶点”；优化版本则要求找出最大团。这两个问题有关，但定义类别时不能省略判定门槛。 把完整输入编码成有限二进制串，长度记为L。P包含能由确定性算法在L的多项式时间内判定的问题。NP用证书刻画判定问题。是实例存在长度不超过某个多项式p(L)的证书，确定性验证器能在多项式时间内接受它；否实例不存在任何能被接受的合法证书。 对CLIQUE，证书是k个不同顶点的编号。检查编号范围、不同性以及每对之间有边，就能验证。使用邻接矩阵时需O(k²)次查边，建矩阵或...

26篇用流提供一个可行值，用割限制所有流的最大值；27篇用匹配和点覆盖形成同样大小的两份证书。线性规划把这种“可行方案与界相遇”的结构推广到线性不等式：原问题给出方案，对偶问题给出界，两边可行且目标相等，就足以证明最优。 本篇只核对小型问题的精确证书，不实现通用线性规划求解器。求出候选解与验证候选解是两个任务；有一个通过检查的证书，并不意味着已经实现了搜索它的算法。 从约束到原问题 考虑非负变量x、y，最大化3x+2y，约束为 x+y≤4,2x+y≤5,x,y≥0.x+y\le 4,\qquad 2x+y\le 5,\qquad x,y\ge 0. x+y≤4,2x+y≤5,x,y≥0. 输入包括约束系数、右端常数、目标系数，以及待核对的原始和对偶候选。输出是候选是否可行、各自目标值和二者差距。变量在本节允许取实数，没有整数要求。 一般形式写为最大化cᵀx，满足Ax≤b、x≥0。设A有m行n列，m是约束条数，n是变量数。向量不等式逐项成立，转置只是交换行列，使Aᵀu按变量汇总各条约束的系数。 选择点(x,y)=(1,3)，两条约束左侧分别为4和5，目标值为9。它证明最优值至少为9...

把候选安排逐个加入日程时，先选中的一对可能妨碍后续分配。若每位人员最多接受一项任务，每项任务也最多分配一人，这个问题可以表示成二分图匹配。提高匹配大小有时需要撤销一对已有安排，换成两对新安排；26篇残量网络中的撤销操作正好表达这种调整。 本篇先证明匹配与整数流的对应，再从终止时的残量可达集合构造最小点覆盖。匹配是可行安排，点覆盖则限制任何安排最多能有多少对，两者大小相等时形成可核对的最优性证书。 两侧顶点不能混成一个编号域 输入左侧a个顶点、右侧b个顶点，以及m条候选边(l,r)。左侧编号0到a−1，右侧编号0到b−1，即使数字相同也表示不同对象。边保留输入ID，允许重复候选，但匹配不能重复使用任一端点。 输出一组匹配边ID，以及分别位于左右两侧的点覆盖集合。点覆盖要求每条输入边至少一个端点被选中；匹配则要求所选边两两不共享端点。这两个“覆盖”和“配对”条件不同，不能只比较返回集合的大小。 允许一侧为空、没有边、存在孤立点。不要求把所有人员或任务配满；目标是最大化匹配条数。加入边权、人员容量或任务优先级以后，需要重新说明目标和归约，不能直接沿用本篇最大基数匹配的结论。 单位容量强...

沿一条通路增加流量，很容易得到比原来更好的方案。困难在于证明何时不能继续改善，以及早先选错的通路能否撤销。最大流的残量网络同时处理这两件事：正向残量表示还能增加多少，反向残量表示已有流量能撤回多少。 本篇固定使用Edmonds–Karp算法，每次用BFS找边数最少的增广路。它属于Ford-Fulkerson增广方法，但不能把任意选路规则的执行次数直接当作它的复杂度。最终输出除了流量，还包括一个容量相等的割，让最优性可以独立核对。 流的接口与可行性 输入n≥2个顶点、m条有向边、不同的源点s与汇点t。每条边有非负整数容量c，保留独立输入ID，允许平行边、相反方向的原始边和自环。输出每条原边的流f、总流值以及一个源侧顶点集合S。 可行流必须满足0≤f(e)≤c(e)。除s、t外，每个顶点的流入和流出相等。总流值取s的净流出，即流出减流入，而不是仅把源点所有出边相加；它同时等于t的净流入。 自环对净流量的贡献为零，教学实现不会利用它增广。零流总是可行，所以无需先解决一个寻找初始可行解的子问题。本篇没有下界流、多源供需或最小费用约束。 一条原边需要两个残量方向 原边u→v的当前流量为f时...