У меня есть задание, которое сравнивает 2 разных алгоритма для проблемы. Вот проблема:
Предположим, у меня есть ряд таких координат xy:
A(2,3), B(5,6), C(7,8), D(6,2), E(5,5) и т.д..
И я хочу найти 2 координаты, которые имеют кратчайшее расстояние между ними. Одним из решений является использование грубой силы (сопоставление их одного за другим), но есть и другое решение, использующее метод «разделяй и властвуй».
Не могли бы вы помочь мне с методом «разделяй и властвуй»?
Рекурсивный подход «разделяй и властвуй» работает следующим образом:
1) Отсортировать точки по их координатам x.
2) Разделить набор точек на два подмножества одинакового размера вертикальной линией x=xmid.3) Рекурсивно решить задачу в левом и правом подмножествах. Это
дает минимальное расстояние слева и справа dLmin и dRmin соответственно.4) Найдите минимальное расстояние dLRmin среди пары точек, в которых одна точка лежит слева от разделяющей вертикали, а вторая — справа.
5) Окончательный ответ – это минимум среди dLmin, dRmin и dLRmin. (источник)
Он имеет сложность O(n log n). Также есть реализация псевдокода здесь и визуальное описание метода здесь.
Подумайте о том, что означают части «разделить» и «слить». Очевидно, что «разделить» означает разделить проблему на 2 более мелкие отдельные. Как? Затем, учитывая, что вы решили две меньшие проблемы, как вы объедините их вместе? Какова временная сложность обоих методов? Если вам нужно больше разъяснений, оставьте комментарий.
