Java关于Collections addAll方法的时间复杂度

来源：8-1 树形问题 Letter Combinations of a Phone Number

软件工程小白菜

2020-07-08

老师你好，我想问下addAll这个方法的时间复杂度是O(1)还是O(n)？

我看网上说list.addAll()是浅拷贝,只是将内存中的地址进行了拷贝,指向了原先list的末尾做了拼接。如果是这样那应该是O(1)的复杂度。但我实际进行实验时，发现这是一个O(n)的时间复杂度，相等于说A.addAll(B)，是将B中的所有元素一个个的添加到A中。

感谢老师解答！

写回答

1回答

liuyubobobo

2020-07-08

已采纳

是 O(n) 的。但这也是浅拷贝。

比如 B 中是一系列 Student 类的对象，addAll 只是将 B 中所有 Student 类对象的引用拷贝一份扔给 A，之后修改 A 中的某个对象，也会改变 B 中的相应对象。

继续加油！：）

软件工程小白菜

liuyubobobo

完全明白了！太感谢了！

2020-07-09

共6条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7408 学习 · 1150 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 2