Middle
97
0
questionbank

Какова асимптотическая сложность операций для контейнеров unordered_set и set в C++?

Ответ от нейросети sobes.tech

Асимптотическая сложность операций для std::unordered_set и std::set в C++17:

Операцияstd::unordered_set (средний случай)std::unordered_set (худший случай)std::set
Вставка (insert)O(1)O(n)O(log n)
Удаление (erase)O(1)O(n)O(log n)
Поиск (find)O(1)O(n)O(log n)
ДоступНеприменимоНеприменимоO(log n) (итератор)
  • std::unordered_set основан на хеш-таблице. Средний случай сложности O(1) достигается при хорошей хеш-функции и отсутствии большого количества коллизий. Худший случай O(n) возникает пр

Асимптотическая сложность операций для std::unordered_set и std::set в C++17:

Операцияstd::unordered_set (средний случай)std::unordered_set (худший случай)std::set
Вставка (insert)O(1)O(n)O(log n)
Удаление (erase)O(1)O(n)O(log n)
Поиск (find)O(1)O(n)O(log n)
ДоступНеприменимоНеприменимоO(log n) (итератор)
  • std::unordered_set основан на хеш-таблице. Средний случай сложности O(1) достигается при хорошей хеш-функции и отсутствии большого количества коллизий. Худший случай O(n) возникает пр

Зарегистрируйтесь или войдите, чтобы получить доступ к полным ответам на все вопросы из банка вопросов.

unordered_setsetasymptotic-complexitybig-o-notationdata-structurescontainers