Java ArrayList的时间复杂度

Question

我发现这个问题的其他条目涉及具体方法,但没有全面的.我想验证自己对这种数据结构中最常用的方法的理解:

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)

它是否正确？谢谢你的帮助.

Answer 1

最好的资源来自官方API:

size,isEmpty,get,set,iterator和listIterator操作以恒定时间运行.添加操作以分摊的常量时间运行,即添加n个元素需要O(n)时间.所有其他操作都以线性时间运行(粗略地说).与LinkedList实现相比,常数因子较低.