在对象的ArrayList中包含(Object o)的时间复杂度

Question

正如标题所说,我想知道ArrayList的contains()方法的时间复杂度是多少.

Answer 1

O(n)

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

http://download.oracle.com/javase/6/docs/api/java/util/ArrayList.html

Answer 2

它是ArrayList的O(n)