Сложность времени для ближайшей проблемы пары T (n) = 2T (n/2) + O (n). Я понимаю, что 2T (n/2) исходит из того, что алгоритм применяется к 2 наборам половины размера оригинала, но почему остальные выходят в O (n)? Благодарю.Где O (n) исходит из временной сложности алгоритма ближайших пар?
Любой алгоритм разделения и покоя будет состоять из рекурсивного компонента «разделение» и компонента «слияния», где рекурсивные результаты объединяются. Линейная компонента O (n) в шкафу состоит из объединения результатов с шага «деление» в объединенный ответ.
спасибо. – Evan
Существует также вариант развертки, который также работает в O (n log n) времени. Вы сохраняете точки, которые достаточно близки к линии развертки в сбалансированном двоичном дереве, тогда вы исследуете точки, которые ближе к точке охвата, чем ближайшая пара, найденная до сих пор. Максимальное количество таких «близких» точек составляет не более, поэтому вы получаете общее время O (n log n). – tmyklebu
Отъезд http://en.wikipedia.org/wiki/Closest_pair_of_points_problem, в котором четко указано, откуда находится O (n) (корпус Planar).
Вам нужно указать, какой алгоритм вы используете. – chepner