qual è il tempo di esecuzione per l'inserimento di un elemento in qualche indice di arrayList?

Question

Mi chiedevo qual è il tempo di esecuzione del metodo add(index,E) di java ArrayList. Secondo lo javadoc il tempo di esecuzione per l'operazione di aggiunta è ammortizzato O(1). Ma nella descrizione di add(index,E) lo dice.

Inserisce l'elemento specificato nella posizione specificata in questo elenco. Sposta l'elemento attualmente in quella posizione (se presente) e qualsiasi elemento successivo a a destra (ne aggiunge uno ai rispettivi indici).

Quindi sembra O(N). Mi stavo chiedendo per cosa dovremmo negoziare, se il tempo necessario per eseguire questa operazione era O(1). C'è qualche lavoro di ammortamento che può essere fatto per rendere questa operazione O(1) e sacrificare il tempo di esecuzione per qualche altra operazione?

Ho letto che java ArrayList è supportato da matrici, cambierebbe la struttura della struttura di aiuto?

Answer 1

ArrayList ha O (n) complessità temporale per indici arbitrari di add/remove, ma O (1) per l'operazione alla fine dell'elenco. La ricerca da a O (1) implica può essere una cosa come una struttura dati di backup con Hash Table con indice come chiave e elemento come valore. L'inserimento di nuovo richiederà O (n) tempo perché attiva un ridimensionamento.

Answer 2

Un'implementazione ingenua di un elenco supportato da array copia ogni elemento da spostare su un inserto come operazione separata. Fortunatamente, i byte da spostare sono tutti contigui in memoria e ogni sistema operativo fornisce supporto per la copia efficiente di blocchi di memoria di grandi dimensioni in un'unica operazione rapida.

Quindi l'inserimento nel mezzo di un array non è così brutto come si potrebbe pensare. Ovviamente, la modifica della struttura dei dati in un elenco collegato potrebbe rivelarsi più veloce se la tua applicazione ha il giusto tipo di modello di accesso.