algorithm - 复杂性和大 O 表示法

Question

ArrayList<Integer>假设项目 (an ) 有足够的未使用空间以至于它永远不需要重新调整大小，那么以下两种算法的最坏情况时间复杂度是多少？我最初的猜测是 A 会运行得更慢，因为它必须将每个元素移到 index 处添加新元素[0]。我认为 B 是O(N^2)最坏的情况，但我不确定。

一个。

for (int i = 0; i < N; i++)
    items.add(0, new Integer(i));

和 B。

for (int i = 0; i < N; i++)
    items.add(new Integer(i));

Answer 1

If your question is about java, then first version is slower and has complexity O(N^2)for the very reason you mention, while B has complexity O(N).

Answer 2

通过假设items数组足够大，实现 A 可以实现为：

for (int i = 0; i < n; i++) {
    for (int j = items.size; j > 0; j++) {
        items[j] = items[j-1]; 
    }
    items[0] = i;
}

在这种情况下执行的操作总数（假设m是items列表的初始大小）将是：

这具有复杂性O(n ² )

另一方面，选项 B 可以实现为

for (int i = 0; i < n; i++) {
    items[items.size] = i;
    items.size++;
}

在这种情况下执行的操作数将是

这具有复杂性O(n)

Answer 3

in A, you must shift all of the items to the right one in the internal array of the array list for each insertion. This will be O(n^2) to complete the operation. In the second case, no shifting is needed so it will be O(n). In A, you are doing tons of unnecessary and expensive work.

I am assuming, as you had stipulated, that the internal array is not resized.