В каком сценарии мы делали вставку в Big-O(1), когда массив заполнен?

Question

В каком сценарии мы делали вставку в Big-O(1), когда массив заполнен?

Использование хеш-таблиц, если массив полностью заполнен, чем лучший метод / сценарий, который мы можем сделать в Big-O(1)... объясните мне подробно.

-2

arrays algorithm data-structures hashtable insertion

Источник

user6301319 10 май '16 в 03:54

1 ответ

Другие вопросы по тегам arrays algorithm data-structures hashtable insertion

user477008 10 май '16 в 15:59 2016-05-10 15:59 · Answer 1 · 2016-05-10 15:59

Если массив полностью заполнен (что никогда не должно быть разрешено [Edit: caveat, см. Комментарии]), то невозможно вообще ничего вставить без его расширения, что невозможно сделать за O(1). Если вы не имеете в виду амортизированный O(1) раз. Но в любом случае лучший способ - не допустить полного заполнения массива до его расширения, потому что тогда все операции ухудшаются до O(n) времени.