Я ищу мотивационный пример для «проблемы с ближайшей парой точек».
http://en.wikipedia.org/wiki/Ближайшая_пара_точек_проблемы
Сама по себе это довольно понятная проблема, но я не могу найти разумного случая, когда такой алгоритм с o (n log n) был бы необходим вместо подхода грубой силы в o (n2) .
Какие-либо предложения?
Разумным случаем для использования алгоритма O(nlogn) над O(n^2) является каждый случай, который обрабатывает такое большое количество элементов, что O(n^2) требует больше времени для выполнения, чем O(nlogn). Например, перебор O(n^2) с 1 миллионом элементов может занять около получаса, в то время как алгоритм Divine & Concrete O(nlogn) занимает всего несколько секунд. Очень быстрый способ увидеть разницу (1 миллион ^ 2) и (1 миллион * log2 (1 миллион)), вы можете увидеть огромную разницу.
