Самый близкий парный алгоритм из (n log^2 n) в (n log n) time

Question

Я пытаюсь понять, как перейти от n log^2 n к n log n времени для парного парного алгоритма. Я получаю ниже часть (от http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html)

1. Divide множество на две равные по размеру части линией л, и рекурсивно вычислить минимальное расстояние в каждой части.
2. Пусть d - минимальное из двух минимальных расстояний.
3. Устранить точки, которые лежат дальше, чем d, кроме л
4. Сортировать остальные точки в соответствии с их у-координаты
5. Сканирование оставшихся точек в том порядке, у и вычисления расстояний каждой точки до пяти его соседей.
6. Если какое-либо из этих расстояний меньше, чем d, обновите d.

Этап 4 - это сортировка, которая занимает время O (n log n), которое доминирует во всех остальных шагах, и это то, что необходимо свести к O (n), чтобы общий алгоритм достиг бы O (n log n). И это та часть, с которой мне трудно понять. Автор предлагает

Шаг 1: Разделите набор на ... и рекурсивно вычислите расстояние в каждой части, возвращая точки в каждом наборе в отсортированном порядке по y-координате. Шаг 4: Объедините два отсортированных списка в один отсортированный список в O (n) времени.

Вам по-прежнему приходится сортировать точки по y-координате на рекурсивном шаге, который принимает время O (n log n). Как мы можем избежать этого? Слияние - это O (n), но нам все равно придется сортировать.

Answer 1

Причина того, что O (п   журнала   п) проблема в том, что мы делаем это снова и снова и снова: если мы разобьем множество на два подмножества, и разбиение каждого из них на два подмножеств, то это включает семь сортов (один по всему набору, два по половине его, четыре над четверти его).

поэтому предложение фиксирует это на повторное использование результатов предыдущих видов: так мы делаем полные слияния-виды самых маленьких разделов (каждый из которых является O (1), в общей сложности O (п)), но больше перегородок нам просто нужно сделать одиночный пролет слияния, чтобы объединить результаты. Поэтому мы платим только O ()   журнал   n) цена всего один раз, что хорошо.

Answer 2

Их предложение состоит в том, что у вас есть два (уже отсортированные списки) A и B. Объединение этих в один отсортированный список можно сделать с помощью merge sort (просто шаг (4) в качестве шага слияния в сортировке слияния).

Результат сортировки слияний - это один отсортированный список со всеми членами как A, так и B. После объединения вам больше не нужно ничего сортировать.

Answer 3

Я предоставляю альтернативное решение, которое, возможно, проще понять. Сначала соберите все точки w.r.t с координатой y. Это один раз, используя O (n log n). Есть n точек, и в отсортированном массиве каждый из них имеет некоторый индекс, который не превосходит n. Сохраните индекс каждой точки (добавьте целое число для структуры данных индекса в точку). Затем запустите исходный алгоритм. На этот раз, в тот момент, который мы хотим отсортировать, не сортируйте их с обычным сопоставлением сортировки.Но сортируйте их по их индексу. Мы можем сортировать их в соответствии с их индексом с помощью сортировки radix в O (n). Таким образом, общий процесс равен O (n log n), так как мы использовали сортировку сравнения только один раз, а остальное - T (n) = 2T (n/2) + O (n). Но константа не так хороша, как предложенная в вопросе модификация.

Измененная процедура, предложенная в вопросе, работает как слияние в сортировке слиянием: когда у нас есть два отсортированных списка, нам не нужно сортировать их снова, используя обычную сортировку, мы можем сортировать их, объединив их в O (n).