Array dinamico: differenze tra le versioni

fix +link
(spazi)
(fix +link)
a.dimensione ← a.dimensione + 1
 
Man mano che gli ''n'' elementi vengono inseriti, le capacità formano una [[progressione geometrica]]. Espandere l'array di una qualsiasi proporzione costante assicura che l'inserimento di ''n'' elementi prende un tempo complessivo di [[Notazione O Grande|''O''(''n'')]], ciò significa che ogni inserimento prende un tempo costante [[AnaliziAnalisi ammortizzata|ammortizzato]]. Il
valore di questa proporzione ''a'' porta a un compromesso spazio-tempo: il tempo medio per l'operazione di inserimento è circa ''a''/(''a''-1), mentre il numero di celle perse è delimitata superiormente da (''a''-1)''n''. La scelta di ''a'' è indipendente dall'applicazione, ma un uso comune è ''a''=2.
 
Paragonati alle [[lista concatenata|liste concatenate]], gli array dinamici hanno un'indicizzazione più rapida (tempo costante contro tempo lineare) e tipicamente anche una più rapida iterazione grazie alla migliore località di riferimento; tuttavia, gli array dinamici richiedono un tempo lineare per inserire o cancellare su una locazione arbitraria, dal momento che tutti gli
elementi seguenti devono essere spostati, mentre le liste concatenato possono farlo in tempo costante. Questo svantaggio è mitigato dal [[buffer gap]] e dalla variante ''vettore graduato'' discusso nel paragrafo ''Varianti'' più
sotto. Inoltre, per una regione di memoria altamente [[Frammentazione (informatica)|frammentata]], può essere dispendiosa o impossibile trovare uno spazio contiguo per un grosso array dinamico, mentre le liste concatenate non richiedono che l'intera struttura dati sia memorizzata in maniera contigua.
 
== Varianti ==
ammortizzate nel tempo. In aggiunta, presentano una variante dove
l'allargamento e lo restringimento del buffer non sono solo
ammortizatiammortizzati ma nel caso peggiore in tempo costante.
 
Bagwell (2002)<ref> Fast Functional Lists, Hash-Lists, Deques and Variable
1 502

contributi