Ответ
Добавление элемента в массив (Array) имеет сложность O(N) при вставке в начало или в середину, а не в конец.
Причина: Массив хранит элементы в непрерывной области памяти. Вставка нового элемента не в конец требует сдвига всех последующих элементов на одну позицию, что является операцией, линейно зависящей от количества элементов (O(N)).
Примеры сложности:
| Операция | Метод | Сложность | Объяснение |
|---|---|---|---|
| Вставка в начало/середину | insert(_:at: 0) |
O(N) | Требуется сдвиг N элементов. |
| Добавление в конец (амортизированная) | append(_:) |
O(1) | Если есть зарезервированная емкость. |
| Добавление в конец (худший случай) | append(_:) |
O(N) | При исчерпании емкости требуется переаллокация и копирование всех N элементов. |
Код для демонстрации:
var numbers = [1, 2, 3, 4, 5]
// O(N) операция: сдвигает 5 элементов
numbers.insert(0, at: 0) // Массив станет [0, 1, 2, 3, 4, 5]
// O(1) операция (в среднем)
numbers.append(6) // Массив станет [0, 1, 2, 3, 4, 5, 6]
// O(N) операция: сдвигает элементы с индекса 3 и далее
numbers.insert(99, at: 3) // Массив станет [0, 1, 2, 99, 3, 4, 5, 6]Оптимизация: Если требуется частая вставка в начало, рассмотрите использование ContiguousArray (для примитивов) или других структур данных, например, двусвязного списка, где вставка в начало/конец — O(1).