Сначала ответь вслух
Скажи ответ вслух хотя бы пару минут, потом открой эталон и сравни. Эталон открыт всем и не требует входа.
Показать ответ
Эталонный ответ
Когда массив заполнен, ArrayList создаёт новый в 1,5 раза больше и копирует элементы. Одно такое добавление стоит O(n), но после него следующие добавления дешёвые, пока не кончится запас.
Размеры растут геометрически, поэтому сумма всех копирований за n добавлений ограничена константой, умноженной на n. В среднем на операцию — O(1). Добавление в середину остаётся O(n): элементы справа сдвигаются.
int newCapacity = oldCapacity + (oldCapacity >> 1); // рост в 1,5 раза
List<Order> orders = new ArrayList<>(expectedSize); // без лишних копированийКак у тебя получилось?
Уточняющие вопросы
Так обычно копают глубже. Раскрой строку, когда ответишь вслух.
Уточнение 1-го уровня: Почему рост в разы, а не на фиксированное число элементов?
Ответ уровня Middle
При росте на константу копирований будет n / k, и суммарная работа станет O(n²). Геометрический рост держит её в O(n).
Уточнение 2-го уровня: Уменьшается ли массив после удаления элементов?
Ответ уровня Middle
Нет: ёмкость остаётся прежней. Освободить лишнее можно вызовом trimToSize().
Типичные ошибки
- Путать амортизированную O(1) с O(1) в худшем случае.
- Считать add(index, e) дешёвым.
Первоисточники
Быстрые задания по теме
Для темы «Сложность алгоритмов» быстрых заданий пока нет
Можно проверить всю зону «Алгоритмы» тестом на 10 минут.
Проверить себя за 10 минут