Array dinamico: differenze tra le versioni

m
Bot: fix citazione web (v. discussione)
m (fix)
m (Bot: fix citazione web (v. discussione))
Rank-Based Sequences.[http://citeseer.ist.psu.edu/519744.html]</ref> ha presentato un algoritmo di array dinamici chiamato ''Tiered Vectors'' (vettore graduato) che consente prestazioni O(n<sup<1/2</sup>) per preservare l'inserimento o la rimozione dal mezzo dell'array.
 
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<sup>1/2</sup>, dove n è il numero di elementi nell'[[array]]. L'algoritmo ha le prestazioni
ammortizzate su O(1) quando aggiunge una serie di oggetti alla fine dell'Hashed Array Tree.
 
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<sup>1/2</sup> 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.
 
== Supporto nei linguaggio ==
 
==Bibliografia==
* [[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.
 
==Voci correlate==
 
== Collegamenti esterni ==
* [{{cita web|http://www.nist.gov/dads/HTML/dynamicarray.html |NIST Dictionary of Algorithms and Data Structures: Dynamic array]}}
* [http://www.bsdua.org/libbsdua.html#vpool VPOOL] - C language implementation of dynamic array.
 
3 185 531

contributi