土法炼钢兴趣小组的算法知识备份

最近点对与随机化几何算法

2025-07-15 | algorithms | #geometry #closest-pair #randomized #divide-and-conquer

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