java - 遍历数组列表的时间复杂度

Question

我有一个循环访问的数组列表。在每次迭代中，我调用 get() 来获取一个元素，如果该项目满足某个条件，则使用 add()

将其添加到新的数组列表中>

List<Item> items = new ArrayList<Item>();
List<Item> lessItems = new ArrayList<Item>();
for(int index = 0; index < items.size(); index++){
    Item toCheck = items.get(i);
    if(toCheck meets some condition){
        lessItems.add(toCheck);
    }
}

我不确定这里的时间复杂度是多少。我在所有项目上调用 get()，所以这是 O(n)。然后我还可能对所有项目调用 add()，所以还有另一个 O(n)。不太确定这一点。

Answer 1

1. 迭代 items 列表的第一个循环:复杂度为 O(n)
2. 将每个项目插入到列表的末尾 lessItems:在普通数组中，正如其他人所说，它将是 O(n)。但是 Java 使用 amortized array 实现 ArrayList .这意味着在数组末尾插入时，算法仅花费 Amortized O(1)。或者你可以说 O(1)

所以你的代码的复杂度是:O(n) * amortized O(1)。简而言之就是O(n)

另一个引用:

dynamic array

补充说明1:

如果在数组末尾插入的复杂度是O(N)，那么总的复杂度是O(N^2)，而不是O(2*N )正如其他答案所说。因为插入的总复杂度为:1 + 2 + 3 + ...+ n = n*(n+1)/2

附加说明 2:

作为official document状态:

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.

补充说明3:

这里是我从官方java源代码中获取的grow方法的逻辑:

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

正如源代码所说，当程序添加使数组大小大于当前容量的元素时，数组将增长。增长数组的新大小将是:

int newCapacity = oldCapacity + (oldCapacity >> 1);

这是一个使插入摊销O(1)

的技巧