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

问题描述 投票:0回答:1

我正在通过我的计算机科学课程的练习考试。但是,我不确定下面的问题。

考虑四种不同的方法来重新调整基于数组的列表数据结构的大小。在每种情况下,当我们想要将一个项添加到数组的末尾但它已满时,我们创建一个新数组,然后将旧数组中的元素复制到新数组中。对于以下每个关于制作新数组有多大的选择,以big-O术语给出添加到列表末尾的复杂性:

(i)将数组大小增加1项。

(ii)将阵列大小增加100个项目。

(iii)数组大小加倍。

(iv)阵列大小的三倍。

既然你无论如何调用相同的System.arraycopy()方法到达时间,那么每个方法的复杂性是否相同?

java arrays arraylist big-o complexity-theory
1个回答
3
投票

既然你无论如何调用相同的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());
}

(提示:分析可以作为您推荐的“数据结构和算法”教科书或您的讲义中的一个例子。如果是这样,那就是您应该修改的内容(在进行练习考试之前!)如果没有,Google for“复杂性摊销arraylist“你会找到例子。)

© www.soinside.com 2019 - 2024. All rights reserved.