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

Алгоритмическая сложность вставки в конец массива

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

O(1) - типичный случай

Если в конце массива есть свободное место, вставка происходит за константное время O(1):

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

// Первые операции работают за O(1)
list.add("A");  // O(1) - вставляем в конец
list.add("B");  // O(1) - вставляем в конец
list.add("C");  // O(1) - вставляем в конец

// Внутренне ArrayList имеет capacity больше size
// Capacity = 10 по умолчанию в Java
// Size = 3
// Свободного места = 7 элементов

O(n) - случай, когда нужно расширение

Если массив переполнился (размер = capacity), ArrayList должен создать новый больший массив и скопировать все элементы. Это O(n):

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

// Добавляем 10 элементов
for (int i = 0; i < 10; i++) {
    list.add("item" + i);  // Первые 9 - O(1)
}

// На 10-й операции capacity переполнится
// ArrayList создаст новый массив размером 15 (10 + 10/2)
// Скопирует все 10 элементов туда - O(n)
// Потом вставит новый элемент
list.add("item10");  // O(n) - из-за расширения!

Визуально как это работает

До вставки 11-го элемента:
index:    0  1  2  3  4  5  6  7  8  9
value:   [A][B][C][D][E][F][G][H][I][J][_][_][_][_][_]
                                        ^
                              size=10, capacity=10
                              Переполнен!

Операция add("K"):
1. Создаём новый массив размером 15
2. Копируем все 10 элементов - O(10) = O(n)
3. Вставляем новый элемент

После вставки:
index:    0  1  2  3  4  5  6  7  8  9  10 11 12 13 14
value:   [A][B][C][D][E][F][G][H][I][J][K][_][_][_][_]
                                           ^
                              size=11, capacity=15
                              Теперь есть свободное место

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

Хотя иногда O(n), в целом операция работает за O(1) амортизированно:

// Амортизированная сложность - средняя за много операций
ArrayList<String> list = new ArrayList<>();

// Первые 10 операций: 10 * O(1) = O(10)
for (int i = 0; i < 10; i++) {
    list.add("item" + i);  // O(1) каждая
}

// 11-я операция: O(10) из-за копирования
list.add("item10");  // O(10)

// Следующие операции снова O(1)
for (int i = 11; i < 15; i++) {
    list.add("item" + i);  // O(1) каждая
}

// 16-я операция: O(15) из-за нового копирования
list.add("item15");  // O(15)

// Амортизированная сложность:
// (10*1 + 1*10 + 4*1 + 1*15) / 16 = 40 / 16 = 2.5 = O(1)
// То есть в среднем каждая операция стоит O(1)

Внутренняя реализация ArrayList

public class ArrayList<E> {
    private Object[] elementData;
    private int size;
    
    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);
        }
    }
    
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        // Новая capacity = старая + половина старой
        // Или 10, если массив пуст
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        
        // Копируем все элементы в новый массив - O(n)!
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

Сравнение структур данных

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

// Плохо - вставляем в конец 1 млн раз
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) {
    list.add(i);  // Часто O(n) при расширениях
}

// Хорошо - заранее выделяем памяти
ArrayList<Integer> list = new ArrayList<>(1_000_000);
for (int i = 0; i < 1_000_000; i++) {
    list.add(i);  // Всегда O(1)
}

// Очень хорошо - если знаем размер заранее
Integer[] array = new Integer[1_000_000];
for (int i = 0; i < 1_000_000; i++) {
    array[i] = i;
}

Рост capacity в ArrayList

Вставка  | size | oldCapacity | newCapacity
---------|------|-------------|------------
1-10     | 1-9  | 10          | 10
10       | 10   | 10          | 15 (10 + 5) - O(10)
11-15    | 11-15| 15          | 15
16       | 16   | 15          | 22 (15 + 7) - O(15)
17-22    | 17-22| 22          | 22
23       | 23   | 22          | 33 (22 + 11) - O(22)

Почему O(1) амортизированная?

Средняя стоимость за длинную последовательность операций остаётся O(1), потому что:

1. Расширения происходят всё реже (capacity растёт экспоненциально)
2. Между расширениями много дешёвых O(1) операций
3. Сумма всех стоимостей расширений примерно равна O(n) для n операций

Операции 1-10: 10 * O(1) = O(10)
Расширение 10→15: O(10)
Операции 11-15: 5 * O(1) = O(5)
Расширение 15→22: O(15)
Операции 16-22: 7 * O(1) = O(7)
Расширение 22→33: O(22)
...

Всего за N операций: O(N)
В среднем за операцию: O(N) / N = O(1)

Главное правило

• Типичный случай: O(1) вставка в конец
• Редкий случай: O(n) при расширении capacity
• Амортизированная сложность: O(1) в целом
• Оптимизация: используй ArrayList(capacity) конструктор, если знаешь размер заранее