Какова сложность времени для вставки n элементов в стек с использованием связанного списка?

Question

Каждая вставка в стек - это O (1), так сколько времени занимает вставка 'n' элементов O (n)? Можем ли мы говорить аналогично для хеш-таблицы? В среднем случае время, необходимое для вставки n элементов в хеш-таблицу = O (n)?

Answer 1

Да. Доминирующим фактором является не время вставки, которое является постоянным, это время, которое требуется для перебора всех вещей, которые вы вставляете. Если бы вставка не происходила в постоянное время, это было бы более сложным.

Обратите внимание, что в случае HashTable многое зависит от того, должен ли HashTable самому расти или перефразировать все в нем, когда это произойдет, но для простого случая (т. Е. Если предположить, что таблица достаточно большая, чтобы вместить все, и генерацию хэш-кода не генерирует коллизий) верхняя граница для вставки должна быть n.

Answer 2

Каждая вставка в стек - это O (1), так сколько времени занимает вставка 'n' элементов O (n)? Можем ли мы говорить аналогичным образом и для хеш-таблицы? В среднем случае время, необходимое для вставить 'n' элементов в хеш-таблицу = O (n)?

Как вы упомянули стек , я предполагаю, что мы разрешаем коллизии в хеш-таблице, используя стек ( в цепочке, используя закрытую адресацию ).

В таком случае я отвечаю:

Да, «в среднем случае время, необходимое для вставки« n »элементов в хэш-таблицу = O (n)».

Чтобы быть более конкретным. Как вставить в хеш-таблицу в вашем случае это:

• создание хэша = O (1)
• вставка в стек, выбранный с хешем = O (1)

Вся вставка хеша - O (1). Так что n операций - это O (n).

Мой совет: будьте очень внимательны к экзамену относительно ваших предположений (структуры, которые вы используете, их реализация и сложность), поскольку все эти детали могут оказать существенное влияние на результат всех уравнений.