对于ArrayList Java API中的add方法,它的运行时间为平均常数时间,也就是添加n个元素需要O(n)的时间。
我想知道,使用LinkedList的add方法时,时间复杂度是否相同,即线性时间?
对于ArrayList Java API中的add方法,它的运行时间为平均常数时间,也就是添加n个元素需要O(n)的时间。
我想知道,使用LinkedList的add方法时,时间复杂度是否相同,即线性时间?
这取决于你添加的位置。例如,如果在ArrayList中向列表开头添加元素,实现将不得不每次都移动所有项目,因此添加n个元素将运行在二次时间内。
对于链表也是类似的,JDK中的实现会保留对头部和尾部的指针。如果你一直将元素追加到尾部,或者在头部前面插入,操作将以线性时间运行n个元素。如果你在不同的地方插入,则实现将不得不在链表中搜索正确的位置,这可能会给你更糟糕的运行时间。再一次强调,这取决于插入位置;如果你在列表中间插入,最大数量的元素必须被遍历以找到插入点,这将给你最坏的时间复杂度。
实际的复杂度取决于插入位置是否是常数(例如始终在第10个位置),还是与列表中的项目数量有关的函数(或某些任意搜索)。前者将给你O(n),稍微差一些的常数因子,而后者则是O(n^2)。
ArrayDeque
来完成这个任务。几乎总有比LinkedList
更好的结构 :) - alfArrayList
在 add()
方法上的性能优于 LinkedList
,因为它只是保存一个指向数组的指针并递增计数器。ArrayList
将扩展工作数组,分配一个新的数组并复制内容。这比将新元素添加到 LinkedList
慢—但如果你经常添加元素,那么这只会发生 O(log(N)) 次。add(E)
方法(而不是add(int, E)
方法),那么答案是肯定的,向LinkedList添加单个元素的时间复杂度是恒定的(添加n个元素需要O(n)时间)。add(E)
操作将始终将元素附加到尾部,从而产生恒定的(摊销)时间操作。ArrayList
达到其限制并需要重新生成时。我添加了一个澄清,它在常数(摊销)时间内运行。 - rodrigo.garcia