java - java arrayList remove(element) 的时间复杂度

Question

我试图绘制 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);
    }


}

Answer 1

删除 的成本是 O(n)，因为您必须将元素从该点“左边”的“右边”移动一个:

                 Delete D
                     |
                     V
+-----+-----+-----+-----+-----+-----+-----+
|  A  |  B  |  C  |  D  |  E  |  F  |  G  |
+-----+-----+-----+-----+-----+-----+-----+
                     <------------------
                      Move E, F, G left

如果您的测试代码给您 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 的操作会将所有其他元素向左移动 - 最初 位于偏移量 1 的项目将位于偏移量 0，当您已经删除了原始偏移量 0，然后您继续删除偏移量 1。