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

Сложность вставки в конец ArrayList

Краткий ответ

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

• В среднем: O(1) amortized (амортизированная сложность)
• В худшем случае: O(n) (когда нужен resize массива)

Как работает ArrayList

ArrayList расширяет свой внутренний массив постепенно. Когда массив переполнен, происходит резкий resize:

public class ArrayList {
    private Object[] elementData;
    private int size;
    
    public void add(E e) {
        ensureCapacity(size + 1);
        elementData[size++] = e;
    }
    
    private void ensureCapacity(int minCapacity) {
        if (minCapacity > elementData.length) {
            // Увеличиваем примерно на 50%
            int newCapacity = (int)(elementData.length * 1.5);
            Object[] newArray = new Object[newCapacity];
            System.arraycopy(elementData, 0, newArray, 0, size);
            elementData = newArray;  // O(n) операция!
        }
    }
}

Анализ по операциям

Обычная вставка (без resize):

arrayList.add(42);  // O(1)

Вставка с resize:

// Список на 1000 элементов, попыталась добавить 1001-й
arrayList.add(element);  // O(1000) - копирование всех элементов

Амортизированная O(1) сложность

Почему в среднем O(1)? Потому что resize не происходит в каждой операции:

Добавляем элементы:
[1]:     O(1)  - нет resize
[2]:     O(1)  - нет resize
[3]:     O(1)  - нет resize
[4]:     O(1)  - нет resize
[5]:     O(4)  - resize! копируем 4 элемента
[6]:     O(1)  - нет resize
[7]:     O(1)  - нет resize
[8]:     O(1)  - нет resize
[9]:     O(8)  - resize! копируем 8 элементов
...

Общее время для n операций:
O(1 + 1 + 1 + 1 + 4 + 1 + 1 + 1 + 8 + ...) = O(n)
Средняя сложность на одну операцию = O(n) / n = O(1)

Худший случай

ArrayList<Integer> list = new ArrayList<>(1000);
for (int i = 0; i < 1000; i++) {
    list.add(i);  // O(1) каждый раз
}
list.add(1000);  // O(1000) - нужно скопировать все 1000 элементов!

Сравнение со вставкой в начало

// Вставка в конец: O(1) amortized
arrayList.add(element);

// Вставка в начало: O(n)
arrayList.add(0, element);  // Нужно сдвинуть все элементы

// Вставка в середину: O(n)
arrayList.add(500, element);  // Нужно сдвинуть половину элементов

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

ArrayList<Integer> list = new ArrayList<>();
long start = System.nanoTime();
for (int i = 0; i < 1000000; i++) {
    list.add(i);  // O(1) amortized
}
long time = System.nanoTime() - start;
System.out.println(time);  // примерно 10-50 миллисекунд

// Если бы это был O(n) в каждой операции:
// Времени потребовалось бы: 1000000^2 = 10^12 операций
// Это было бы минуты/часы вычислений!

LinkedList vs ArrayList

// ArrayList: добавление в конец O(1), начало O(n)
arrayList.add(element);           // O(1)
arrayList.add(0, element);        // O(n)

// LinkedList: добавление везде O(1)
linkedList.add(element);          // O(1)
linkedList.add(0, element);       // O(1)

Поэтому для добавления в конец ArrayList лучше, а для добавления в начало LinkedList лучше.

Итоговая таблица

Вывод

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