Array dinamico: differenze tra le versioni

L'[[Hashed array tree]] (HAT) è un algoritmo di array dinamico inventato da Sitarski nel 1996.<ref name="sitarski96"> HATs: Hashed array trees.[http://www.ddj.com/architect/184409965?pgno=5 HATs: Hashed array trees]</ref> L'Hashed Array Tree perde una quantità di spazio di memorizzazione nell'ordine di n^1/2, dove n è il numero di elementi nell'[[array]]. L'algoritmo ha le prestazioni

In una relazione del 1999 <ref name="brodnik"> Resizable Arrays in Optimal Time and Space.[http://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.

Bagwell (2002)<ref>[http://citeseer.ist.psu.edu/bagwell02fast.html Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays.[http://citeseer.ist.psu.edu/bagwell02fast.html] </ref> ha presentato l'algoritmo [[VList]], il quale può essere adottato per implementare un array dinamico.

* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 17.4: Dynamic tables, pp.&nbsp;416–425.

* [{{cita web|http://www.nist.gov/dads/HTML/dynamicarray.html |NIST Dictionary of Algorithms and Data Structures: Dynamic array]}}