我有一个矩阵中某些顶点的 (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)。有没有时间复杂度更小的更好方法来做到这一点?
最佳答案
由于输出的大小是 \Theta(n^2)
并且每对的每个曼哈顿距离的复杂度在 O(1)
中,您可以不再提高复杂性。
关于c++ - 计算所有对之间的曼哈顿距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52905348/