Array dinamico: differenze tra le versioni

In una relazione del 1999 <ref name="brodnik">[httphttps://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf Resizable Arrays in Optimal Time and Space]</ref>, Brodnik et al. descrivono una struttura dati array graduato dinamico, il quale perde solo n^1/2 di spazio per ''n'' elementi in qualsiasi punto nel tempo, e provano un limite più basso mostrando che gli array dinamici devono perdere questo spazio in più se le operazioni sono di rimanere ammortizzate nel tempo. In aggiunta, presentano una variante dove l'allargamento e lo restringimento del buffer non sono solo ammortizzati ma nel caso peggiore in tempo costante.