Perché l'inserimento alla fine di un array dinamico O (1) mentre l'inserimento al centro è O (n)?

Question

Secondo l'articolo di Wikipedia su array dinamici , inserendo / eliminando alla fine del l'array è O (1) mentre l'inserimento / eliminazione dal centro è O (n). Perché esattamente quello?

Inoltre - se ho un array dinamico con 5 elementi e inserisco un nuovo elemento in posizione 6 l'operazione è O (n) mentre se uso la funzione per aggiungere alla fine dell'array è O (1) . Non è la stessa operazione supponendo che l'array non debba ridimensionare in entrambi i casi? Oppure l'aggiunta alla matrice dinamica inserisce davvero il nuovo elemento da qualche parte oltre alla posizione 6?

Grazie!

EDIT: Penso che la mia principale confusione sia la differenza tra l'inserimento alla fine dell'array e l'inserimento in una posizione specifica che è equivalente alla fine dell'array.

Suppongo che un puntatore all'indirizzo di memoria della fine dell'array sia tenuto a portata di mano ed è per questo che l'operazione di aggiunta è rapida. Al contrario, se specifico una posizione precisa (anche se è la fine dell'array) non saprà che l'inserimento in quella posizione equivale all'utilizzo dell'indirizzo di memoria di cui sopra quindi deve attraversare l'intero array, eh?

Answer 1

L'ordine di grandezza dipende interamente dal tipo di struttura dei dati della "matrice dinamica" in realtà è ("array dinamico" non è una struttura di dati strettamente definita, è più un risultato desiderato ottenuto impiegando una particolare struttura di dati). L'esempio che daresti sarebbe quello riflesso da una matrice dinamica ottenuta impiegando un elenco collegato. L'aggiunta alla fine potrebbe essere O (1) se la struttura dell'elenco mantiene un puntatore all'elemento finale. L'inserimento (indipendentemente dall'indice) richiederebbe l'attraversamento dell'elenco collegato, il che significa un'operazione per nodo fino all'indice desiderato.

Answer 2

Per inserire alla fine di un array, è sufficiente inserire l'elemento lì.

Per inserire nel mezzo di un array, è necessario spostare gli elementi dopo quello in alto di uno.

Per eliminare dalla fine di un array, è sufficiente ridurne il conteggio di uno.

Per eliminare dal centro devi fare e spostare gli altri elementi verso il basso.

È il spostamento che lo trasforma in O (n).

Answer 3

È abbastanza semplice:

L'inserimento nel mezzo implica lo spostamento di ogni elemento successivo di 1. Per inserire alla fine, se c'è spazio aggiuntivo riservato, l'elemento viene semplicemente memorizzato lì, ma in caso contrario viene assegnato nuovo spazio. Quindi questa operazione viene eseguita in tempo costante ammortizzato .

Answer 4

Aggiungendo all'ottimo riassunto di Adam Robinson: questa non è solo teoria. Ho visto un numero qualsiasi di situazioni in cui è stato costruito un array dinamico aggiungendo ripetutamente alla fine dell'array. Ciò si traduce in una prestazione (N ** 2) , poiché l'array deve essere ripetutamente allocato, costringendo ciascuno dei suoi membri a essere copiato nella nuova struttura dell'array. Le riassegnazioni possono avvenire solo su 1/10 delle operazioni di accodamento, ma questo è abbastanza grave ed è ancora o (N ** 2) in termini di prestazioni.

In STL, questa penalità di prestazione può essere evitata chiamando vector :: reserve (N) prima di scrivere nel vettore; ma questo passaggio è spesso trascurato.

Answer 5

In realtà, non è Big-O ma Big-Theta .