Какой из следующих методов является более эффективным

Question

Постановка задачи: - Учитывая массив целых чисел и целое число k, выведите все пары в массиве, сумма которых равна k

Метод 1: - Сортируйте массив и поддерживайте два указателя: низкий и высокий, начинайте итерацию ...

Сложность времени - O (nlogn)

Сложность пространства - O (1)

Метод 2: - Сохраните все элементы в словаре и выполните процесс

Сложность времени - O (n)

Сложность пространства - O (n)

---

Теперь из двух вышеуказанных подходов, какой из них является наиболее эффективным, и на каком основании я собираюсь сравнить эффективность, время (или) пространство в этом случае, поскольку оба они различны в обоих подходах

Answer 1

1. Я оставил свой комментарий выше для справки.
2. Это было поспешно. Вы предоставляете O (nlogn) время для метода 1 (теперь я думаю, я понимаю?), И это справедливо (извинения ;-).
3. Что будет дальше? Если входной массив нужно использовать снова, то вам нужна отсортированная копия (сортировка не будет на месте), которая добавляет O (n) место.
4. «Итеративная» часть метода 1 такжестоит ~ O (n) времени.
5. Но загрузка словаря в методе 2 - это также ~ O (n) время (предположительно, структура данных с раздачей?) и доступ к словарю - хотя ~ O (1)- медленнее (чем индексирование массива).

Итог: О-нотация полезна, если она может идентифицировать «чрезмерную стоимость» (делая другие незначительными при сравнении), но без намека на использование-случаи (типичные и граничные, подробности, такие как объемы данных и доступные системные ресурсы и т. д.), подобные вопросы (в поисках «обобщенного идеального» ответа) не могут извлечь из этого пользу.

Часто некоторые простые доказательства концепциитесты кода и производительности на репрезентативных данных могут сделать «правильный выбор очевидным» (легче и часто более правильно, чем спекулятивное теоретизирование).

Наконец, при отсутствии четкой производительности wвнутренняя, всегда есть «читабельность кода», чтобы помочь решить; -)