Java ArrayList 的时间复杂度

Question

我在Stack Overflow上找到了其他与此问题有关的条目，但没有综合性的内容。我想确认一下我对这种数据结构最常用的方法的理解：

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)

这正确吗？感谢你的帮助。

- dvanaria

---

如果我理解你的问题，我认为应该将add(x, i)归入第二组。 - user468311

remove(i) 的时间复杂度既可以是 O(1)，也可以是 O(N)。 - Bala R

remove(i)在最坏情况和平均情况下都是O(N)，在最佳情况下（即仅删除最后一个元素）为O(1)。 - Haroldo_OK

Answer 1

最好的资源来自官方API：

大小，isEmpty，get，set，iterator和listIterator操作在常数时间内运行。添加操作以摊销常数时间运行，即添加n个元素需要O（n）时间。所有其他操作都在线性时间内运行（粗略地说）。与LinkedList实现相比，常数因子较低。

- brian_d

---

确实有帮助，谢谢。我现在明白为什么add(x, i)可能需要将数组中的许多元素向上移动以插入新元素，因此在最坏情况下运行时间是线性的。remove(i)也是如此。摊销常数时间和普通常数时间有什么区别？ - dvanaria

@dvanaria，有关摊销常数时间的一些好答案在此帖子中https://dev59.com/OXVC5IYBdhLWcg3wtzyt。基本上，平均时间是恒定的，但每个单独的操作可能需要更多的时间 - 在这种情况下，当底层数组需要调整大小时。 - brian_d