java - 对象 ArrayList 中 contains(Object o) 的时间复杂度

Question

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

Answer 1

O(n)

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.

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