La complessità del tempo per java ArrayList

Question

È ArrayList un array o un elenco in java? qual è la complessità temporale per l'operazione get, è O(n) o O(1)?

Answer 1

Un ArrayList in Java è un List supportato da un array.

Il metodo get(index) è un tempo costante, O(1), operazione.

Il codice direttamente dalla libreria Java per ArrayList.get(index):

public E get(int index) { 
    RangeCheck(index); 
    return (E) elementData[index]; 
} 

Fondamentalmente, solo restituisce un valore direttamente fuori della matrice di supporto. (RangeCheck(index)) è anche tempo costante)

Answer 2

L'implementazione viene eseguita con un array e l'operazione get è O (1).

javadoc dice:

Le dimensioni, EVuota, ottenere, insieme, iteratore, e le operazioni di ListIterator eseguito in costante tempo. L'operazione di aggiunta viene eseguita in tempo costante ammortizzato, ovvero, l'aggiunta di n elementi richiede tempo O (n). Tutte le altre operazioni vengono eseguite in tempo lineare (approssimativamente). Il fattore costante è basso rispetto a a quello per l'implementazione di LinkedList.

Answer 3

essere pedanti, si tratta di un List sostenuta da un array. E sì, la complessità temporale per get() è O (1).

Answer 4

Come tutti hanno già sottolineato, le operazioni di lettura sono costanti - O (1) ma le operazioni di scrittura hanno il potenziale per esaurire lo spazio nel backing array, la riassegnazione e una copia - in modo che viene eseguito in O (n), come il dottore dice:

le dimensioni, EVuota, ottenere, set, iteratore, e le operazioni ListIterator eseguito in tempo costante. L'operazione di aggiunta esegue in tempo costante ammortizzato, ovvero aggiungendo n elementi richiede O (n) tempo. Tutte le altre operazioni vengono eseguite nel tempo lineare (in parole povere). Il fattore costante è basso rispetto a che per l'implementazione di LinkedList .

In pratica tutto è O (1) dopo alcuni aggiunti, poiché l'array di supporto viene raddoppiato ogni volta che viene esaurita la capacità. Quindi, se l'array inizia a 16, si riempie, viene riallocato a 32, quindi a 64, 128, ecc. In modo che risulti corretto, ma GC può essere attivato durante un grande riallocamento.

Answer 5

Solo una nota.

Il metodo get(index) è una costante di tempo, O(1)

Ma questo è il caso, se conosciamo l'indice.Se proviamo a ottenere l'indice usando , questo costerà O(n)