Почему добавление в конец ArrayList считается амортизированно O(1), хотя иногда требует копирования всего массива?
- Как растёт ArrayList?
- Почему add в ArrayList считают амортизированной O(1), если при переполнении происходит копирование всего массива?
Ёмкость растёт в 1,5 раза: копирования всё реже, сумма копирований на n вставок — геометрическая прогрессия, то есть O(n). На одну вставку — константа в среднем, хотя отдельная вставка бывает O(n).
- Ёмкости: 10, 15, 22, 33, 49, 73…
- Рост на константу дал бы O(n²) в сумме
- Известный размер — задать ёмкость в конструкторе
А ещё «Амортизированно» — в среднем по последовательности операций, без вероятностей
Подробно
Ключ в мультипликативном росте: в HotSpot новая ёмкость считается как старая плюс половина старой. Из-за этого расширения происходят всё реже, а сумма всех копирований образует убывающую геометрическую прогрессию и остаётся линейной от n. Если бы массив рос на фиксированную величину, суммарная стоимость была бы квадратичной. Важно понимать, что амортизированная оценка — про среднее по серии операций: отдельное добавление, попавшее на расширение, всё равно стоит O(n), и для чувствительных к задержке участков ёмкость задают заранее через конструктор.
Что хотят услышать
- Мультипликативный рост и редкость копирований.
- Расчёт суммарной работы.
- Отличие от роста на константу.
Частые ошибки
- Путать амортизированную оценку с гарантией на каждую операцию.
- Считать, что ArrayList растёт вдвое — в HotSpot это полтора раза.
Проверьте себя
Один верный вариант. Подумайте, потом откройте ответ.
Показать варианты и ответ
- ✗Массив растёт на один элемент, поэтому каждое копирование небольшое и дешёвое
- ✗Копирование выполняется в фоновом потоке и не задерживает вызов add
- ✓Ёмкость растёт в полтора раза, поэтому суммарная цена копирований на n вставок линейна
- ✗JVM оптимизирует System.arraycopy до константного времени для любого размера
Что спросят дальше
- Когда стоит задавать начальную ёмкость?
- Уменьшается ли ArrayList автоматически после удалений?
- Почему вставка в середину остаётся O(n) даже при запасе ёмкости?
- Что делает trimToSize и когда он нужен?
Разбор темы
- ArrayList: динамический массив изнутри
Бэкенд-массив, рост в 1.5×, амортизированная O(1), стоимость вставки/удаления и когда массив лучше.
Связанные вопросы
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.