迭代数组列表的时间复杂度

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实现了ArrayList使用分摊的数组.这意味着在数组末尾插入时,算法只需要花费Amortized O(1).或者你可以说O(1)

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

另一个参考:

动态数组

附加说明1:

如果在阵列末尾插入的复杂性是O(N),那么总复杂度O(N^2)不是O(2*N),正如其他答案所说的那样.因为插入的总复杂性将是:1 + 2 + 3 + ...+ n = n*(n+1)/2

附加说明2:

正如官方文件所述:

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

附加说明3:

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

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);
    }

正如源代码所说,当程序添加使数组大小大于当前容量的元素时,Array将会增长.增长阵列的新大小将是:

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

这是一个插入的技巧 amortized O(1)

Answer 2

Big-O 和类似的符号是时间复杂度的渐近界限。它们丢弃数字系数并用于估计作为输入大小的函数的运行时间。

所以，，，2*n等等3*n。分别表示为O(n)、 、2*nlog(n)、3*nlog(n)等。表示为O(nlog(n)).

由于在本例中 add() 操作仅插入一个元素，因此其运行时间大约为 ，(some small constant)k*1总运行时间为(some constant)j*(n+some constant(k))，换句话说j*n， 或O(n)。

在这种情况下以及所有类似的情况下，任何常数k乘以n都将表示为O(n)意味着运行时间随输入 ArrayList 的大小线性变化。