ArrayList indexOf是复杂度N吗？

Question

我在arraylist中有N个数字.为了得到这个indexOf,arraylist必须迭代最多N次,所以复杂性是O(N)正确的吗？

Answer 1

源Java API

是的,复杂性是O(N).

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

Answer 2

是的，它是O(n)，因为在最坏的情况下它需要迭代列表中的每个项目。

实现比这更好的唯一方法是为列表提供某种结构。最典型的例子是使用二分搜索在O(log n)时间内浏览排序列表。

Answer 3

对，那是正确的。该顺序基于最坏的情况。