Collection.retainAll（Collection）のコストはどれくらいですか

私は2つの共通要素を見つけたかったLinkedHashSet<String>、主に私自身の関数を書きましたが、コストはo（n^2）でした。その後、私はretainAll() javaの組み込み関数のより良いソリューションを発見しました。私はこの機能のコストがどれくらいかと思っていました。 O（n）またはo（n^2）？Collection.retainAll（Collection）のコストはどれくらいですか

出典

2017-12-18 user1836957

[AbstractCollection']（http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/AbstractCollection.java#）の実装を使用しています。 404）。一定時間の 'contains'と' remove'を使うので、線形のように見えます。 –

@AndyTurner：ありがとう – user1836957

LinkedHashSetには少なくともO（N）になります。ツリーセットのような他のCollectionの場合、それはO（NlogN）になり、残りはO（N^2）に戻ります。

これらの方法は、retainAllメソッドに渡すコレクションによって異なります。だから、HashSetを渡すとTreeSetはO（NlogN）になり、何かがAbstractCollectionでの実装を見てみると（NlogN）

出典

2017-12-18 22:47:45 smac89

Oよりも悪くなり、（N）Oになります、それは、コレクションのすべての要素を反復処理しました（すなわち、n）が呼び出され、各要素に対して、他のコレクションにそれが含まれているかどうかチェックされます（LinkedHashSetの場合はO（1）操作）。

結論 - これはO（n）操作です。ここで、nは、メソッドと呼ばれるコレクションのサイズです。

出典

2017-12-18 22:48:13 Mureinik

Collection.retainAll（Collection）のコストはどれくらいですか

答えて

関連する問題