java - 添加到完整 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 元素的数组比 需要更多的空间和时间>N + 1 个元素。但您只会将 N 个元素复制到数组中。)

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

(值得注意的是，2 会比 1 更快，即使它们具有相同的复杂性。)

对此的典型分析包括计算出类似这样的事情的总成本:

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

<小时/>

^{(提示:分析可能会在您推荐的“数据结构与算法”教科书或您的讲义中作为示例给出。如果是这样，这就是您应该复习的内容(在进行练习考试之前!)如果没有，请 Google 搜索“complexity amortized arraylist”，您会找到示例。)}