Complejidad del tiempo para java ArrayList

Question

¿ArrayList es una matriz o una lista en java? ¿Cuál es la complejidad del tiempo para la operación get, es O(n) o O(1)?

Answer 1

Un ArrayList en Java es un List que está respaldado por un array.

El método get(index) es un funcionamiento de tiempo constante, O(1).

El código directamente de la biblioteca Java para ArrayList.get(index):

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

Básicamente, sólo se devuelve un valor directamente de la matriz de soporte. (RangeCheck(index)) también es tiempo constante)

Answer 2

Su implementación se realiza con una matriz y la operación get es O (1).

javadoc dice:

El tamaño, estaVacia, get, set, iterador, y las operaciones se ejecutan en ListIterator constante tiempo. La operación de agregar se ejecuta en tiempo constante amortizado, es decir, agregar n elementos requiere O (n) tiempo. Todas las demás operaciones se ejecutan en tiempo lineal (aproximadamente). El factor constante es bajo en comparación con para la implementación LinkedList.

Answer 3

Para ser pedante, es un List respaldado por una matriz. Y sí, la complejidad de tiempo para get() es O (1).

Answer 4

Como todos ya han señalado, las operaciones de lectura son de tiempo constante - O (1) pero las operaciones de escritura tienen el potencial de quedarse sin espacio en la matriz de respaldo, reasignación y una copia - de manera que se ejecuta en tiempo O (n), ya que el médico dice:

el tamaño, estaVacia, get, set, iterador, y operaciones ListIterator ejecuta en tiempo constante. La operación de agregar ejecuta en tiempo constante amortizado, es decir, añadiendo n elementos requiere O (n) tiempo. Todas las otras operaciones se ejecutan en tiempo lineal (aproximadamente). El factor constante es bajo en comparación con que para la implementación LinkedList .

En la práctica todo es O (1) después de algunas adiciones, ya que la matriz de respaldo se duplica cada vez que se agota su capacidad. Entonces, si la matriz comienza en 16, se llena, se reasigna a 32, luego a 64, 128, etc., por lo que escalan bien, pero GC puede golpear durante un realloc grande.

Answer 5

Una nota.

El método get(index) es una constante de tiempo, O(1)

Pero ese es el caso si se conoce el índice.Si tratamos de obtener el índice usando indexOf(something), eso costará O(n)