添加到完整的 ArrayList 时如何确定 Big-O 中的程序复杂性？

Question

我正在参加计算机科学 class 的模拟考试。但是，我不确定下面的问题。

Consider four different approaches to re-sizing an array-based list data-structure. In each case, when we want to add() an item to the end of the array, but it is full, we create a new array and then copy elements from the old one into the new one. For each of the following choices about how big to make the new array, give the resulting complexity of adding to the end of the list, in big-O terms:

(i) increase array size by 1 item.

(ii) Increase array size by 100 items.

(iii) Double the array size.

(iv) Triple the array size.

既然您调用相同的 System.arraycopy() 方法到达时间，那么每个方法的复杂度不会相同吗？

Answer 1

Since you call the same System.arraycopy() method reach time regardless, wouldn't the complexity be the same for each?

是，也不是。

是的 - 当您实际进行复制时，复制的成本在所有情况下都是相似的。

（如果包括分配和初始化数组的成本，它们并不完全相同。分配和初始化 2 * N 个元素的数组比 space 和时间更长=12=] 个元素。但是你只会将 N 个元素复制到数组中。）

否 - 不同的策略导致数组复制发生的次数不同。如果您对一系列操作进行完整的复杂性分析，您会发现选项 3 和 4 的复杂性与 1 和 2 不同。

（值得注意的是，2 将比 1 快，即使它们具有相同的复杂度。）

对此的典型分析涉及计算出总成本，如下所示：

List<Object> list = new ArrayList<>();
for (int i = 0; i < N; i++) {
    list.add(new Object());
}

^{（提示：您推荐的 "data structures and algorithms" 教科书或您的讲义中可能会给出分析作为示例。如果是这样，那是您应该修改的内容（在练习之前考试！）如果没有，Google for "complexity amortized arraylist" 你会找到例子。）}

添加到完整的 ArrayList 时如何确定 Big-O 中的程序复杂性？

How to determine program complexity in Big-O when adding to a full ArrayList?

java

arrays

complexity-theory

big-o

arraylist