Почему вставка в конец динамического массива равна O(1), в то время как вставка в середину равна O (n)?

Question

В соответствии со статьей Википедии о динамические массивы, вставка / удаление в конце массива равно O (1), в то время как вставка / удаление из середины равно O (n).Почему именно это происходит?

Также - если у меня есть динамический массив с 5 элементами, и я вставляю новый элемент в позицию 6, операция равна O (n), тогда как если я использую функцию для добавления в конец массива, это O (1).Разве это не та же самая операция, предполагающая, что массив не нужно изменять в любом случае?Или добавление к динамическому массиву действительно вставляет новый элемент где-то помимо позиции 6?

Спасибо!

Редактировать: Я думаю, что моя главная путаница заключается в разнице между вставкой в конец массива и вставкой в определенную позицию, которая эквивалентна концу массива.

Я полагаю, что указатель на адрес памяти в конце массива хранится под рукой, и именно поэтому операция добавления выполняется быстро.И наоборот, если я укажу точную позицию (даже если это конец массива), он не будет знать, что вставка в эту позицию равносильна использованию вышеупомянутого адреса памяти, поэтому он должен пройти весь массив, не так ли?

Answer 1

Порядок величины будет полностью зависеть от того, какой структурой данных на самом деле является "динамический массив" ("динамический массив" - это не строго определенная структура данных, это скорее желаемый результат, достигаемый при использовании определенной структуры данных).Пример, который вы приводите, будет отражать динамический массив, достигаемый с помощью связанного списка.Добавление в конец могло бы быть O (1), если бы структура списка содержала указатель на конечный элемент.Вставка (независимо от индекса) потребовала бы обхода связанного списка, что означает одну операцию на узел вплоть до получения нужного индекса.

Answer 2

Чтобы вставить в конец массива, вам просто нужно поместить туда элемент.

Чтобы вставить в середину массива, вам нужно переместить элементы после этой точки вверх на единицу.

Чтобы удалить из конца массива, вы просто уменьшаете его количество на единицу.

Чтобы удалить из середины, вы должны сделать это и переложите остальные предметы вниз.

Это тот самый смещение это превращает его в O (n).

Answer 3

Это довольно просто:

Вставка в середину предполагает перемещение каждого последующего элемента на 1.Для вставки в конце, если зарезервировано дополнительное место, элемент просто сохраняется там, но если нет, выделяется новое место.Таким образом, эта операция выполняется в амортизированное постоянное время.

Answer 4

Дополнение к превосходному резюме Адама Робинсона:Это не просто теория.Я видел множество ситуаций, в которых динамический массив создавался путем многократного добавления в конец массива.Это работает до о(N**2) производительность, поскольку массив неоднократно нуждается в перераспределении, что вынуждает копировать каждый из его элементов в новую структуру массива.Перераспределение может происходить только в 1/10 операций добавления, но это достаточно плохо и все еще не выполняется.(N**2) с точки зрения производительности.

В STL этого снижения производительности можно избежать, вызвав vector::reserve(N) перед записью в вектор;но этот шаг часто упускается из виду.

Answer 5

На самом деле, это не так уж и Важно, но Биг-Тета.