randomized 标签归档 | 土法炼钢兴趣小组的算法知识备份

随机化算法：当运气成为武器

随机化不是偷懒，而是一种强大的算法设计范式。从 Karger 最小割到 Schwartz-Zippel 引理，随机性让许多困难问题变得出人意料地简单。

面对一个不知道有多长的数据流，如何保证每个元素被等概率选中？水塘抽样用一个优雅的不变量解决了这个看似不可能的问题。

给定一个被线段划分的平面，如何快速确定一个查询点落在哪个区域？梯形分解用随机增量法构建 O(log n) 查询的优雅结构。

在 n 个点中找最近的一对，暴力需要 O(n^2)。分治法将其优化到 O(n log n)，而 Rabin 的随机化方法更进一步达到期望 O(n)。

当我们放弃对确定性平衡的执念，转而拥抱随机化，会发现一些最优雅的数据结构——Treap 用一个随机优先级就消除了旋转的痛苦，跳表用抛硬币就实现了对数级查找。这不是妥协，而是对概率论最精彩的工程应用。