how - Complejidad del tiempo para Java ArrayList

java collections arraylist

Question

Encontré otras entradas para esta pregunta que tratan sobre métodos específicos, pero nada exhaustivo. Me gustaría verificar mi propia comprensión de los métodos más utilizados de esta estructura de datos:

O (1) - Tiempo constante:

isEmpty()
add(x)
add(x, i)
set(x, i)
size()
get(i)
remove(i)

O (N) - Tiempo lineal:

indexof(x)
clear()
remove(x)
remove(i)

¿Es esto correcto? Gracias por tu ayuda.

Answer 1

El mejor recurso es directamente de la API oficial :

Las operaciones size, isEmpty, get, set, iterator y listIterator se ejecutan en tiempo constante. La operación de adición se ejecuta en tiempo constante amortizado, es decir, agregar n elementos requiere O (n) tiempo. Todas las otras operaciones se ejecutan en tiempo lineal (aproximadamente hablando). El factor constante es bajo comparado con el de la implementación LinkedList.