Асимптотическая сложность операций для 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) возникает прRegister or sign in to get access to full answers for all questions from the question bank.