Примечание: этот ответ был обновлен для будущих ссылок на основе подробных обсуждений с @Danilo Souza Morães и @burnabyRails, который является автором принятого ответа на аналогичный вопрос Данило. на сайте CS. Основная проблема с исходным ответом заключается в том, что я предположил, что здесь используется / обсуждается немного другой алгоритм. Поскольку первоначальный ответ предоставил Данило некоторые важные сведения, он сохранился, как и в конце. Также, если вы собираетесь прочитать обсуждение , упомянутое Данило в его ответе, обязательно прочитайте вступление здесь, чтобы лучше понять, что я имел в виду. В добавленном предисловии рассматриваются различные версии рассматриваемого алгоритма.
Введение
Этот алгоритм основан на двух основных идеях:
- Типичный рекурсивный подход "разделяй и властвуй"
- Тот факт, что если вы уже знаете наилучшее расстояние как в левой, так и в правой областях, вы можете сделать шаг «объединения» за
O(N) время, потому что вы можете доказать, что вы можете делать проверки для каждой точки за O(1) время .
Тем не менее, существует несколько способов реализации одних и тех же базовых идей на практике, особенно шаг объединения. Основные отличия:
- Вы относитесь к "левой" и "правой" точкам независимо и по-разному?
- Для каждого пункта вы проводите фиксированное количество проверок или вы сначала фильтруете кандидатов и выполняете только дистанционные проверки для отфильтрованных кандидатов? Обратите внимание, что вы можете выполнить некоторую фильтрацию, не прерывая время
O(N*log(N)), если можете убедиться, что она выполняется в амортизированной форме O(1) Другими словами, если вы знаете, что количество хороших кандидатов строго ограничено, вам не нужно проверять именно это количество кандидатов.
Классическое описание алгоритма в CLRS Введение в алгоритмы четко отвечает на вопрос № 1, когда вы смешиваете «левую» и «правую» точки и обрабатываете их совместно. Что касается # 2, ответ менее ясен (для меня), но, вероятно, подразумевает проверку определенного количества точек. Похоже, это та версия, которую Данило имел в виду, задавая вопрос.
Алгоритм, который я имел в виду, отличается в обеих точках: он проходит через «левые» точки и сравнивает их со всеми отфильтрованными «правыми» кандидатами. Очевидно, я не знал об этой разнице, когда писал свой ответ и во время первоначального обсуждения в чате.
«Мой» алгоритм
Вот эскиз алгоритма, который я имел в виду.
Начальные шаги являются общими: мы уже обработали «левую» и «правую» точки и знаем лучший ? софар, и мы отсортировали их по оси Y. Мы также отфильтровали все точки, которые не лежат в полосах ±?.
Внешний цикл состоит в том, что мы проходим «левые» точки вверх. Теперь предположим, что мы обрабатываем один, назовем его «левая точка». Дополнительно и частично независимо мы перебираем «правильные» точки, перемещая «стартовую позицию», когда это необходимо (см. Шаг № 2).
Для каждой левой точки двигайтесь вверх от последней начальной позиции в правильных точках и увеличивайте начальную позицию, пока мы не попадем в диапазон разницы ? (или, скорее, -?) с левой точкой в соответствии с ось Y. (Примечание: разделение «левой» и «правой» точек - это то, что заставляет начинать с -?)
Теперь из этой начальной позиции продолжайте идти вверх и рассчитайте расстояние до всех точек, которые лежат перед +? с текущей левой точкой.
Фильтрация, выполняемая на шагах № 2 и № 3, делает ее «зависимой от данных». Компромисс в этой реализации заключается в том, что вы делаете меньше дистанционных проверок, затрачивая больше Y -чек. Кроме того, код является более сложным.
Почему этот алгоритм объединения работает в O(N)? По той же причине, по которой существует фиксированная граница (т. Е. O(1)) для количества точек, которые можно вписать в прямоугольник ?x2?, чтобы расстояние между каждыми двумя точками было не менее ?. Это означает, что на шаге № 3 будет выполнено O(1) проверки. На практике все расстояния, проверенные этим алгоритмом, будут проверяться CLRS-версией и, в зависимости от данных, могут быть проверены и другие.
Амортизированная стоимость шага № 2 также составляет O(1), поскольку общая стоимость шага № 2 по всему внешнему циклу составляет O(n): вы явно не можете сдвинуть начальную позицию вверх больше раз, чем есть. "правильные баллы" всего.
Модифицированный алгоритм CLRS
Вы можете легко принять другое решение относительно # 2 даже в CLRS-версии алгоритма. Описание решающего шага гласит:
- Для каждой точки
p в массиве Y′ алгоритм пытается найти точки в Y′, которые находятся в пределах δ единиц p. Как мы вскоре увидим, необходимо учитывать только 7 пунктов в Y′, следующих за p. Алгоритм вычисляет расстояние от p до каждой из этих 7 точек и отслеживает расстояние ближайшей пары δ′, найденное по всем парам точек в Y′
Его легко изменить, чтобы проверить не 7 точек, а сначала проверить, меньше ли разница в Y, чем ?. Очевидно, вам по-прежнему гарантируется необходимость проверять не более 7 баллов. Опять же, компромисс заключается в том, что вы делаете меньше дистанционных проверок, но делаете некоторые проверки Y. В зависимости от ваших данных и относительной производительности различных операций на вашем оборудовании это может быть хорошим или плохим компромиссом.
Некоторые другие важные идеи
Если вам не нужно находить все пары с минимальным расстоянием, вы можете безопасно использовать <?`` instead of <= ?` при фильтрации </p>
В мире реальных аппаратных средств с представлением чисел с плавающей запятой идея = не столь ясна. Обычно вам все равно нужно проверить что-то вроде abs(a - b) < έ.
Идея, стоящая за моим контрпримером (для другого алгоритма): вам не нужно ставить все точки по краям. Равносторонний треугольник со стороной ? может вписаться в квадрат с размером ?-έ (иначе говоря <?)
Оригинальный ответ
Не думаю, что вы правильно понимаете значение этой константы 7 в этом алгоритме. На практике вы не проверяете 4 или 7 или любое другое фиксированное количество точек, вы идете вверх (или вниз) вдоль оси Y и проверяете те, которые попадают в соответствующий прямоугольник. Таких точек может быть просто 0. Что действительно важно для работы алгоритма в обещанное время O(n*log(n)), так это наличие фиксированной верхней границы для количества точек, проверенных на этом шаге. Любая константа верхняя граница будет работать до тех пор, пока вы можете это доказать. Другими словами, важно, чтобы этот шаг был O(n), а не конкретной константой. 7 - это сравнительно легко доказать, и все.
Я полагаю, что практическая причина для 7 заключается в том, что на реальном оборудовании вы не можете делать точные вычисления расстояний в типах данных с плавающей запятой, у вас обязательно будут некоторые ошибки округления. Вот почему использование < вместо <= не очень практично.
И, наконец, я не думаю, что 4 - это правильная граница, при условии, что вы можете надежно выполнить <. Давайте предположим, что ? = 1. Пусть «левая» точка будет (-0.0001; 0), поэтому «правый» < прямоугольник для нее будет 0 <= x < 1 и -1 < y < 1. Рассмотрим следующие 5 точек (идея состоит в том, что 4 точки почти в углах просто соответствуют прямоугольнику < ? и расстояниям между ними > ?, а пятая находится в центре прямоугольника):
P1 = (0.001; 0.999)P2 = (0.999; 0.93)P3 = (0.001; -0.999)P4 = (0.999; -0.93)P5 = (0.5; 0)
Обратите внимание, что эти 5 точек должны быть больше чем ? между собой, некоторые из них могут быть меньше, чем ? от "левой" точки. Вот почему мы проверяем их в первую очередь.
Расстояние P1-P2 (и симметрично P3-P4) равно
sqrt(0.998^2 + 0.069^2) = sqrt(0.996004 + 0.004761) = sqrt(1.000765) > 1
Расстояние P1-P5 (и симметрично P3-P5) равно
sqrt(0.499^2 + 0.999^2) = sqrt(0.249001 + 0.998001) = sqrt(1.247002) > 1
Расстояние P2-P5 (и симметрично P4-P5) равно
sqrt(0.499^2 + 0.93^2) = sqrt(0.249001 + 0.8649) = sqrt(1.113901) > 1
Таким образом, вы можете поместить 5 точек в такой < прямоугольник, который явно больше, чем 4.