2

我可以在文档中看到：

java.util.AbstractList#removeRange

它需要二次时间：

此实现获取一个位于 fromIndex 之前的列表迭代器，并重复调用 ListIterator.next 后跟 ListIterator.remove，直到删除整个范围。注意：如果 ListIterator.remove 需要线性时间，则此实现需要二次时间。

但为什么？？编码：

protected void removeRange(int fromIndex, int toIndex) {
        ListIterator<E> it = listIterator(fromIndex);
        for (int i=0, n=toIndex-fromIndex; i<n; i++) {
            it.next();
            it.remove();
        }
    }

对我来说似乎是线性的......但我必须是错的，因为我是这种算法的新手。请帮助我理解它。

4

2 回答 2

4

重要的部分是“注意：如果 ListIterator.remove 需要线性时间，则此实现需要二次时间。” for 循环需要线性时间，你是对的。但是，如果你在每次迭代中做一个线性时间步长，你会得到n * n = n^2.

于 2012-08-04T18:21:44.157 回答
3

原因在于：

it.remove();

这可以是列表上的 O(n) 操作，您可以在 O(n) 循环中调用它。

换句话说，如果是这种情况，您的真实循环将如下所示（我编造了，但您明白了）：

protected void removeRange(int fromIndex, int toIndex) {
    ListIterator<E> it = listIterator(fromIndex);
    for (int i = 0, n = toIndex - fromIndex; i < n; i++) {
        E item = it.next();
        //it.remove();
        for (int j = ; j < n; j++) {
            if (list.get(j).equals(e)) {
                list.remove(e);
                break;
            }
        }
    }
}
于 2012-08-04T18:22:46.087 回答