Сложность времени для Java ArrayList
Я нашел другие записи для этого вопроса, которые касались конкретных методов, но ничего исчерпывающего. Я хотел бы проверить свое собственное понимание наиболее часто используемых методов этой структуры данных:
O (1) - Постоянное время:
isEmpty()
add(x)
add(x, i)
set(x, i)
size()
get(i)
remove(i)
O (N) - Линейное время:
indexof(x)
clear()
remove(x)
remove(i)
Это правильно? Благодарим за помощь.
Ответы
Ответ 1
Лучший ресурс прямо из официального официального API:
Операции size, isEmpty, get, set, iterator и listIterator выполняются в постоянное время. Операция add работает в режиме амортизированного постоянного времени, то есть для добавления n элементов требуется время O (n). Все остальные операции выполняются в линейном времени (грубо говоря). Постоянный коэффициент невысок по сравнению с константой для реализации LinkedList.
