Расчет Манхэттенского расстояния между всеми парами

Question

У меня есть список (вектор в c ++) координат (x, y) некоторых вершин из матрицы, например, [ (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), вы больше не сможете улучшить сложность.