Java中的时间复杂性

Question

对于方法,添加ArrayList Java API状态:

添加操作以分摊的常量时间运行,即添加n个元素需要O(n)时间.

我想知道当使用LinkedList的add方法时,它是否是同一时间复杂度,线性.

Answer 1

这取决于您要添加的位置.例如,如果在ArrayList中添加到列表的前面,则实现将不得不每次都移动所有项目,因此添加n个元素将以二次方运行.

类似于链表,JDK中的实现保持指向头部和尾部的指针.如果你继续附加在尾部,或者在头部前面,则操作将在n个元素的线性时间内运行.如果您追加到其他位置,则实现必须在链接列表中搜索正确的位置,这可能会使运行时更糟糕.同样,这取决于插入位置; 如果你插入列表的中间,你会得到最差的时间复杂度,因为必须遍历最大数量的元素来找到插入点.

实际的复杂程度取决于您的插入位置是否恒定(例如,始终位于第10个位置),或者是列表中项目数量的函数(或者对其进行任意搜索).第一个会给你O(n)一个稍差的常数因子,后者O(n ^ 2).