Array dinamico: differenze tra le versioni

Jump to navigation Jump to search
m
Bot: passaggio degli url da HTTP a HTTPS
m (Bot: Correzione di uno o più errori comuni)
m (Bot: passaggio degli url da HTTP a HTTPS)
ammortizzate su O(1) quando aggiunge una serie di oggetti alla fine dell'Hashed Array Tree.
 
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<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]</ref> ha presentato l'algoritmo [[VList]], il quale può essere adottato per implementare un array dinamico.
799 297

contributi

Menu di navigazione