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

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：

这是我从官方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);

这是一个技巧，让插入变得

amortized O(1)

Answer 2

您正在进行一次迭代，其时间复杂度为 O(n)。

您还向 ArrayList 添加项目，其时间复杂度为 O(1) (Amortized)

获取索引也是 O(1)。

所以你执行了 O(n) 次，O(1) 的操作，这将是 O(n)。

Answer 3

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 的大小线性变化。

Answer 4

对于数组列表的迭代，时间复杂度为O(n)。 n 将是列表的大小。

使用 get() 获取值，时间复杂度为 O(1)，可以使用索引在数组列表中进行随机访问。

使用 add() 添加值时，值会在最后添加，因此时间复杂度为 O(1)。

此操作的时间复杂度将为 O(n)。

Answer 5

检查此技巧以将数组迭代（查找整数）减少到恒定时间：https://research.swtch.com/sparse