java - Java 中的时间复杂度

Question

对于 ArrayList Java API 的方法 add 声明:

添加操作以摊销常数时间运行，即添加 n 个元素需要 O(n) 时间。

想知道是不是同样的时间复杂度，线性的，在使用LinkedList的add方法的时候。

Answer 1

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

与链表类似，JDK 中的实现保留了指向头和尾的指针。如果您继续追加到尾部，或在头部前面添加，则操作将以线性时间运行 n 个元素。如果你在不同的地方追加，实现将不得不在链表中搜索正确的地方，这可能会给你带来更糟糕的运行时间。同样，这取决于插入位置；如果您在列表的中间插入，您将获得最差的时间复杂度，因为必须遍历最大数量的元素才能找到插入点。

实际的复杂性取决于您的插入位置是恒定的(例如总是在第 10 个位置)，还是列表中项目数量的函数(或对其进行的一些任意搜索)。第一个会给你 O(n) 和稍微差一点的常数因子，后者 O(n^2)。