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

Question

正如标题所说，我想知道 ArrayList 是。

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)

Answer 3

如果您查看 ArrayList 的源代码并检查其 contains 方法，它看起来如下所示：

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

contains 将检查委托给 indexOf方法。因此，如果我们检查 indexOf 实现，它如下所示：

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

从代码中可以看出，为了找到给定元素的索引，在最坏的情况下，必须迭代整个阵列。随着数组大小的增加，元素的搜索时间也会增加。因此，contains方法的时间复杂度为O(n)，其中n是列表中元素的数量。

Answer 4

它的O(n)。 contains(Object o) 在 indexOf() 上实现，需要 O(n)。因此 contains(Object o) 的复杂性是防御性的 O(n)

如果您需要的话，这里还有其他一些：

add() - O(1)
add(index, element) – O(n)
get() – O(1)
set() – O(1)
remove() –  (n)
indexOf()` – O(n)