Un tableau dynamique reçoit 1000 valeurs une par une. Sa capacité initiale est de 2, et deux stratégies d'agrandissement sont possibles.
Objectif
Comparer le nombre d'agrandissements, puis le travail de recopie qu'ils représentent.
Les deux stratégies
capacite = capacite * 2;
valeurs = realloc(valeurs, capacite * sizeof(int));
capacite = capacite + 1;
valeurs = realloc(valeurs, capacite * sizeof(int));
Ce que ces nombres représentent
Chaque agrandissement recopie le bloc entier. La seconde stratégie recopie donc successivement 2, 3, 4 éléments et ainsi de suite jusqu'à 999, soit environ la moitié du carré du nombre d'éléments. En doublant, le total des recopies reste proportionnel au nombre d'éléments, et non à son carré.