java - 为什么 AbstractList.removeRange 需要二次时间？

Question

我可以在文档中看到:

java.util.AbstractList#removeRange

它需要二次时间:

This implementation gets a list iterator positioned before fromIndex, and repeatedly calls ListIterator.next followed by ListIterator.remove until the entire range has been removed. Note: if ListIterator.remove requires linear time, this implementation requires quadratic time.

但是为什么？？代码:

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

对我来说似乎是线性的...但我一定是错的，因为我是这类算法方面的新手。请帮助我理解它。

Answer 1

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