Выбор ответа Junior Контейнеры STL изнутри спрашивают часто обновлено
Сложность push_back
Вопрос
Какая сложность у std::vector::push_back?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Амортизированно O(1): ёмкость растёт геометрически. Ёмкость растёт в разы (в 2 раза в libstdc++ и libc++, в 1,5 в MSVC), поэтому суммарная стоимость n вставок O(n), и на одну вставку в среднем O(1). - Отдельная вставка с реаллокацией стоит O(n), поэтому «всегда O(1)» неверно. - O(n) на…
Варианты ответа
- Всегда O(1): память под элементы выделяется блоками заранее
- Амортизированно O(1): ёмкость растёт геометрическиправильный ответ
- Всегда O(n): каждая вставка копирует весь буфер заново
- O(log n): ёмкость удваивается, и число шагов логарифмическое
Разбор
Ёмкость растёт в разы (в 2 раза в libstdc++ и libc++, в 1,5 в MSVC), поэтому суммарная стоимость n вставок O(n), и на одну вставку в среднем O(1).
- Отдельная вставка с реаллокацией стоит O(n), поэтому «всегда O(1)» неверно.
- O(n) на каждую вставку было бы при росте на константу.
- Логарифм характерен для деревьев.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.