Асимптотика Array (массива)

Junior PRO

Суть

Array — динамический массив: непрерывный буфер с count и capacity, value-тип с copy-on-write. Отсюда вся асимптотика.

• Чтение/запись по индексу — O(1).
• append — O(1) амортизированно; когда буфер заполнен, выделяется новый вдвое большего размера и элементы копируются — O(n) на этой операции, но редко.
• insert(_:at:) — O(n): сдвиг всех элементов правее позиции. Вставка в начало — худший случай.
• removeLast() / popLast() — O(1).
• remove(at:) / removeFirst() — O(n) (сдвиг).
• contains, firstIndex(of:) — O(n): линейный поиск.
• count, isEmpty, first, last — O(1).
• Копирование let b = a — O(1) (общий буфер); первая мутация разделяемого буфера — O(n) из-за CoW.

var a = [1, 2, 3]
a.append(4)               // O(1) амортизированно
a.insert(0, at: 0)        // O(n)
a.removeLast()            // O(1)
a.removeFirst()           // O(n)
_ = a.contains(3)         // O(n)
_ = a[1]                  // O(1)
var b = a                 // O(1): общий буфер
b.append(5)               // O(n): первая мутация копирует буфер (CoW)
a.reserveCapacity(1_000)  // чтобы append не реаллоцировал