arraylist 调整大小的时间复杂度 java

Question

我知道 arraylist 的默认大小是 10，并且 arraylist 会自动扩展以添加额外的项目。

resizing/expansion的时间复杂度是多少？

它是否类似于普通数组，其中的项目必须在 O(n) 时间内复制到新的更大的数组中？

Answer 1

概述

调整大小的时间复杂度为O(n)。

它将创建一个容量加倍的新数组，并将每个元素从原始数组复制到新数组中。这需要 完整迭代 。请注意，这可以由 JVM 在内部进行优化。

摊销

不需要经常调整大小。特别是不是每个 add 电话。因此，为什么它将内部容量加倍。这为一大堆后续 add-调用提供了空间。

更正式地说，这会产生 add 的摊销复杂度 O(1)，尽管它的常规复杂度将 O(n) 受限于resize.

详情

你可以看到这个here（OpenJDK 17）的来源：

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (/* ... */) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        // ...
    }
}

首选增长是oldCapacity >> 1，即容量翻倍。实际影响性能并给你 O(n) 的部分是 Arrays.copyOf(...).

这个方法主要是从this helper调用的：

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

主入口点使用add(E):

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

arraylist 调整大小的时间复杂度 java

time complexity for arraylist resizing java

java

arraylist

time-complexity

概述

摊销

详情