F. BO Algorithm: Analysis
数学大学
F. BO Algorithm: Analysi
计算几何 · 02. Geometric Intersection
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
F. BO Algorithm: Analysi
计算几何 · 02. Geometric Intersection
Correctness
桶算法的正确性论证：最大间隔必然跨桶，桶间候选因此穷尽一切可能。
不变量
候选间隔只在相邻非空桶的边界间产生
完备性
鸽巢论证排除「真最大间隔在桶内」的可能
Example
算例走查：一组具体数据经分桶、清点边界、求最大差值的全程演示。
走查
手工模拟分桶与相邻非空桶配对
验证
与排序解法对照结果一致
Retesting
复测机制：算法输出后用随机小样本或排序法抽查，防实现缺陷。
抽查
随机小输入用排序法对拍
回归
极端数据（重合、聚簇）纳入回归测试
Complexity of Event Queu
事件队列的复杂度：预排序为 O(n log n)，数组实现则 O(1) 取事件。
预排序版
一次排序，之后取事件 O(1)
动态版
优先队列每次操作 O(log n)
Complexity of Status Str
扫描状态的复杂度：平衡树支持 O(log n) 的前驱后继查询与插入。
操作
插入、删除、查前驱后继均 O(log n)
总量
n 个事件共 O(n log n)
本节要点
- ✓正确性根基：最大间隔必跨桶
- ✓算例与回归测试防实现缺陷
- ✓队列与状态结构各 O(n log n)
延伸主题：写一份完整对拍脚本分析状态结构的常数因子
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1为什么随机对拍能高效发现实现缺陷？
参考答案几何实现的缺陷集中在退化与边界情形，而随机数据会以高概率覆盖大部分分支组合；用简单但慢的排序解法做参照，一旦不一致立即暴露实现漏洞。小而随机的测试往往比精心设计的大用例更有效。
2正确性论证中「不变量」是什么？
参考答案不变量是算法每步都保持的真命题，例如「真最大间隔一定属于当前候选集合」。每步操作不破坏不变量，算法结束时不变量直接给出正确答案——这就是正确性证明的骨架。
3散度（散度比）事件队列与状态结构的成本哪个占主导？
参考答案通常事件队列的排序与取事件为主导（O(n log n)），状态结构操作同为对数级但常数不同。优化时先排序与队列，再动状态结构——按成本大头排序投入。