Что такое амортизированная сложность и как она применяется к операциям расширения ArrayList

Что проверяют

Различаете ли вы амортизированную оценку и среднюю. Вопрос базовый, но по ответу видно, читал ли человек про устройство коллекций или пересказывает, что добавление в список «быстрое».

Как отвечать

Амортизированная сложность это стоимость операции, усреднённая по любой последовательности из n операций. Важно слово «любой»: это гарантия для худшего случая на серии, а не вероятностное среднее по распределению входных данных. Средний случай зависит от того, какие данные придут, амортизированная оценка не зависит ни от чего.

ArrayList хранит элементы в массиве. Пока есть место, добавление в конец это запись по индексу, O(1). Когда место кончилось, создаётся новый массив, элементы копируются через System.arraycopy, и одна конкретная вставка стоит O(n). Ключ в том, что ёмкость растёт умножением: ArrayList берёт полторы прежней ёмкости. Значит, между двумя расширениями успевает пройти столько дешёвых вставок, сколько стоило копирование, и суммарная стоимость n вставок остаётся O(n), то есть O(1) на операцию амортизированно.

Проверьте это суммой: копирования дают ряд вида n плюс половина n плюс четверть n и так далее, геометрическая прогрессия сходится к константе, умноженной на n.

Полезно добавить: если растить массив на фиксированный кусок, а не в разы, расширений становится линейно много, и амортизированная стоимость вставки превращается в O(n). Когда размер известен заранее, его задают в конструкторе или через ensureCapacity.

Где спотыкаются

Говорят «в среднем O(1)» и на уточняющий вопрос не могут отличить это от амортизированной оценки. Формулировка через среднее звучит похоже, но допускает неудачный вход, а здесь его не бывает: гарантия держится на любой серии операций.

Переносят O(1) на весь класс. Амортизированно дешёвая только вставка в конец. Вставка и удаление по индексу, а также поиск значения остаются O(n), потому что двигают хвост массива или сканируют его целиком.

Забывают про память. В момент копирования в куче лежат обе версии массива сразу, старая остаётся мусором, а удаление элементов не уменьшает ёмкость обратно: для этого есть trimToSize.