Big-O копирующих элементов в динамическом массиве

Question

Итак, я хотел бы спросить об асимптотическом росте копирующих элементов в алгоритме динамических массивов.

В алгоритме динамических массивов размер массива удваивается каждый раз, когда он заполняется, и новый элемент должен быть добавлен. Когда массив заполнен, он содержит N/2 элемента, а после его удвоения размер нового массива равен 2N. Затем следующий элемент вставляется после скопированных объектов/значений.

Я полагал, что Big-O для количества скопированных элементов будет O (N/2), но должен ли я также учитывать моменты, когда массив был удвоен?

Просто для того, чтобы быть предельно ясным, это проблема, которую назначил мой инструктор, и я думал об этом, но в настоящее время я не уверен, если/как учитывать количество раз, когда массив был удвоен , учитывая только массив размера N.

Answer 1

Я полагал, что Big-Oh для количества копируемых элементов будет O (N/2), но нужно ли мне также учитывать время, когда массив был удвоен?

Возможно, что вы ищете различие между сложностью операции и amortized complexity.

В частности, наихудший временная сложность вставки в динамическом массиве, действительно O(N), но амортизируется сложность O(1) (поскольку для N инсерции в большинстве 2*N элементов копируются).

Answer 2

Пусть N - количество элементов, добавляемых к массиву. Если массив начинает пуст с нулевым размером, для которого элементы необходимо изменить размер массива? при условии, что он начинается с емкости 1:

size | 0 1 2 3 4 5 6 7 8 9 ... 16 17 
capacity| 0 1 2 4 8  16 ... 32 

поэтому массив изменен в размере всего журнала (N) +1 раз. Общее число элементов скопированных, хотя это:

 size | 0 1 2 3 4 5 6 7 8 9 ... 16 17 
    capacity| 0 1 2 4 8  16 ... 32 
total copied| 0 0 1 3 7  15 ... 31 ... 

Таким образом, общее число копий составляет ~ 2 * N, который является O (N)

Однако обратите внимание, что это в случае, если вы вставите N элементы один за другим в первоначально пустом растущем массиве. Вот почему типичная реализация позволяет указать начальную емкость, поэтому, если у вас есть достаточная догадка о том, сколько элементов вы вставляете, вы можете начать с емкости! = 0.