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

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)。这一点不太确定。

- Chicken Crimpy

---

这段话的意思是：它的时间复杂度为O(n) + O(n)，即O(2n)，但你可以忽略2（因为相对于输入来说是一个常数），并说它的时间复杂度是O(n)。 - Elliott Frisch

@ElliottFrisch，那不是真的。在Java中插入ArrayList的最后一个元素不是O(n)。请看我的回答。 - hqt

我不明白为什么有争议。难道不是所有的答案都说了同样的事情吗，就是它是O(n)？获取项的时间复杂度为O(n)，添加新项的时间复杂度也为O(n)。 - fgb

@fgb，争议在于缺乏清晰和准确性。有一个循环使得这个算法的时间复杂度为O(n)。之后是一些常数时间的操作，数量不是2。他们不应该像@Elliott在之前的评论中那样说。将O(n) + O(n)简单相加是错误和不准确的，因为第二个复杂度是嵌套在第一个内部的（也就是说，不是简单相加，而是常数项的乘积）；它是cn = O(n)。 - ChiefTwoPencils

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - ChiefTwoPencils

Answer 1

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

因此，您的代码的复杂度为：O(n) * 摊销 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);

这是一种使插入的时间复杂度为均摊O(1)的技巧。

- hqt

---

为什么ArrayList实现不被认为是低效的，这是一个非常精确的问题。 - ChiefTwoPencils

Answer 2

您正在进行一次迭代，这是O(n)的。

您还在向ArrayList添加项目，它是O(1)(分摊)。

获取索引也是O(1)。

因此，您正在进行O(n)次O(1)操作，这将是O(n)。

- SpiXel

Answer 3

大O符号和类似的符号是时间复杂度的渐进上界。它们舍弃了数值系数，并用输入大小的函数来估计运行时间。

因此，2*n，3*n等表示为O(n)，2*nlog(n)，3*nlog(n)等表示为O(nlog(n))。

由于在这种情况下add()操作仅插入一个元素，其运行时间约为(某个小常数)k*1，总运行时间为(某个常数)j*(n+某个常数(k))，换句话说是j*n或O(n)。

在这种情况和所有类似情况中，任何常数k乘以n都表示为O(n)，这意味着运行时间与输入ArrayList的大小成线性关系。

- brijs

Answer 4

对于遍历数组列表，时间复杂度为O(n)，其中n是列表的大小。

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

而使用add()添加值时，值会被添加到末尾，因此时间复杂度为O(1)。

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

- Vijai