Junior
215
Mi az aszimptotikus komplexitása a list és vector tárolókban az elemek beszúrásának és törlésének?
Válasz az MI-től
sobes.tech MI
std::vector:
| Операция | Асимптотическая сложность | Примечания |
|---|---|---|
| Вставка | O(N) в худшем случае | Требует сдвига всех последующих элементов. |
Вставка в конец (push_back) |
Амортизированная O(1) | Может потребовать перевыделения памяти O(N). |
| Удаление | O(N) в худшем случае | Требует сдвига всех последующих элементов. |
Удаление с конца (pop_back) |
O(1) | Не требует сдвигов. |
std::list:
| Операция | Асимптотическая сложность | Примечания |
|---|---|---|
| Вставка | O(1) | Требует лишь изменения указателей. |
| Удаление | O(1) | Требует лишь изменения указателей. |