C#实现欧氏距离计算代码功能测试通过但性能不达标原因咨询

你的实现功能逻辑正确，但性能问题来自算法选型和细节实现两个层面，具体如下：

• 核心问题：算法时间复杂度过高
  你当前采用的双重循环暴力枚举所有点对的方案，时间复杂度为O(n²)。当性能测试用例中点的规模达到10^{4及以上时，总计算量会达到10}8级别，远超常规时间限制要求。平面最近点对问题的标准最优解法是分治算法，时间复杂度仅为O(n log n)，在大规模数据下性能比暴力法高几个数量级。

• 实现细节存在大量冗余高开销运算

  1. 不必要的开平方操作：比较两点距离大小和比较两点距离的平方大小是完全等价的，Math.Sqrt属于高开销浮点运算，你在每一次点对计算时都执行开平方，做了大量无用功。优化方案是全程存储当前最小距离的平方做比较，仅在最终返回结果时执行一次开平方即可。
  2. 低效的平方计算：Math.Pow是为任意指数幂运算设计的通用方法，调用开销远大于直接乘法。计算差值的平方完全可以直接写(x - a) * (x - a)，不需要调用Math.Pow，单步运算速度能提升3~5倍。

• 缺少基础剪枝逻辑
  哪怕不替换分治算法，仅在暴力法基础上增加剪枝也能获得数倍性能提升：先将所有点按x坐标排序，内层循环遍历j时，如果当前j点和i点的x轴差值已经大于当前记录的最小距离，那么后续j点和i点的x差只会更大，不可能得到更小的距离，直接终止内层循环即可，能砍掉大量无效计算。

附：优化了运算细节的暴力版本参考（仍为O(n²)复杂度，仅做细节优化，大规模数据仍需替换分治算法）

public static double solution(int[][] p)
{
    long bestDistSq = long.MaxValue;
    int plength = p.Length;
    // 先按x坐标排序，为剪枝做准备
    Array.Sort(p, (a,b) => a[0].CompareTo(b[0]));
    for (int i = 0; i < plength - 1; i++)
    {
        int x = p[i][0];
        int y = p[i][1];
        for (int j = i + 1; j < plength; j++)
        {
            int dx = x - p[j][0];
            // x差已经大于当前最优距离，直接剪枝跳出
            if ((long)dx * dx >= bestDistSq) break;
            int dy = y - p[j][1];
            long distSq = (long)dx * dx + (long)dy * dy;
            if (distSq < bestDistSq)
                bestDistSq = distSq;
        }
    }
    return Math.Sqrt(bestDistSq);
}

内容的提问来源于stack exchange，提问作者Leandro De Mello Fagundes