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

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

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

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

Космическая сложность - O (1)

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

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

Космическая сложность - O (n)

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


arrays data-structures time-complexity big-o space-complexity
person user2978343    schedule 30.09.2019    source источник
comment
Что заставляет вас думать, что существует объективный порядок сравнения пространственной и временной сложности? На чем он будет основан? Если у вас много места, но мало времени, вы бы предпочли более низкую временную сложность. Если у вас почти нет места, но много времени, вы бы предпочли меньшую сложность пространства.   -  person walnut    schedule 30.09.2019
comment
Решите, что важнее. Если вы ограничены в пространстве, вам, возможно, придется принять временные затраты, и наоборот. Кстати: сортировка массива не O (1) ни для времени, ни для пространства.   -  person AlanK    schedule 30.09.2019
comment
@AlanK Существуют алгоритмы сортировки на месте с использованием O (1) дополнительной памяти. Совершенно очевидно, что любой алгоритм с входной длиной n будет использовать как минимум Theta (n) total памяти.   -  person walnut    schedule 30.09.2019
comment
@AlanK, я написал O (1) для пространства, потому что для решения проблемы не было создано дополнительного пространства / памяти ... мы используем тот же массив, который указан ... поэтому постоянная сложность пространства O (1) ... Надеюсь, ты согласен с моим подходом   -  person user2978343    schedule 30.09.2019
comment
Спасибо всем за разъяснение моего вопроса.   -  person user2978343    schedule 30.09.2019
comment
Мне не ясно, как должен работать метод 2, но какой подход лучше, зависит от того, насколько велики ваши ожидаемые входные данные, будут ли вы ограничены пространством и размером любых постоянных факторов между двумя алгоритмами.   -  person Lee    schedule 30.09.2019
comment
Словари @Lee занимают O (1) раз для поиска / поиска элемента в нем. поэтому для n элементов это будет O (n)   -  person user2978343    schedule 30.09.2019
comment
Как вы собираетесь искать только N элементов, когда ищете пары чисел? Есть N ^ 2 возможных пар.   -  person Lee    schedule 30.09.2019
comment
Этот размер ответа в худшем случае равен Ω (n ^ 2), поэтому столько времени уйдет на печать.   -  person Matt Timmermans    schedule 30.09.2019

Ответы (1)


arrow_upward
0
arrow_downward

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

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

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

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

person AlanK    schedule 30.09.2019
comment
эй, ты можешь определить, [leetcode.com/problems/find-the-duplicate-number/discuss/394883/ имеет O (n) пробел или нет - person user2978343; 01.10.2019
comment
@ user2978343: Я давно не играл с Python, но на первый взгляд - да. Чтобы вернуть сумму избыточных (дублированных) значений элементов списка, он создает набор (для которого стоимость места пропорциональна длине списка). Обратите внимание, что в коде нет места O (n), скорее, учитывая список из n элементов, для возврата результата требуется O (n) (дополнительное) пространство. (Операция суммирования требует времени, но (предположительно) не требует затрат места.) - person AlanK; 01.10.2019