Посмотрим, как распределяется память в массиве, при объявлении массива размера n для этого выделяется некий непрерывный блок памяти.
например, когда массив размером 5 объявил, что каждая единица занимает 2 байта, а непрерывный блок памяти, если он начинается с 1000, тогда выделенная память находится в диапазоне от 1000 до 1010.
Здесь непрерывная память после выделения следующей памяти используется другими переменными или любыми другими данными. поэтому следующее 1011 место занято. когда мы пытаемся вставить новый элемент в этот массив. ЦП находит память, которая в два раза больше памяти текущего массива.
предыдущий массив: размер = 5 память = 10 байт
текущий массив: размер = 10 память = 20 байт
мы не можем точно сказать, что он в 2 раза больше, но примерно в 1,5-2 раза.
После нахождения новой памяти обычно в 2 раза больше и указывает ту же переменную на вновь сформированное пространство памяти. Теперь он берет все элементы из предыдущей ячейки памяти и вставляет их в новую ячейку памяти [это означает, что он вставляет все n элементов из предыдущего массива] и вставляет их в новый массив.
После того, как элемент n+1 будет вставлен в (n+1)-е место вновь сформированного массива.
Время, затрачиваемое на вставку (n+1)-го элемента, составляет:
1. Поиск места в памяти
2. Вставка всех предыдущих n элементов занимает время O(n)
3.n+ Вставка 1 элемента занимает O (1).
Всего для вставки n+1 элемента в динамический массив размера n равно n+1
Например, у нас есть массив A[] размера 5:
вставка 0-го элемента A[0]=10 → 1
вставка 1-го элемента A[1]=20 → 1
вставка 2-го элемента элемент A[2]=30 → 1
вставка 3-го элемента A[3]=40 → 1
вставка 4-го элемента A[4]=50 → 1
так что всего пять элементов время вставки составляет O (5).
Теперь, если мы попытаемся вставить 60 в массив, ЦП найдет удвоенный текущий размер и изменит ссылочный адрес A[] размера 10 на новый адрес.
После вставки всех элементов 10,20,30,40,50 в новый массив требуется время O(5). Теперь он вставляет 60 в A[5], и время, затраченное здесь, составляет O(5) + O(1), потому что для вставки 60 ЦП должен найти новую память, вставить старые и 60.
Но с этого момента и до A[9] вставка новых элементов занимает O(1).
То же самое для каждого (n+1)-го элемента при вставке в массив размера n.
Поэтому всякий раз, когда мы пытаемся вставить (n+1)-й элемент в массив размера n. В памяти формируется новое пространство массива, размер которого в 1,5-2 раза превышает размер предыдущего массива, и в него вставляется новый элемент. предыдущий объем памяти уничтожается.
