最近对蛮力算法 - 基本操作

Question

给出以下伪代码，用于通过蛮力计算该地点两个最近点之间的距离：

for (i <-- 1 to n-1) do
    for (j <-- i+1 to n) do
        d <-- min(d, sqrt(xi-xj)^2 + (yi-yj)^2)
return d

基本操作是计算平方根。但是显然可以通过忽略平方根函数并比较值 (xi-xj)^2 + (yi-yj)^2) 来避免在循环中计算平方根。我查了一下，得到了这个 "the smaller a number of which we take the root, the smaller its square root, meaning the square root function is strictly increasing"。因此，基本操作变成了数字的平方。谁能解释这个定义？

Answer 1

回答问题的最简单方法是了解为什么可以避免求平方根。考虑以下一组点之间的距离，按升序排列：

{2, 5, 10, 15, 30, ...} = {d_1,1, d_1,2, d_{1, 3}, d_2,1, d_2,2, ...}

这些距离中的每一个都被计算为 x 和 y 距离平方和的平方根。但是我们可以对这个集合中的每个项目进行平方并得出相同的顺序：

{4, 25, 100, 225, 900} = {d_1,1², d_1,2²,d_1,3²,d_2,1², d_2,2², ...}

注意距离的位置，包括最小距离（第一个条目），没有改变位置。

应该注意的是，您的伪代码实际上并没有计算最小距离，但可以很容易地修改它来计算它。

最近对蛮力算法 - 基本操作

Closest Pair Brute Force Algorithm - Basic Operation

algorithm

brute-force