Путаница с временной сложностью в «Найти пару с заданной разницей»

Question

Я пытаюсь узнать сложность времени с помощью алгоритмов. Я нашел эту проблему интересной, которая гласит: «Найти пары с данной разницей». Я понимаю проблему и сужу до двух методов, которые:

1. Using Binary search (Time complexity: O(nLogn) in worst case) 
2. Use hash (Time comlexity: O(n), Space complexity : O(n)) 

Пожалуйста, кто-нибудь может объяснить, какой из них лучше реализовать. Благодарю.

В случае ссылки я имею в виду эту проблему: http://www.geeksforgeeks.org/count-pairs-difference-equal-k/

Answer 1

Пожалуйста, может кто-то объяснить, какой из них лучше реализовать.

Это дизайнерское решение, и для него нет четкого ответа. Каждое решение имеет свои преимущества и недостатки, а выбор «правильного» зависит от реальных потребностей.
Некоторые примеры соображения:

1. Если память очень ограничена, или поток элементов очень велико (скажем, это на файле размером 10GB), решение хеширования становится неосуществимым, так как вы не можете сохранить его не- память и решение сортировки + бинарный поиск становится более привлекательным.
2. Если вам требуется самое быстрое среднее время для больших массивов, и у вас столько памяти, сколько вы хотите - хешинговое решение становится более привлекательным из-за средней сложности времени O(n).
3. Если ваше приложение работает в режиме реального времени, и вы не можете себе это позволить, то в любом случае это займет O(n^2), независимо от того, насколько мала вероятность - он сломает вашу компанию. Поскольку хеширующее решение распадается на O(n^2) в худшем случае (очень редкий случай), вы захотите его избежать, и снова - сортировка становится более привлекательной.
4. Поскольку обе они относительно эффективны, и если нет реальных ограничений (это, вероятно, 99% случаев), тот, который будет проще реализовать и поддерживать, тот, который вы должны предпочесть.