Попарное расстояние точек в одном измерении

Question

Можно ли рассчитать попарное расстояние набора точек в одном измерении (все точки на одной линии) быстрее, чем O (n ^ 2)?

Answer 1

Мы можем создать алгоритм в O (N) для вычисления парного расстояния, если заданные точки линии находятся в массиве. Сложность сортировки будет Nlog (N) , поэтому общая сложность будет Nlog (N) .

Хранить префиксную сумму очков после сортировки в массиве и итогосумма баллов в переменной сумме.

//suppose elements in the array is sorted and psum is prefix sum of array

ans=0, sum=psum[n-1];   //sum is total sum of points

for(i=0;i<n;i++)
   ans+=((sum-psum[i]) - arr[i]*(n-i-1));

// (sum-psum[i]) will give the sum of all the numbers which are greater than arr[i]
// now we need to substract arr[i] (n-i-1) number of times
// all (n*n-n)/2 pairs distance will be calculated

cout<<ans;

Answer 2

Очевидно, что невозможно вычислить расстояния O (N²) за менее чем O (N²) операций.

Если вам нужны только некоторые расстояния по запросу, вы вычисляете одно расстояние в O (1);не делайте предварительных вычислений для всех из них.

Если ваш вопрос на самом деле касается пары ближайших точек, 1D-версия является немедленной: сортировка и поиск ближайших последовательных точек. Самая дальняя пара точек еще проще: найдите минимальное и максимальное время O (N). Или, может быть, вы после еще одной проблемы ...