Java中的时间复杂度

Question

对于ArrayList Java API中的add方法，它的运行时间为平均常数时间，也就是添加n个元素需要O(n)的时间。

我想知道，使用LinkedList的add方法时，时间复杂度是否相同，即线性时间？

- FranXh

---

可能是Constant Amortized Time的重复问题。 - Brian Roach

Answer 1

这取决于你添加的位置。例如，如果在ArrayList中向列表开头添加元素，实现将不得不每次都移动所有项目，因此添加n个元素将运行在二次时间内。

对于链表也是类似的，JDK中的实现会保留对头部和尾部的指针。如果你一直将元素追加到尾部，或者在头部前面插入，操作将以线性时间运行n个元素。如果你在不同的地方插入，则实现将不得不在链表中搜索正确的位置，这可能会给你更糟糕的运行时间。再一次强调，这取决于插入位置;如果你在列表中间插入，最大数量的元素必须被遍历以找到插入点，这将给你最坏的时间复杂度。

实际的复杂度取决于插入位置是否是常数（例如始终在第10个位置），还是与列表中的项目数量有关的函数（或某些任意搜索）。前者将给你O(n)，稍微差一些的常数因子，而后者则是O(n^2)。

- Martin Probst

---

好的，这很有道理。我正在将元素添加到列表的前面，因此对于 ArrayList，时间复杂度将是二次的，对于链表则是线性的。 - FranXh

真的，但是在前面添加最好使用ArrayDeque来完成这个任务。几乎总有比LinkedList更好的结构 :) - alf

@BrianRoach 向 ArrayList 的头部添加一个元素不是 O(1)，而是像 Martins 说的那样是 O(n)。 - Roger Lindsjö

Answer 2

在大多数情况下，ArrayList 在 add() 方法上的性能优于 LinkedList，因为它只是保存一个指向数组的指针并递增计数器。

但如果工作数组不够大，ArrayList 将扩展工作数组，分配一个新的数组并复制内容。这比将新元素添加到 LinkedList 慢—但如果你经常添加元素，那么这只会发生 O(log(N)) 次。

当我们谈论“摊销”复杂度时，我们需要计算某个参考任务的平均时间。

所以，回答你的问题，它们的复杂度不同：在大多数情况下，速度更快（尽管仍然是 O(1)），有时速度更慢（O(N)）。你应该使用分析器来确定哪种方法更适合你。

- alf

Answer 3

如果您指的是add(E)方法（而不是add(int, E)方法），那么答案是肯定的，向LinkedList添加单个元素的时间复杂度是恒定的（添加n个元素需要O（n）时间）。

正如Martin Probst所指出的，在不同的位置上，您会得到不同的复杂度，但add(E)操作将始终将元素附加到尾部，从而产生恒定的（摊销）时间操作。

- rodrigo.garcia

---

“add(E)”操作将始终将元素附加到尾部，从而产生一个常数时间操作——但并不完全正确，对于“ArrayList”来说它可能是O(N)。 - alf

@alf 这是真的，当 ArrayList 达到其限制并需要重新生成时。我添加了一个澄清，它在常数（摊销）时间内运行。 - rodrigo.garcia