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

Question

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

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

Спасибо!

РЕДАКТИРОВАТЬ: Я думаю, что моя основная путаница заключается в разнице между вставкой в ​​конце массива и вставкой в ​​определенной позиции, которая эквивалентна концу массива.

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

Answer 1

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

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

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

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

Это смещение , которое превращает его в O (n).

Answer 2

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

Answer 3

Все довольно просто:

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

Answer 4

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

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

Answer 5

На самом деле, это не Big-O, а Big-Theta .