Почему динамические массивы c имеют удвоенный размер при нехватке места?

Question

Я новичок в амортизированном анализе. Я заметил, что обычной практикой для динамических c массивов является удвоение их размеров при нехватке места. Есть ли конкретная c причина, по которой мы решили удвоить размер? Почему не тройной или четырехместный? Есть ли конкретное c объяснение выбора удвоения с использованием амортизированного анализа? Или выбор произвольный?

Answer 1

Увеличение размера массива путем масштабирования на любой постоянный коэффициент будет достаточным, чтобы время выполнения было равно O (n). Чтобы увидеть это, обратите внимание, что если конечный размер массива заканчивается на n и мы масштабируемся с коэффициентом m на каждом шаге, то общая работа, выполненная при увеличении массива, будет

1 + m + m ² + ... + m ^{1 + log _m n} .

Чтобы понять, почему это так, обратите внимание, что ( если массив начинается с размера один), то массив будет расти с размерами 1, m, m ² , ..., пока не достигнет размера n. Этот последний шаг роста происходит, когда m ^k = n, что происходит, когда k = log _m n. Факторинг в еще одном шаге роста для превышения n здесь равен +1.

Приведенная выше сумма является суммой геометрии серии c и суммой

(м ^{2 + log _m n} - 1) / (м - 1)

= (м ² n - 1) / (м - 1 )

≤ n · (м ² / (м - 1))

Таким образом, в основном любой показатель больше одного работает, но старший коэффициент зависит от какой выбор м мы выберем. Для больших m этот коэффициент приблизительно равен m, и в итоге мы тратим много сил и пространства на выращивание массива. Если m становится ближе к единице, знаменатель становится все больше и больше, и это вызывает больше беспокойства.

Выбор m = 2 дает ведущий коэффициент 4, который довольно низок. Комплектация 1,5 дает ведущий коэффициент 4,5. Это выше, но не намного. Однако, выбор 1.5 имеет некоторые другие преимущества:

• Выделенный массив, если мы продолжаем увеличивать массив, никогда не будет больше, чем на 50% больше, чем мы имели прежде. Это уменьшает накладные расходы структуры данных по сравнению с удвоением.
• Если нам нужно увеличить массив, сумма размеров предыдущих массивов превышает размер нового массива (проверьте это - степени двух донов). не делай этого). Это повышает вероятность того, что распределитель памяти может перезапускать пространство из старых сброшенных массивов, чтобы соответствовать новому массиву.
• Умножение на 1,5 может быть выполнено путем вычисления size + (size >> 1), что является чрезвычайно дешевым для процессора по сравнению с умножить.

Надеюсь, это поможет!

Answer 2

Как вы могли найти в этом посте , амортизируемая сложность массива динамического c равна O(1). Если вы посмотрите анализ, вы обнаружите, что нет никакой разницы в асимптотике c сложности времени, если вы измените 2 на 3 или 4 или даже на любую другую константу (большую, чем 1) число, даже десятичные дроби. Например, в Microsoft Visual C ++ с использованием 1.5 в качестве фактора роста [1] (см. Больше примеров в приведенной ссылке).

Следовательно, 2 не является конкретным фактор роста здесь и другие факторы используют также. Более того, как уже упоминалось здесь :

Однако во многих учебниках для простоты и анализа используется символ = 2.