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);
    }

}

原文由 user1526053 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

a remove 的成本是 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 将所有其他元素向左移动 - 当您删除原始偏移量 0 时， 最初 位于偏移量 1 的项目将位于偏移量 0，然后您移动on 删除偏移量 1。

原文由 paxdiablo 发布，翻译遵循 CC BY-SA 4.0 许可协议