java arrayList的时间复杂度删除（元素）

我试图绘制ArrayList的remove（element）方法的Time Complexity。 我的理解是它应该是O（N），然而，它给我一个O（1）。 任何人都可以指出我在这里做错了什么？ 先谢谢你。

public static void arrayListRemoveTiming(){ long startTime, midPointTime, stopTime; // Spin the computer until one second has gone by, this allows this // thread to stabilize; startTime = System.nanoTime(); while (System.nanoTime() - startTime < 1000000000) { } long timesToLoop = 100000; int N; ArrayList list = new ArrayList(); // Fill up the array with 0 to 10000 for (N = 0; N < timesToLoop; N++) list.add(N); startTime = System.nanoTime(); for (int i = 0; i < list.size() ; i++) { list.remove(i); midPointTime = System.nanoTime(); // Run an Loop to capture other cost. for (int j = 0; j < timesToLoop; j++) { } stopTime = System.nanoTime(); // Compute the time, subtract the cost of running the loop // from the cost of running the loop. double averageTime = ((midPointTime - startTime) - (stopTime - midPointTime)) / timesToLoop; System.out.println(averageTime); } } 

Answer 1

remove的成本是O(n)因为你必须将“左”点上方的元素混为一。 如果你的测试代码给你O(1)那么你没有正确测量它:-)

例如，OpenJDK源具有：

 public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // Let gc do its work return oldValue; } 

System.arraycopy是此函数的O(n)成本。

---

另外，我不确定你是否已经认识到这一点 ：

 for (int i = 0; i < list.size() ; i++) list.remove(i); 

这将从原始列表中删除以下元素：

 0, 2, 4, 8 

依此类推，因为移除元素0的行为会将所有其他元素向左移动 - 当您删除原始偏移0时， 原始位于偏移1的项目将位于偏移0处，然后继续删除偏移量1。

你会更好：

 list.remove(0); 

在循环内。

Answer 2

首先，您不是在测量此代码中的复杂性。 您正在做的是衡量（或尝试衡量）绩效。 当您绘制数字图表时（假设它们被正确测量），您可以获得特定用例的性能曲线，该曲线变量的有限值范围内。

这与计算复杂性度量不同; 即大O，或相关的Bachman-Landau符号 。 这些是关于数学限制的，因为缩放变量趋于无穷大。

这不仅仅是一个挑剔。 构建N个变得非常大时性能特征发生显着变化的例子非常容易。

当您在一系列值上绘制性能并拟合曲线时，正在做的是估计复杂性。

---

第二点是ArrayList.remove(index)的复杂性对ArrayList.remove(index)的值以及列表长度很敏感。

• 平均和最差情况下O(N)的“广告”复杂性。

• 在最好的情况下，复杂性实际上是O(1) 。 真！

  删除列表的最后一个元素时会发生这种情况; 即index == list.size() - 1 。 这可以通过零复制来执行; 看看@paxdiablo在他的答案中包含的代码。

---

现在问你的问题。 您的代码可能导致错误测量的原因有很多。 例如：

• 您没有考虑JIT编译开销和其他JVM预热效果。

• 我可以看到JIT编译器可能潜在地优化整个循环的地方。

• 你测量时间的方式很奇怪。 尝试将其视为代数……并简化。

    ((midPoint - start) - (stop - midPoint)) / count; 

  midPoint术语消失了….

• 您只从列表中删除了一半元素，因此您只能测量缩放变量的50,000到100,000范围。 （而且我希望你正在绘制缩放变量;即你正在绘制f（N + 5000）对N.

• 您测量的时间间隔对于机器上的时钟分辨率来说可能太小。 （阅读nanoTime()的javadocs以查看它保证的分辨率。）

Answer 3

remove(int)删除第i个INDEX处的元素，即O（1）

您可能想要remove( Object ) ，这是您需要调用的O（N） remove(Integer.valueOf(i))

如果您的列表没有按顺序排列元素，那将更加明显