Частные случаи могут зависеть от реализации, но для стандартных контейнеров сложность операций выглядит следующим образом:
std::vector
| Операция | Средняя сложность | Худшая сложность | Примечание |
|---|---|---|---|
| Доступ по индексу | O(1) | O(1) | operator[], at() |
| Вставка в конец | O(1) амортизированная | O(N) | push_back() (при необходимости перераспределения) |
| Вставка в произвольное место | O(N) | O(N) | |
| Удаление с конца | O(1) | O(1) | pop_back() |
| Удаление из произвольного места | O(N) | O(N) | |
| Поиск элемента | O(N) | O(N) | std::find (независимо от контейнера) |
| Изменение размера | O(N) | O(N) | resize(), reserve() (при увеличении емкости) |
std::list
| Операция | Средняя сложность | Худшая сложность | Примечание |
|---|---|---|---|
| Доступ по индексу | O(N) | O(N) | Требует итерации от начала или конца к нужному элементу |
| Вставка в к |
Частные случаи могут зависеть от реализации, но для стандартных контейнеров сложность операций выглядит следующим образом:
std::vector
| Операция | Средняя сложность | Худшая сложность | Примечание |
|---|---|---|---|
| Доступ по индексу | O(1) | O(1) | operator[], at() |
| Вставка в конец | O(1) амортизированная | O(N) | push_back() (при необходимости перераспределения) |
| Вставка в произвольное место | O(N) | O(N) | |
| Удаление с конца | O(1) | O(1) | pop_back() |
| Удаление из произвольного места | O(N) | O(N) | |
| Поиск элемента | O(N) | O(N) | std::find (независимо от контейнера) |
| Изменение размера | O(N) | O(N) | resize(), reserve() (при увеличении емкости) |
std::list
| Операция | Средняя сложность | Худшая сложность | Примечание |
|---|---|---|---|
| Доступ по индексу | O(N) | O(N) | Требует итерации от начала или конца к нужному элементу |
| Вставка в к |
Зарегистрируйтесь или войдите, чтобы получить доступ к полным ответам на все вопросы из банка вопросов.