私は2つの共通要素を見つけたかったLinkedHashSet<String>
、主に私自身の関数を書きましたが、コストはo(n^2)でした。その後、私はretainAll()
javaの組み込み関数のより良いソリューションを発見しました。 私はこの機能のコストがどれくらいかと思っていました。 O(n)またはo(n^2)?Collection.retainAll(Collection)のコストはどれくらいですか
1
A
答えて
1
LinkedHashSetには少なくともO(N)になります。ツリーセットのような他のCollection
の場合、それはO(NlogN)になり、残りはO(N^2)に戻ります。
これらの方法は、retainAll
メソッドに渡すコレクションによって異なります。だから、HashSet
を渡すとTreeSet
はO(NlogN)になり、何かがAbstractCollection
での実装を見てみると(NlogN)
2
Oよりも悪くなり、(N)Oになります、それは、コレクションのすべての要素を反復処理しました(すなわち、n
)が呼び出され、各要素に対して、他のコレクションにそれが含まれているかどうかチェックされます(LinkedHashSet
の場合はO(1)操作)。
結論 - これはO(n)操作です。ここで、n
は、メソッドと呼ばれるコレクションのサイズです。
関連する問題
- 1. x86_64の割り込みコストはどれくらいですか
- 2. ルビーではどれくらいのコストがかかりますか?
- 3. C#の基本操作のコストはいくらですか?
- 4. レルムをリフレッシュするコストはいくらですか?
- 5. 「x in collection」からLINQ文を正しく実装するにはどうすればよいですか?
- 6. スレッドのCPUサイクルとメモリの大まかな「コスト」はいくらですか?
- 7. データベース列にNULLを使用するコストはいくらですか?
- 8. Windowsカーネルモードとユーザーモードを切り替えるにはどのくらいのコストがかかりますか?
- 9. Backbone Collectionフェッチコールバックをアンバインドするにはどうすればよいですか?
- 10. FileSystemWatcherのサイズNotifyFilterはどれくらい細かいですか?
- 11. どのJavaオブジェクトタイプ(collection/list/set/whatever)でこれをしたいですか?
- 12. プロトタイプ(JavaScript)でのイベントのパフォーマンスはどれくらいですか?
- 13. JLabelはどれくらい小さいのですか?
- 14. akkaの俳優はどれくらい重いですか?
- 15. EC2のエラスティックロードバランシングはどれくらい良いですか
- 16. Python/djangoの例外はどれくらい遅いですか?
- 17. Doctrine Collectionの要素数が正しくないのはなぜですか?
- 18. これらの各ケースでの最大ファイルサイズはどれくらいですか?
- 19. 私はMVCからどのくらい離れています
- 20. HTMLのテキストのデフォルトのピクセルサイズはどれくらいですか?
- 21. Androidワーカースレッドはどれくらい持続するのですか?
- 22. fortranの "double"タイプのサイズはどれくらいですか?
- 23. iPhone 4のGPSの精度はどれくらいですか?
- 24. このアルゴリズムの複雑さはどれくらいですか
- 25. RのURLの最大長はどれくらいですか?
- 26. PostgreSQLのフットプリントの大きさはどれくらいですか?
- 27. GPSのスピードはWindows phone 7のどれくらいですか
- 28. YouTubeチャンネルのチャンネルのサイズはどれくらいですか?
- 29. ICS(Android OS4.0)のデフォルトのアプリケーションヒープサイズはどれくらいですか?
- 30. iptablesのバイトカウンタの大きさはどれくらいですか?
[AbstractCollection'](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/AbstractCollection.java#)の実装を使用しています。 404)。一定時間の 'contains'と' remove'を使うので、線形のように見えます。 –
@AndyTurner:ありがとう – user1836957