Почему динамический массив всегда удваивается с коэффициентом 2?

Question

Мне было интересно, как можно определить коэффициент изменения размера, по которому изменяется динамический массив? В википедии и еще где я всегда видел, как количество элементов увеличивается в 2 раза? Почему 2? Почему не 3? как решить этот фактор? Если это зависит от языка, я хотел бы знать это для Java.

Answer 1

Цитата из Википедия :

При вставке n элементов емкости образуют геометрическую прогрессию. Расширение массива на любую постоянную пропорцию гарантирует, что вставка n элементов занимает в целом O (n) времени, а это означает, что каждая вставка занимает амортизированное постоянное время. Значение этой пропорции a приводит к компромиссу между пространством и временем: среднее время на операцию вставки составляет около a / (a-1), в то время как количество потерянных ячеек ограничено сверху (a-1) n. Выбор a зависит от библиотеки или приложения: a = 3/2 1 и a = 2 [требуется цитирование] обычно используется.

Видимо, это хороший компромисс между временем процессора и потерей памяти. Я думаю, что «лучшее» значение зависит от того, что делает ваше приложение.

Answer 2

Вы бы потратили больше места, чем фактически используете?
Если нет, коэффициент должен быть меньше или равен 2.
Если вы хотите, чтобы оно было целым числом, чтобы с ним было легко работать, есть только один выбор.

Answer 3

На самом деле в Java ArrayList формула для расчета новой емкости после изменения размера:

newCapacity = (oldCapacity * 3)/2 + 1;

Это означает примерно 1,5 фактора.

О причине этого числа я не знаю, но надеюсь, что кто-то провел статистический анализ и обнаружил, что это хороший компромисс между пространством и вычислительными затратами.