Когда алгоритмическая сложность операции добавления элемента в конец динамического массива (append) превышает O(1)?

Операция append (добавление в конец) для динамического массива имеет амортизированную сложность O(1), но в наихудшем случае (worst-case) её сложность равна O(n).

Причина: Когда при добавлении нового элемента текущая вместимость (capacity) массива исчерпана, происходит реаллокация:

1. Выделяется новый, больший блок памяти (обычно capacity увеличивается в 1.5-2 раза).
2. Все существующие n элементов копируются в новый блок.
3. Старый блок памяти освобождается.

Этот процесс копирования и делает единичную операцию в этот момент O(n).

Пример на Swift:

var array = [Int]()
// Предположим, начальная capacity = 0
array.append(1) // Реаллокация: capacity -> 1
array.append(2) // Реаллокация: capacity -> 2
array.append(3) // Реаллокация: capacity -> 4
// Копируются 2 элемента. Следующие 3 операции append будут O(1).

Оптимизация: Чтобы избежать частых реаллокаций при известном ожидаемом размере, используйте reserveCapacity(_:).

array.reserveCapacity(1000) // Одна реаллокация под 1000 элементов.
for i in 0..<1000 {
    array.append(i) // Все 1000 операций будут O(1).
}