Выбор ответа Middle Сложность обновлено
Амортизированная сложность push
Вопрос
Почему push в динамический массив считают O(1), хотя иногда массив копируется целиком?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Ёмкость растёт в разы, и n вставок в сумме стоят O(n). При заполнении ёмкость увеличивается мультипликативно (например, вдвое).
Варианты ответа
- Копирование выполняется в отдельном потоке и не влияет на время
- Движок JS заранее выделяет память под любое число элементов
- Ёмкость растёт в разы, и n вставок в сумме стоят O(n)правильный ответ
- Это оценка худшего случая, а амортизация тут ни при чём
Разбор
При заполнении ёмкость увеличивается мультипликативно (например, вдвое). Копирования стоят 1 + 2 + 4 + ... + n < 2n, значит n вставок суммарно O(n), в среднем O(1) амортизированно. Отдельная вставка в худшем случае O(n).
- Отдельного потока для копирования нет.
- Бесконечной предвыделенной памяти нет.
- Худший случай одной операции как раз O(n), O(1) это именно амортизированная оценка.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.