java arrayList remove(element) 的时间复杂度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/24462513/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
time complexity for java arrayList remove(element)
提问by user1526053
I was trying to graph the Time Complexity of ArrayList's remove(element) method. My understanding is that it should be O(N), however, its giving me a O(1). Can anyone point out what i did wrong here?? Thank you in advance.
我试图绘制 ArrayList 的 remove(element) 方法的时间复杂度。我的理解是它应该是 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<Integer> list = new ArrayList<Integer>();
// 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);
}
}
回答by dkatzel
remove(int)removes the element at the ith INDEX which is O(1)
remove(int)删除第 i 个 INDEX 处的元素，即 O(1)
You probably want remove( Object )which is O(N) you would need to call remove(Integer.valueOf(i))
你可能想要remove( Object )哪个 O(N) 你需要调用remove(Integer.valueOf(i))
it would be more obvious if your list didn't have the elements in order
如果您的列表没有按顺序排列的元素会更明显
回答by paxdiablo
The cost of a removeis O(n)as you have to shuffle the elements above that point "left" by one. If your test code is giving you O(1)then you're not measuring it properly :-)
a 的成本remove是O(n)因为您必须将该点上方的元素“向左”移动一个。如果您的测试代码给了您，O(1)那么您没有正确测量它:-)
The OpenJDK source, for example, has this:
例如，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;
}
and the System.arraycopyis the O(n)cost for this function.
而System.arraycopy就是O(n)这个功能成本。
In addition, I'm not sure you've thought thisthrough very well:
此外，我不确定您是否已经很好地考虑了这一点：
for (int i = 0; i < list.size() ; i++)
list.remove(i);
This is going to remove the following elements from the originallist:
这将从原始列表中删除以下元素：
0, 2, 4, 8
and so on, because the act of removing element 0shifts all other elements left - the item that was originallyat offset 1 will be at offset 0 when you've deleted the original offset 0, and you then move on to delete offset 1.
依此类推，因为删除元素的行为0会将所有其他元素向左移动 -当您删除原始偏移量 0 时，最初位于偏移量 1 的项目将位于偏移量 0，然后您继续删除偏移量 1。
You would be better off with:
你会更好：
list.remove(0);
inside the loop.
循环内。
回答by Stephen C
First off, you are not measuringcomplexity in this code. What you are doing is measuring (or attempting to measure) performance. When you graph the numbers (assuming that they are correctly measured) you get a performance curve for a particular use-case over a finite range of values for your scaling variable.
首先，您不是在测量此代码的复杂性。您正在做的是衡量（或试图衡量）绩效。当您绘制数字（假设它们被正确测量）时，您将获得特定用例在缩放变量的有限值范围内的性能曲线。
That is not the same as a computational complexity measure; i.e. big O, or related Bachman-Landau notations. These are about mathematical limits as the scaling variable tends to infinity.
这与计算复杂性度量不同；即大 O，或相关的Bachman-Landau 符号。这些是关于数学限制的，因为缩放变量趋于无穷大。
And this is not just a nitpick. It is quite easy to construct examples1where performance characteristics change markedly as N gets very large.
这不仅仅是吹毛求疵。构建示例1非常容易，其中当 N 变得非常大时，性能特征会发生显着变化。
What are doing when you graph performance over a range of values and fit a curve is to estimatethe complexity.
当您在一系列值上绘制性能图并拟合曲线时，所做的是估计复杂性。
1 - And a real example is the average complexity of various HashMapfunctions which switch from O(1)to O(N)(with a very small C) when Nreaches 2^31. The modality is because the hash array cannot grow beyond 2^31slots.
1 - 一个真实的例子是当到达时HashMap从O(1)to切换到O(N)（非常小C）的各种函数的平均复杂度。这种方式是因为哈希数组不能增长到插槽之外。N2^312^31
The second point is that that the complexity of ArrayList.remove(index)is sensitive to the value of indexas well as the list length.
第二点是， 的复杂ArrayList.remove(index)度对 的值index以及列表长度很敏感。
The "advertised" complexity of
O(N)for the average and worst cases.In the best case, the complexity is actually
O(1). Really!This happens when you remove the last element of the list; i.e.
index == list.size() - 1. That can be performed with zero copying; look at the code that @paxdiablo included in his Answer.
O(N)平均和最坏情况的“广告”复杂性。在最好的情况下，复杂性实际上是
O(1)。真的！当您删除列表的最后一个元素时会发生这种情况；即
index == list.size() - 1。这可以通过零复制来执行；看看@paxdiablo 包含在他的答案中的代码。
Now to your Question. There are a number of reasons why your code could give incorrect measurements. For example:
现在回答你的问题。您的代码可能会给出不正确的测量值的原因有很多。例如：
You are not taking account of JIT compilation overheads and other JVM warmup effects.
I can see places where the JIT compiler could potentially optimize away entire loops.
The way you are measuring the time is strange. Try treating this as algebra ... and simplifying.
((midPoint - start) - (stop - midPoint)) / count;The
midPointterm disappears ....You are only removing half of the elements from the list, so you only measuring over the range 50,000 to 100,000 of your scaling variable. (And I expect you are then plotting against the scaling variable; i.e. you are plotting f(N + 5000) against N.
The time intervals you are measuring could betoo small for the clock resolution on your machine. (Read the javadocs for
nanoTime()to see what resolution it guarantees.)
您没有考虑 JIT 编译开销和其他 JVM 预热效果。
我可以看到 JIT 编译器可能优化掉整个循环的地方。
你测量时间的方式很奇怪。尝试将其视为代数......并简化。
((midPoint - start) - (stop - midPoint)) / count;这个
midPoint词消失了......您只是从列表中删除了一半的元素，因此您只能测量缩放变量的 50,000 到 100,000 范围。（并且我希望您随后针对缩放变量进行绘图；即您正在针对 N 绘制 f(N + 5000)。
您测量的时间间隔对于您机器上的时钟分辨率来说可能太小了。（阅读 javadoc
nanoTime()以了解它保证的分辨率。）
