我正在通过我的计算机科学课程的练习考试。但是,我不确定下面的问题。
考虑四种不同的方法来重新调整基于数组的列表数据结构的大小。在每种情况下,当我们想要将一个项添加到数组的末尾但它已满时,我们创建一个新数组,然后将旧数组中的元素复制到新数组中。对于以下每个关于制作新数组有多大的选择,以big-O术语给出添加到列表末尾的复杂性:
(i)将数组大小增加1项。
(ii)将阵列大小增加100个项目。
(iii)数组大小加倍。
(iv)阵列大小的三倍。
既然你无论如何调用相同的System.arraycopy()
方法到达时间,那么每个方法的复杂性是否相同?
既然你无论如何调用相同的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“你会找到例子。)