2

次のドキュメントで確認できます。

java.util.AbstractList#removeRange

二次時間が必要であること：

この実装は、fromIndex の前に配置されたリスト反復子を取得し、範囲全体が削除されるまで、ListIterator.next に続いて ListIterator.remove を繰り返し呼び出します。注: ListIterator.remove に線形時間が必要な場合、この実装には 2 次時間が必要です。

しかし、なぜ？？コード：

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 に線形時間が必要な場合、この実装には 2 次時間が必要です。」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 に答える