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