Ответ
Добавление в конец (append) обычно имеет сложность O(1), если в буфере есть свободная емкость. Это происходит потому, что элемент просто помещается в следующую доступную позицию.
Добавление в начало (insert) имеет сложность O(n), так как требует сдвига всех существующих элементов на одну позицию для освобождения места.
Пример на Swift (Data):
var buffer = Data([1, 2, 3])
// Медленно: O(n)
buffer.insert(0, at: 0) // Теперь [0, 1, 2, 3]
// Быстро: O(1) (амортизированно)
buffer.append(4) // Теперь [0, 1, 2, 3, 4]Практическое следствие: Для частых операций вставки в начало следует рассмотреть другие структуры данных, такие как:
- Двусвязный список (LinkedList) – вставка в начало O(1).
- Дек (Deque) – эффективные операции с обоих концов.
- Использование reversed() – хранение данных в обратном порядке для превращения добавления в конец во вставку в начало.
Ответ 18+ 🔞
А, слушай, вот тебе наглядный пример, почему иногда код тормозит как муха в патоке. Всё упирается в эту самую сложность, в то, как данные внутри устроены.
Представь себе очередь в столовую, блядь. Люди стоят плотно, друг за дружкой. Добавить нового человека в конец — вообще не проблема, ёпта. Подошёл, встал за последним — и всё, O(1). Быстро и без нервов.
А теперь попробуй впихнуть нового человека в самое начало этой очереди, прямо перед тем, кто первый стоит. Что придётся делать? Правильно, сука, всех по цепочке сдвигать на шаг назад, чтобы освободить место! Чем очередь длиннее, тем больше движений, тем дольше всё это. Вот тебе и O(n), блядь, линейная сложность. Всех переставлять — это тебе не хухры-мухры.
Вот смотри, как это в коде выглядит, на примере Data в Swift (код не трогаю, он святой):
var buffer = Data([1, 2, 3])
// Медленно, как черепаха в смоле: O(n)
buffer.insert(0, at: 0) // Теперь [0, 1, 2, 3]
// Быстро, как удар током: O(1) (амортизированно)
buffer.append(4) // Теперь [0, 1, 2, 3, 4]Видишь разницу? insert в начало — это пиздец какой дорогой, а append в конец — копейки.
Так что из этого следует, гений ты мой луковый? А следует вот что: если твоя программа постоянно, как одержимая, пытается пихать данные в начало коллекции — ты выбрал не тот инструмент, дружок-пирожок. Твой массив или Data будут орать от боли и всё виснуть.
Смотри, какие есть варианты выкрутиться, чтобы не выглядеть полным дауном:
- Двусвязный список (LinkedList) – Тут вставка в начало — это O(1), потому что ты просто перепривязываешь парочку ссылочек, а не всю очередь двигаешь. Красота!
- Дек (Deque) – Умная структура, которая заточена под эффективную работу с обоими концами. И спереди добавить, и сзадь — всё быстро.
- Хитрый трюк с reversed() – Самый простой костыль, но иногда работает. Храни данные задом наперёд! Тогда твоё "добавить в начало" на самом деле станет "добавить в конец" перевёрнутого массива. Добавил, а потом когда надо прочитать — развернул обратно. Ёперный театр, но работает.
Короче, думай головой, что ты делаешь. Не лезь с O(n) операцией в цикл, который выполняется миллион раз, а потом не удивляйся, что всё ебёт кирпичи. Выбор структуры — это половина успеха, блядь.