仅存在距离度量时如何找两个最远点？是否有优于O(n²)的算法

在仅已知距离度量满足三大公理（恒等性、对称性、三角不等式）、无任何额外结构信息的通用场景下，不存在确定性算法能做到严格优于O(n²)的时间复杂度。

核心原因 #

你没有办法通过部分点对的距离计算，100%确定未计算的点对中不会存在全局距离最大的点对。我们可以构造很简单的反例：假设共有n个点，任意点对的距离均为1，唯独某一对隐藏的点对距离为2，只要你没有遍历计算所有点对，就有概率漏掉这一对全局最远点。

现有优于O(n²)的最远点对算法，全部依赖于空间的额外结构：比如欧氏平面上的旋转卡壳算法，本质利用了凸包的几何性质，最远点对一定在凸包顶点上，才能把复杂度降下来，而这些性质在通用度量空间里并不存在。

可尝试的替代方案 #

如果不需要100%精确的结果，或者你的距离度量存在额外隐含结构，可以尝试以下方案：

• 近似求解：经典的2倍近似算法仅需要O(n)时间：随机选取一个起始点，找到距离它最远的点A，再找到距离A最远的点B，(A,B)这对点的距离一定不小于全局最远点对距离的1/2。如果需要更高精度的1+ε近似，也可以通过少量迭代或采样把时间复杂度控制在O(n/ε)级别，远低于O(n²)。
• 低维嵌入：如果你的距离度量实际对应d维欧氏空间的距离（只是你没有点的坐标），可以先通过多维缩放（MDS）算法把所有点嵌入到d维欧氏空间拿到坐标，再用对应维度的最远点对快速算法求解，总复杂度由嵌入复杂度和低维算法复杂度共同决定，在d远小于n的场景下远优于O(n²)。
• 特定距离优化：如果你的距离度量有特殊性质（比如树距离、字符串编辑距离、曼哈顿距离等），可以针对该度量的特性设计专门的快速算法，很多特殊度量下都存在优于O(n²)的精确解算法。

内容的提问来源于stack exchange，提问作者cbyh