ArrayList 的 indexOf 复杂度是 N 吗? [英] Is ArrayList indexOf complexity N?

问题描述

我在数组列表中有 N 个数字.要获得 indexOf，arraylist 必须最多迭代 N 次，所以复杂度是 O(N)，对吗?

I have N numbers in arraylist. To get the indexOf, arraylist will have to iterate maximum N times, so complexity is O(N), is that correct?

推荐答案

Source Java API

是的，复杂度是 O(N).

Yes,Complexity is O(N).

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

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

这篇关于ArrayList 的 indexOf 复杂度是 N 吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！