Какая временная сложность вставки в конец в ArrayList?

# Временная сложность вставки в конец ArrayList

Ответ: O(1) амортизированно (amortized O(1))

Вставка элемента в конец ArrayList обычно O(1), но иногда O(n).

Два сценария

Сценарий 1: Есть свободное место (O(1))

ArrayList<String> list = new ArrayList<>();
// Capacity = 10, size = 0

list.add("A");  // O(1) - просто добавить в элемент
list.add("B");  // O(1)
list.add("C");  // O(1)
list.add("D");  // O(1)
list.add("E");  // O(1)

// capacity = 10, size = 5
// Все добавления O(1) - прямое присваивание в массив

Сценарий 2: Нет свободного места (O(n))

ArrayList<String> list = new ArrayList<>();
// Capacity = 10, size = 10 (полно!)

list.add("K");  // O(n)!
// Нужно:
// 1. Создать новый массив capacity = 15
// 2. Скопировать все 10 элементов (O(n))
// 3. Добавить новый элемент

// Итого: O(n) операция

Амортизированный анализ

Препаксполнение растет на 1.5x:

По следующей математике O(1) амортизированно:

Операция 1-10:   O(1) каждая  = 10 * O(1)
Операция 11:     O(10) копирование + O(1) вставка = O(11)
Операция 12-15:  O(1) каждая  = 4 * O(1)
Операция 16:     O(15) копирование + O(1) вставка = O(16)
Операция 17-22:  O(1) каждая  = 6 * O(1)
Операция 23:     O(22) копирование + O(1) вставка = O(23)

Средняя стоимость одной вставки:
(10*1 + 11 + 4*1 + 16 + 6*1 + 23) / 22 операций
= 80 / 22 ≈ 3.6 ≈ O(1)

Код вставки в ArrayList

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Проверяем место
    elementData[size++] = e;            // Вставляем O(1)
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);  // O(n) если нужно расширение
    }
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // Увеличение на 50%
    
    // Копируем все элементы - O(n)
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Сравнение операций

Добавление в конец:
- 90% случаев: O(1)
- 10% случаев: O(n) когда нужно увеличение
- Амортизированно: O(1)

Добавление в начало [add(0, e)]:
- Всегда O(n) - нужно сдвинуть все элементы

Добавление в середину [add(i, e)]:
- O(n) - нужно сдвинуть элементы после позиции i

Практический пример

ArrayList<Integer> list = new ArrayList<>();

long startTime = System.nanoTime();

for (int i = 0; i < 1000000; i++) {
    list.add(i);  // Обычно O(1), иногда O(n)
}

long duration = System.nanoTime() - startTime;
System.out.println("Time: " + duration / 1_000_000 + " ms");
// Результат: ~10-20 ms (很fast)

// Если бы это было O(n) для каждой операции:
// Ожидаемо: ~5 сек (очень медленно)

Вывод

Вставка в конец ArrayList:

• Амортизированная сложность: O(1)
• Worst case: O(n) когда нужно расширение
• Best case: O(1) когда есть свободное место

Это почему ArrayList эффективен для вставок в конец. Для вставок в начало/середину - используй LinkedList (O(1) вставка после поиска).