C ++ tem std :: vector e Java tem ArrayList, e muitas outras linguagens têm sua própria forma de matriz alocada dinamicamente. Quando um array dinâmico fica sem espaço, ele é realocado em uma área maior e os valores antigos são copiados para o novo array. Uma questão central para o desempenho de um array é a rapidez com que o array cresce em tamanho. Se você sempre crescer grande o suficiente para caber o impulso atual, você vai acabar realocando cada vez. Portanto, faz sentido duplicar o tamanho do array ou multiplicá-lo por 1,5x.

Existe um fator de crescimento ideal? 2x 1,5x? Por ideal quero dizer matematicamente justificado, melhor desempenho de equilíbrio e memória desperdiçada. Eu percebo que teoricamente, dado que seu aplicativo poderia ter qualquer distribuição potencial de pushes, isso é um pouco dependente de aplicativos. Mas estou curioso para saber se há um valor "geralmente" melhor ou considerado melhor dentro de alguma restrição rigorosa.

Ouvi dizer que há um artigo sobre isso em algum lugar, mas não consegui encontrá-lo.