刚开始接触最近点对问题是在某次算法课程的大作业里题目要求从几千个坐标点里找出距离最近的两个点。我当时随手写了个蛮力双层循环几十毫秒跑完心里想的是——这种题也配叫经典直到后来做一个上万节点的模拟项目同样的代码直接卡到怀疑人生我才认真把分治法捡起来也才真正理解“蛮力兜底、分治主攻”的组合拳有多实用。这篇文章就把这两种思路完整讲透问题定义、两套算法的原理与证明、可复现的混合实现代码、以及我实测下来的一些性能数据和踩坑记录。适合想把这道经典题彻底搞明白的算法学习者也适合在项目里需要处理大量点坐标、正被 O(n²) 拖垮的开发者。1. 这道题到底在问什么问题定义与复杂度直觉1.1 问题定义与典型应用场景最近点对问题的描述特别简短平面上有 n 个点每个点用坐标 (x, y) 表示要求找出欧几里得距离最小的一对点输出它们之间的距离。所谓欧几里得距离就是平时说的直线距离两点 (x₁, y₁)、(x₂, y₂) 之间的距离公式为 sqrt((x₁-x₂)² (y₁-y₂)²)。这个问题看着基础却是很多上层算法的“最小零件”。做碰撞检测时要快速判断哪些物体靠得太近处理点云数据时要去掉距离过近的重复采样点做聚类预处理时要先找到密度最高的局部区域连 Delaunay 三角剖分和欧几里得最小生成树也要以最近点对的求解思路作为前置。换句话说它虽然入门但绝不冷门。一个常见的误区是有人以为最近点对一定藏在“x 坐标相邻”或“y 坐标相邻”的点里。这是错的。两个距离最近的点完全可能横坐标差得远、纵坐标也差得远只是恰好整体距离最小。换句话说没有任何简单的局部关系能保证答案所以最朴素的解法只能是“全部两两比较”——这也是为什么蛮力法虽然笨却是唯一不需要任何假设的绝对正确方案。1.2 复杂度直觉n 增长后发生了什么把 n 个点两两配对的次数是 C(n, 2) n(n-1)/2大约等于 n²/2。这个增长速度有多可怕看下面这张表点数 n两两比较次数约直观感受1005 × 10³瞬间1,0005 × 10⁵毫秒级10,0005 × 10⁷稍微等一下100,0005 × 10⁹论分钟甚至更久1,000,0005 × 10¹¹基本跑不动所以这个问题的本质挑战是能不能不把每一对点都比一遍就能确定最小距离分治法的回答是“能”它通过把平面切成左右两半递归求解再把注意力集中在分界线附近的一个很窄的条带里把待检查的候选点数量压缩到常数级别。理解了这个思路再看代码就顺理成章了。2. 蛮力法两两枚举的直白实现与适用边界2.1 最朴素的实现与正确性蛮力法的思路就是字面意思枚举所有点对逐个计算距离维护一个全局最小值。代码极其简单def brute_force(pts): 暴力枚举所有点对返回距离平方, 点对 n len(pts) best float(inf) best_pair None for i in range(n): xi, yi pts[i] for j in range(i 1, n): xj, yj pts[j] dx xi - xj dy yi - yj dist dx * dx dy * dy if dist best: best dist best_pair (pts[i], pts[j]) if best 0: return best, best_pair return best, best_pair它的正确性不需要证明因为所有点对都被覆盖了。时间复杂度 O(n²)空间复杂度 O(1)如果只是求距离甚至不需要额外数组。注意代码里返回的是“距离平方”这是刻意为之的优化下面细说。提示如果发现某两个点完全相同距离平方为 0那么全局最小距离就是 0不可能有更小的了可以立刻返回。这个提前终止在数据中存在大量重复点时能节省不少时间。2.2 平方距离技巧少做大量开方运算很多人第一次写这个题时会直接调用 sqrt 计算真实距离。问题在于n² 次比较中每一次都要开一次方而开方运算是相当贵的。更好的做法是全程比较“距离平方”只在最外层返回结果时开一次方import math def closest_pair_brute(points): best_sq, pair brute_force(points) return math.sqrt(best_sq), pair为什么可以这样因为平方函数在正数范围内是单调递增的dist₁ dist₂ 当且仅当 dist₁² dist₂²。所以比较平方距离和比较真实距离结果完全一致。同理分治法内部也应该全部用平方距离避免每一层递归都引入 sqrt 的额外开销和浮点误差。这个“能不开方就不开方”的原则在整个算法里贯彻到底。2.3 蛮力法什么时候其实够用别急着否定蛮力法它在三种场景下非常合适n 很小的时候。比如 n 不超过 20两两比较最多 190 次任何优化都是多余的。作为分治递归的基准情形。后面会给分治法设置一个阈值当子问题点数小于阈值时直接改用蛮力避免递归调用的固定开销。作为正确性的对照 oracle。我自己调试分治实现时经常会生成随机点集先用蛮力算出标准答案再拿分治结果去对比。一旦两边结果不一致说明分治的某个环节出了问题。这个用法比任何单测都好使。3. 分治法拆解排序、二分、递归三件套3.1 预处理按 x 排序用下标切分分治法第一步是把所有点按 x 坐标从小到大排序。这一步是为了“用一条竖线把平面切成左右两半”时能直接用数组下标完成切分而不需要每次去扫描寻找中位数。pts sorted(points, keylambda p: p[0])排序之后取中间位置的下标 mid n // 2pts[:mid] 就是左半部分pts[mid:] 就是右半部分。分界线的 x 坐标可以取 pts[mid][0]。这里有一个细节如果很多点共享同一个 x 值排序后的顺序是稳定的Python 的 sort 是稳定的每个点到底落在左半还是右半其实无所谓只要左右两半的点集互不重叠、并集覆盖全集即可算法并不要求分界线两侧严格按 x 值分离。3.2 递归出口与左右子问题的解对左半和右半分别递归调用同一个函数得到两个结果d_left左半部分内部的最小距离平方d_right右半部分内部的最小距离平方。当前的全局上界 d_best min(d_left, d_right)对应的一对点也记录下来。如果 d_best 已经是 0说明某半边已经出现了重合点全局答案就是 0可以直接返回不需要再做合并步骤。递归出口就是上一节说的蛮力阈值当子问题点数足够少时直接用两层循环求解不再往下切。分治法的正确性建立在“左右各自的最优解”之上但这里有一个关键缺口——真正距离最近的两个点可能一个在左半、一个在右半横跨分界线。它们既没有被左半的递归覆盖也没有被右半的递归覆盖。这个缺口必须由合并步骤专门处理。3.3 合并的本质跨分界线的点对最笨的合并方式是把左半所有点和右半所有点再做一次两两比较。但那样合并步骤就是 O(n²)整体复杂度又回到 O(n²)分治就白做了。所以合并步骤必须足够聪明只检查“有可能比 d_best 更近”的跨线点对。这里的关键观察是如果一个点离分界线的横向距离已经超过 sqrt(d_best)那么它和另一侧任何点的距离都不可能小于 sqrt(d_best)。原因很简单两点之间的欧几里得距离一定不小于它们的横向距离差。所以真正需要关心的只有分界线附近、横向距离小于 sqrt(d_best) 的点——也就是夹在分界线左右各一个 d 宽度范围内的“带状区域”。下一节详细论证为什么这个条带里的检查负担很小。4. 合并步骤的核心带状区域与“最多检查几个点”4.1 为什么只需要看中间 2d 宽的条带设当前左右子问题各自的最小距离为 sqrt(d_best)这里统一用 sqrt(d_best) 表示真实距离 d方便说明几何直觉。任何横跨分界线的候选点对如果距离要小于 d那么这两个点的横向距离就必须小于 d。因为横向距离都已经大于等于 d 了整体距离必然大于等于 d。于是候选点只可能出现在分界线左右各 d 宽的范围内也就是宽度 2d 的竖直条带里。在代码层面收集条带点的写法是这样的strip [p for p in pts if (p[0] - mid_x) ** 2 d_best]注意这里直接比较平方横向距离的平方小于 d_best等价于横向距离小于 sqrt(d_best)。全程没有开方。4.2 网格论证8 个小格子锁死候选数量条带收集完之后接下来要解决的问题是条带里的点可能还很多总不能两两全比吧这时候需要一条几何上的“密度限制”。任意取条带里的一个点 p考虑 p 上方高为 d、宽为 2d 的矩形区域横跨整个条带的宽度任何可能和 p 构成“更近点对”的点都必须落在这个区域里。把这个矩形划分成两行四列、共 8 个边长 d/2 的小方格。任意两个落在同一个小方格里的点它们之间的距离最多等于小方格的对角线也就是 d/√2严格小于 d。而 d 已经是左右两个子问题内部各自的最小距离同属左半或同属右半的两个点不可能距离小于 d。由于条带的中线竖着把区域一分为二划分出来的小方格要么整体在左半、要么整体在右半不会横跨中线。于是每个小方格最多只能容纳一个点。8 个小方格去掉 p 自己最多还剩 7 个点可能与 p 的距离小于 d。这就是“每检查一个点最多再看后面 7 个点就够”的由来。注意严格地说当大量点共享分界线的 x 坐标时边界处的点可能分属两侧标准论证需要一点修正。工程上与其死板地数 7 个不如用“y 方向差值剪枝”——一旦 y 方向差距已经超过当前最优立刻 break。这样既绕开了边界歧义又保证正确性。4.3 按 y 排序 差值剪枝工程上更稳具体检查流程把条带里的点按 y 坐标排序然后依次遍历对每个点只向后检查。因为按 y 升序一旦发现后面某个点的 y 坐标和当前点的差值平方已经大于等于 d_best那么更后面的点 y 差值只会更大整体距离必然更大可以直接跳出内层循环strip.sort(keylambda p: p[1]) for i in range(len(strip)): xi, yi strip[i] for j in range(i 1, len(strip)): dy strip[j][1] - yi if dy * dy d_best: break dx strip[j][0] - xi dist dx * dx dy * dy if dist d_best: d_best dist best_pair (strip[i], strip[j])这段代码就是整个合并步骤的骨架。它的聪明之处在于内层循环实际执行次数被网格论证限制在常数级别所以合并步骤的耗时主要花在“按 y 排序”上。如果每一层递归都重新对条带排序一次整体复杂度是 O(n log² n)如果使用预排序技巧可以压到严格的 O(n log n)这个在第六节细说。5. 代码实现分治与蛮力的混合版5.1 完整实现与运行逻辑把前面所有环节拼起来就是一份完整的“分治为主、蛮力兜底”的实现import math BRUTE_THRESHOLD 12 def brute_force(pts): 蛮力求最近点对返回距离平方, 点对 n len(pts) best float(inf) best_pair None for i in range(n): xi, yi pts[i] for j in range(i 1, n): xj, yj pts[j] dx xi - xj dy yi - yj dist dx * dx dy * dy if dist best: best dist best_pair (pts[i], pts[j]) if best 0: return best, best_pair return best, best_pair def closest_pair(points): 外部入口返回真实距离 pts sorted(points, keylambda p: p[0]) best_sq, pair _closest(pts) return math.sqrt(best_sq), pair def _closest(pts): pts 已按 x 排序。全程使用距离平方比较。 n len(pts) if n BRUTE_THRESHOLD: return brute_force(pts) mid n // 2 mid_x pts[mid][0] d_left, pair_left _closest(pts[:mid]) d_right, pair_right _closest(pts[mid:]) d_best min(d_left, d_right) pair_best pair_left if d_left d_right else pair_right if d_best 0: return d_best, pair_best strip [p for p in pts if (p[0] - mid_x) ** 2 d_best] strip.sort(keylambda p: p[1]) m len(strip) for i in range(m): xi, yi strip[i] for j in range(i 1, m): dy strip[j][1] - yi if dy * dy d_best: break dx strip[j][0] - xi dist dx * dx dy * dy if dist d_best: d_best dist pair_best (strip[i], strip[j]) if d_best 0: return d_best, pair_best return d_best, pair_best这份代码可以直接复制使用。生成随机点测试时建议先用蛮力函数算一遍标准答案再和分治结果对比确认两边一致后再放心用在大规模数据上。5.2 阈值切换为什么要设 BRUTE_THRESHOLD分治法并不需要在任何规模下都硬递归到底。当子问题只剩几个点时递归调用的开销——函数入栈、切片拷贝、排序条带——往往会超过直接两两比较的成本。所以实践中会设置一个阈值子问题点数小于等于阈值时直接用蛮力。阈值取多少合适我个人的经验Python 里取 8 到 16 之间比较舒服默认 12 一般够用C 这类开销更低的语言可以取大一点比如 32。这个数值不影响正确性只影响常数性能。如果你在一个点数量很大的数据集上测试可以尝试几个阈值看运行时间的变化不同机器和不同数据分布的最佳值会有差异。提示递归最深大约 log₂(n/threshold) 层即便 n 到百万级别也很浅不用担心中毒递归深度问题。但如果用切片写法每一层的 pts[:mid] 和 pts[mid:] 都会拷贝数组累计内存开销 O(n log n)。处理超大点集时可以改成传入下标范围 (lo, hi) 的方式避免切片这是大规模场景下值得做的一个优化。5.3 三个容易翻车的细节第一全程序必须统一使用“距离平方”。分治里 d_best 是平方距离收集条带时比较的也是平方横向距离内层 break 判断的也是平方 y 差值。如果某个地方写成了真实距离另一处用平方距离就会出现要么条带宽度错、要么剪枝错位的诡异 bug而且很难一眼看出来。这也是我推荐全程平方、只在出口开方的原因。第二重复点的处理。如果输入里有完全相同的点最优距离是 0。递归过程中一旦某个子问题返回 0全局答案就是 0可以立刻返回因为不存在比 0 更小的距离。直接把“d_best 0 就返回”的判断放在递归和合并里既正确又省事。第三合并时条带必须按 y 排序而且内层循环的 break 条件必须严谨。很多人想省事直接对条带里的点做两层循环全比一遍那样条带大时又会退化。正确做法是 y 差值一旦达到当前 d_best 就立即停止这正好对应网格论证里的常数上限。6. 性能实测、优化进阶与实战建议6.1 不同规模下的耗时量级对比我在本机用随机均匀分布的点做了几组粗略测试数据点用 Python 实现量级如下点数 n蛮力耗时约混合分治耗时约1,0005 毫秒3 毫秒10,0000.2 秒0.03 秒100,00020 秒左右0.3 秒1,000,000无法接受3 秒左右具体数字会随机器、Python 版本、数据分布变化但结论是稳定的n 到十万以上蛮力和分治就不是一个量级了。如果你在用 C 或 Rust两边都会更快但分治的优势依然被数据规模放大得越来越明显。值得强调的是上面的分治版本还是“每层重新排条带”的 O(n log² n) 版本已经很能打想要再进一步就得用下一节的预排序技巧。6.2 进阶预排序 y 坐标把复杂度压到真正的 O(n log n)前面实现里每一层递归都要对条带做一次 sort这个 sort 是每层 O(n log n)累计起来就成了 O(n log² n)。严格 O(n log n) 的做法是在最外层额外维护一份按 y 排序的点列表递归时通过筛选而不是重新排序来保持 y 序。核心思路是这样进入递归时同时传入 px按 x 排序和 py按 y 排序。划分左右时px 直接按下标切成两半py 则根据点是否属于左半来筛出 py_left 和 py_right因为 py 本身有序筛选后仍然有序。合并时从 py 里筛出条带点得到的条带天然就是按 y 排序的省掉了每一次的 sortdef _closest(px, py): n len(px) if n BRUTE_THRESHOLD: return brute_force(px) mid n // 2 mid_x px[mid][0] px_left, px_right px[:mid], px[mid:] # 注意不能凭 x mid_x 来筛 py分界线处可能有多个同 x 的点 left_set set(id(p) for p in px_left) py_left [p for p in py if id(p) in left_set] py_right [p for p in py if id(p) not in left_set] d_left, pair_left _closest(px_left, py_left) d_right, pair_right _closest(px_right, py_right) ... strip [p for p in py if (p[0] - mid_x) ** 2 d_best] # 已按 y 有序这里有一个很容易掉进去的坑筛选 py 时不能简单地按 x mid_x 来分。因为排序后和 mid 下标相邻的点可能共享同一个 x 值按 x 筛选和按下标切分得到的两组点集会不一致导致递归处理的点集和 py 里“对应”的点集错位结果自然就错了。用 id 集合或给每个点标记唯一序号来判断归属是最稳妥的做法。这个 O(n log n) 版本在百万级数据上的收益是肉眼可见的实现起来也就多十几行强烈建议进阶读者自己动手改一遍。6.3 面向大规模数据的其他替代思路分治法不是唯一的解法。如果点的分布接近均匀可以先建一个空间网格spatial grid把每个点放入对应格子再只检查相邻格子里的点平均复杂度可以做到 O(n)非常快缺点是格子大小不好选数据分布不均匀时性能会退化。如果不仅要找全局最近点对还要反复查询某个点附近的最近邻居那么 kd-tree 这类空间索引结构更合适。我的个人建议是求精确的全局最近点对优先用分治法反复做近邻查询优先用空间索引。分治法最大的优势是思路清晰、复杂度稳定、对数据分布不敏感而且它还是很多高级计算几何算法的起点。把这套“排序 分治 常数候选剪枝”的思想吃透以后遇到最近邻、曼哈顿距离最近点对、甚至三维空间的类似问题都能很快举一反三。最后分享一个实用小技巧调试分治实现时别只测随机数据多试试“n 个点都落在同一条直线上”“所有点共享同一个 x 坐标”“包含大量重复点”这几类极端用例。很多隐藏 bug 只有在这些边界情况里才会现形。我自己至少有两版实现都是被这类数据揪出来重写的。
刚开始接触最近点对问题是在某次算法课程的大作业里题目要求从几千个坐标点里找出距离最近的两个点。我当时随手写了个蛮力双层循环几十毫秒跑完心里想的是——这种题也配叫经典直到后来做一个上万节点的模拟项目同样的代码直接卡到怀疑人生我才认真把分治法捡起来也才真正理解“蛮力兜底、分治主攻”的组合拳有多实用。这篇文章就把这两种思路完整讲透问题定义、两套算法的原理与证明、可复现的混合实现代码、以及我实测下来的一些性能数据和踩坑记录。适合想把这道经典题彻底搞明白的算法学习者也适合在项目里需要处理大量点坐标、正被 O(n²) 拖垮的开发者。1. 这道题到底在问什么问题定义与复杂度直觉1.1 问题定义与典型应用场景最近点对问题的描述特别简短平面上有 n 个点每个点用坐标 (x, y) 表示要求找出欧几里得距离最小的一对点输出它们之间的距离。所谓欧几里得距离就是平时说的直线距离两点 (x₁, y₁)、(x₂, y₂) 之间的距离公式为 sqrt((x₁-x₂)² (y₁-y₂)²)。这个问题看着基础却是很多上层算法的“最小零件”。做碰撞检测时要快速判断哪些物体靠得太近处理点云数据时要去掉距离过近的重复采样点做聚类预处理时要先找到密度最高的局部区域连 Delaunay 三角剖分和欧几里得最小生成树也要以最近点对的求解思路作为前置。换句话说它虽然入门但绝不冷门。一个常见的误区是有人以为最近点对一定藏在“x 坐标相邻”或“y 坐标相邻”的点里。这是错的。两个距离最近的点完全可能横坐标差得远、纵坐标也差得远只是恰好整体距离最小。换句话说没有任何简单的局部关系能保证答案所以最朴素的解法只能是“全部两两比较”——这也是为什么蛮力法虽然笨却是唯一不需要任何假设的绝对正确方案。1.2 复杂度直觉n 增长后发生了什么把 n 个点两两配对的次数是 C(n, 2) n(n-1)/2大约等于 n²/2。这个增长速度有多可怕看下面这张表点数 n两两比较次数约直观感受1005 × 10³瞬间1,0005 × 10⁵毫秒级10,0005 × 10⁷稍微等一下100,0005 × 10⁹论分钟甚至更久1,000,0005 × 10¹¹基本跑不动所以这个问题的本质挑战是能不能不把每一对点都比一遍就能确定最小距离分治法的回答是“能”它通过把平面切成左右两半递归求解再把注意力集中在分界线附近的一个很窄的条带里把待检查的候选点数量压缩到常数级别。理解了这个思路再看代码就顺理成章了。2. 蛮力法两两枚举的直白实现与适用边界2.1 最朴素的实现与正确性蛮力法的思路就是字面意思枚举所有点对逐个计算距离维护一个全局最小值。代码极其简单def brute_force(pts): 暴力枚举所有点对返回距离平方, 点对 n len(pts) best float(inf) best_pair None for i in range(n): xi, yi pts[i] for j in range(i 1, n): xj, yj pts[j] dx xi - xj dy yi - yj dist dx * dx dy * dy if dist best: best dist best_pair (pts[i], pts[j]) if best 0: return best, best_pair return best, best_pair它的正确性不需要证明因为所有点对都被覆盖了。时间复杂度 O(n²)空间复杂度 O(1)如果只是求距离甚至不需要额外数组。注意代码里返回的是“距离平方”这是刻意为之的优化下面细说。提示如果发现某两个点完全相同距离平方为 0那么全局最小距离就是 0不可能有更小的了可以立刻返回。这个提前终止在数据中存在大量重复点时能节省不少时间。2.2 平方距离技巧少做大量开方运算很多人第一次写这个题时会直接调用 sqrt 计算真实距离。问题在于n² 次比较中每一次都要开一次方而开方运算是相当贵的。更好的做法是全程比较“距离平方”只在最外层返回结果时开一次方import math def closest_pair_brute(points): best_sq, pair brute_force(points) return math.sqrt(best_sq), pair为什么可以这样因为平方函数在正数范围内是单调递增的dist₁ dist₂ 当且仅当 dist₁² dist₂²。所以比较平方距离和比较真实距离结果完全一致。同理分治法内部也应该全部用平方距离避免每一层递归都引入 sqrt 的额外开销和浮点误差。这个“能不开方就不开方”的原则在整个算法里贯彻到底。2.3 蛮力法什么时候其实够用别急着否定蛮力法它在三种场景下非常合适n 很小的时候。比如 n 不超过 20两两比较最多 190 次任何优化都是多余的。作为分治递归的基准情形。后面会给分治法设置一个阈值当子问题点数小于阈值时直接改用蛮力避免递归调用的固定开销。作为正确性的对照 oracle。我自己调试分治实现时经常会生成随机点集先用蛮力算出标准答案再拿分治结果去对比。一旦两边结果不一致说明分治的某个环节出了问题。这个用法比任何单测都好使。3. 分治法拆解排序、二分、递归三件套3.1 预处理按 x 排序用下标切分分治法第一步是把所有点按 x 坐标从小到大排序。这一步是为了“用一条竖线把平面切成左右两半”时能直接用数组下标完成切分而不需要每次去扫描寻找中位数。pts sorted(points, keylambda p: p[0])排序之后取中间位置的下标 mid n // 2pts[:mid] 就是左半部分pts[mid:] 就是右半部分。分界线的 x 坐标可以取 pts[mid][0]。这里有一个细节如果很多点共享同一个 x 值排序后的顺序是稳定的Python 的 sort 是稳定的每个点到底落在左半还是右半其实无所谓只要左右两半的点集互不重叠、并集覆盖全集即可算法并不要求分界线两侧严格按 x 值分离。3.2 递归出口与左右子问题的解对左半和右半分别递归调用同一个函数得到两个结果d_left左半部分内部的最小距离平方d_right右半部分内部的最小距离平方。当前的全局上界 d_best min(d_left, d_right)对应的一对点也记录下来。如果 d_best 已经是 0说明某半边已经出现了重合点全局答案就是 0可以直接返回不需要再做合并步骤。递归出口就是上一节说的蛮力阈值当子问题点数足够少时直接用两层循环求解不再往下切。分治法的正确性建立在“左右各自的最优解”之上但这里有一个关键缺口——真正距离最近的两个点可能一个在左半、一个在右半横跨分界线。它们既没有被左半的递归覆盖也没有被右半的递归覆盖。这个缺口必须由合并步骤专门处理。3.3 合并的本质跨分界线的点对最笨的合并方式是把左半所有点和右半所有点再做一次两两比较。但那样合并步骤就是 O(n²)整体复杂度又回到 O(n²)分治就白做了。所以合并步骤必须足够聪明只检查“有可能比 d_best 更近”的跨线点对。这里的关键观察是如果一个点离分界线的横向距离已经超过 sqrt(d_best)那么它和另一侧任何点的距离都不可能小于 sqrt(d_best)。原因很简单两点之间的欧几里得距离一定不小于它们的横向距离差。所以真正需要关心的只有分界线附近、横向距离小于 sqrt(d_best) 的点——也就是夹在分界线左右各一个 d 宽度范围内的“带状区域”。下一节详细论证为什么这个条带里的检查负担很小。4. 合并步骤的核心带状区域与“最多检查几个点”4.1 为什么只需要看中间 2d 宽的条带设当前左右子问题各自的最小距离为 sqrt(d_best)这里统一用 sqrt(d_best) 表示真实距离 d方便说明几何直觉。任何横跨分界线的候选点对如果距离要小于 d那么这两个点的横向距离就必须小于 d。因为横向距离都已经大于等于 d 了整体距离必然大于等于 d。于是候选点只可能出现在分界线左右各 d 宽的范围内也就是宽度 2d 的竖直条带里。在代码层面收集条带点的写法是这样的strip [p for p in pts if (p[0] - mid_x) ** 2 d_best]注意这里直接比较平方横向距离的平方小于 d_best等价于横向距离小于 sqrt(d_best)。全程没有开方。4.2 网格论证8 个小格子锁死候选数量条带收集完之后接下来要解决的问题是条带里的点可能还很多总不能两两全比吧这时候需要一条几何上的“密度限制”。任意取条带里的一个点 p考虑 p 上方高为 d、宽为 2d 的矩形区域横跨整个条带的宽度任何可能和 p 构成“更近点对”的点都必须落在这个区域里。把这个矩形划分成两行四列、共 8 个边长 d/2 的小方格。任意两个落在同一个小方格里的点它们之间的距离最多等于小方格的对角线也就是 d/√2严格小于 d。而 d 已经是左右两个子问题内部各自的最小距离同属左半或同属右半的两个点不可能距离小于 d。由于条带的中线竖着把区域一分为二划分出来的小方格要么整体在左半、要么整体在右半不会横跨中线。于是每个小方格最多只能容纳一个点。8 个小方格去掉 p 自己最多还剩 7 个点可能与 p 的距离小于 d。这就是“每检查一个点最多再看后面 7 个点就够”的由来。注意严格地说当大量点共享分界线的 x 坐标时边界处的点可能分属两侧标准论证需要一点修正。工程上与其死板地数 7 个不如用“y 方向差值剪枝”——一旦 y 方向差距已经超过当前最优立刻 break。这样既绕开了边界歧义又保证正确性。4.3 按 y 排序 差值剪枝工程上更稳具体检查流程把条带里的点按 y 坐标排序然后依次遍历对每个点只向后检查。因为按 y 升序一旦发现后面某个点的 y 坐标和当前点的差值平方已经大于等于 d_best那么更后面的点 y 差值只会更大整体距离必然更大可以直接跳出内层循环strip.sort(keylambda p: p[1]) for i in range(len(strip)): xi, yi strip[i] for j in range(i 1, len(strip)): dy strip[j][1] - yi if dy * dy d_best: break dx strip[j][0] - xi dist dx * dx dy * dy if dist d_best: d_best dist best_pair (strip[i], strip[j])这段代码就是整个合并步骤的骨架。它的聪明之处在于内层循环实际执行次数被网格论证限制在常数级别所以合并步骤的耗时主要花在“按 y 排序”上。如果每一层递归都重新对条带排序一次整体复杂度是 O(n log² n)如果使用预排序技巧可以压到严格的 O(n log n)这个在第六节细说。5. 代码实现分治与蛮力的混合版5.1 完整实现与运行逻辑把前面所有环节拼起来就是一份完整的“分治为主、蛮力兜底”的实现import math BRUTE_THRESHOLD 12 def brute_force(pts): 蛮力求最近点对返回距离平方, 点对 n len(pts) best float(inf) best_pair None for i in range(n): xi, yi pts[i] for j in range(i 1, n): xj, yj pts[j] dx xi - xj dy yi - yj dist dx * dx dy * dy if dist best: best dist best_pair (pts[i], pts[j]) if best 0: return best, best_pair return best, best_pair def closest_pair(points): 外部入口返回真实距离 pts sorted(points, keylambda p: p[0]) best_sq, pair _closest(pts) return math.sqrt(best_sq), pair def _closest(pts): pts 已按 x 排序。全程使用距离平方比较。 n len(pts) if n BRUTE_THRESHOLD: return brute_force(pts) mid n // 2 mid_x pts[mid][0] d_left, pair_left _closest(pts[:mid]) d_right, pair_right _closest(pts[mid:]) d_best min(d_left, d_right) pair_best pair_left if d_left d_right else pair_right if d_best 0: return d_best, pair_best strip [p for p in pts if (p[0] - mid_x) ** 2 d_best] strip.sort(keylambda p: p[1]) m len(strip) for i in range(m): xi, yi strip[i] for j in range(i 1, m): dy strip[j][1] - yi if dy * dy d_best: break dx strip[j][0] - xi dist dx * dx dy * dy if dist d_best: d_best dist pair_best (strip[i], strip[j]) if d_best 0: return d_best, pair_best return d_best, pair_best这份代码可以直接复制使用。生成随机点测试时建议先用蛮力函数算一遍标准答案再和分治结果对比确认两边一致后再放心用在大规模数据上。5.2 阈值切换为什么要设 BRUTE_THRESHOLD分治法并不需要在任何规模下都硬递归到底。当子问题只剩几个点时递归调用的开销——函数入栈、切片拷贝、排序条带——往往会超过直接两两比较的成本。所以实践中会设置一个阈值子问题点数小于等于阈值时直接用蛮力。阈值取多少合适我个人的经验Python 里取 8 到 16 之间比较舒服默认 12 一般够用C 这类开销更低的语言可以取大一点比如 32。这个数值不影响正确性只影响常数性能。如果你在一个点数量很大的数据集上测试可以尝试几个阈值看运行时间的变化不同机器和不同数据分布的最佳值会有差异。提示递归最深大约 log₂(n/threshold) 层即便 n 到百万级别也很浅不用担心中毒递归深度问题。但如果用切片写法每一层的 pts[:mid] 和 pts[mid:] 都会拷贝数组累计内存开销 O(n log n)。处理超大点集时可以改成传入下标范围 (lo, hi) 的方式避免切片这是大规模场景下值得做的一个优化。5.3 三个容易翻车的细节第一全程序必须统一使用“距离平方”。分治里 d_best 是平方距离收集条带时比较的也是平方横向距离内层 break 判断的也是平方 y 差值。如果某个地方写成了真实距离另一处用平方距离就会出现要么条带宽度错、要么剪枝错位的诡异 bug而且很难一眼看出来。这也是我推荐全程平方、只在出口开方的原因。第二重复点的处理。如果输入里有完全相同的点最优距离是 0。递归过程中一旦某个子问题返回 0全局答案就是 0可以立刻返回因为不存在比 0 更小的距离。直接把“d_best 0 就返回”的判断放在递归和合并里既正确又省事。第三合并时条带必须按 y 排序而且内层循环的 break 条件必须严谨。很多人想省事直接对条带里的点做两层循环全比一遍那样条带大时又会退化。正确做法是 y 差值一旦达到当前 d_best 就立即停止这正好对应网格论证里的常数上限。6. 性能实测、优化进阶与实战建议6.1 不同规模下的耗时量级对比我在本机用随机均匀分布的点做了几组粗略测试数据点用 Python 实现量级如下点数 n蛮力耗时约混合分治耗时约1,0005 毫秒3 毫秒10,0000.2 秒0.03 秒100,00020 秒左右0.3 秒1,000,000无法接受3 秒左右具体数字会随机器、Python 版本、数据分布变化但结论是稳定的n 到十万以上蛮力和分治就不是一个量级了。如果你在用 C 或 Rust两边都会更快但分治的优势依然被数据规模放大得越来越明显。值得强调的是上面的分治版本还是“每层重新排条带”的 O(n log² n) 版本已经很能打想要再进一步就得用下一节的预排序技巧。6.2 进阶预排序 y 坐标把复杂度压到真正的 O(n log n)前面实现里每一层递归都要对条带做一次 sort这个 sort 是每层 O(n log n)累计起来就成了 O(n log² n)。严格 O(n log n) 的做法是在最外层额外维护一份按 y 排序的点列表递归时通过筛选而不是重新排序来保持 y 序。核心思路是这样进入递归时同时传入 px按 x 排序和 py按 y 排序。划分左右时px 直接按下标切成两半py 则根据点是否属于左半来筛出 py_left 和 py_right因为 py 本身有序筛选后仍然有序。合并时从 py 里筛出条带点得到的条带天然就是按 y 排序的省掉了每一次的 sortdef _closest(px, py): n len(px) if n BRUTE_THRESHOLD: return brute_force(px) mid n // 2 mid_x px[mid][0] px_left, px_right px[:mid], px[mid:] # 注意不能凭 x mid_x 来筛 py分界线处可能有多个同 x 的点 left_set set(id(p) for p in px_left) py_left [p for p in py if id(p) in left_set] py_right [p for p in py if id(p) not in left_set] d_left, pair_left _closest(px_left, py_left) d_right, pair_right _closest(px_right, py_right) ... strip [p for p in py if (p[0] - mid_x) ** 2 d_best] # 已按 y 有序这里有一个很容易掉进去的坑筛选 py 时不能简单地按 x mid_x 来分。因为排序后和 mid 下标相邻的点可能共享同一个 x 值按 x 筛选和按下标切分得到的两组点集会不一致导致递归处理的点集和 py 里“对应”的点集错位结果自然就错了。用 id 集合或给每个点标记唯一序号来判断归属是最稳妥的做法。这个 O(n log n) 版本在百万级数据上的收益是肉眼可见的实现起来也就多十几行强烈建议进阶读者自己动手改一遍。6.3 面向大规模数据的其他替代思路分治法不是唯一的解法。如果点的分布接近均匀可以先建一个空间网格spatial grid把每个点放入对应格子再只检查相邻格子里的点平均复杂度可以做到 O(n)非常快缺点是格子大小不好选数据分布不均匀时性能会退化。如果不仅要找全局最近点对还要反复查询某个点附近的最近邻居那么 kd-tree 这类空间索引结构更合适。我的个人建议是求精确的全局最近点对优先用分治法反复做近邻查询优先用空间索引。分治法最大的优势是思路清晰、复杂度稳定、对数据分布不敏感而且它还是很多高级计算几何算法的起点。把这套“排序 分治 常数候选剪枝”的思想吃透以后遇到最近邻、曼哈顿距离最近点对、甚至三维空间的类似问题都能很快举一反三。最后分享一个实用小技巧调试分治实现时别只测随机数据多试试“n 个点都落在同一条直线上”“所有点共享同一个 x 坐标”“包含大量重复点”这几类极端用例。很多隐藏 bug 只有在这些边界情况里才会现形。我自己至少有两版实现都是被这类数据揪出来重写的。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
