c++ - 计算所有对之间的曼哈顿距离

Question

我有一个矩阵中某些顶点的 (x,y) 坐标的列表(c++ 中的 vector )，例如 [ (0,2) , (0,3) , (1,2) , (2 ,2) ] 。我想计算列表中每对顶点之间的曼哈顿距离。目前我正在使用两个循环:

for(int i=0;i<size-1;i++)
        {
            for(int j=i+1;j<size;j++)
            {
                dist=abs(v[i][0]-v[j][0])+abs(v[i][1]-v[j][1]);
                //Process dist
            }
        } 

这种方法的时间复杂度为 O(n^2)。有没有时间复杂度更小的更好方法来做到这一点？

Answer 1

由于输出的大小是 \Theta(n^2) 并且每对的每个曼哈顿距离的复杂度在 O(1) 中，您可以不再提高复杂性。