如何在big-o中确定添加到完整arraylist时的程序复杂性?

既然不管怎样都调用同一个System.ArrayCopy()方法到达时间,那么每个方法的复杂度不是都一样吗?

是的,没有。

是的-当你真的复制时,复制的成本在任何情况下都是相似的。

(如果包括分配和初始化数组的成本,它们就不完全相同。分配和初始化 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());
}

^{(提示:这个分析可以在你推荐的“数据结构和算法”教科书或你的课堂讲稿中作为一个例子。如果是的话,那就是你应该复习的内容(在做练习考试之前!)如果不是的话,谷歌的“复杂度摊销数组列表”和你会发现的例子。)}