177

もうすぐ「Java クラッシュ コース」を教えることになるかもしれません。聴衆メンバーが Big-O 記法を知っていると想定するのはおそらく安全ですが、さまざまなコレクション実装でのさまざまな操作の順序が何であるかを知っていると想定するのはおそらく安全ではありません。

自分で要約マトリックスを生成するのに時間をかけることもできますが、それがすでにどこかで公開されている場合は、それを再利用したいと思います (もちろん、適切なクレジットを付けて)。

誰にも指針がありますか？

4

4 に答える 4

262

本Java Generics and Collectionsにこの情報があります (ページ: 188、211、222、240)。

実装のリスト:

                      get  add  contains next remove(0) iterator.remove
ArrayList             O(1) O(1) O(n)     O(1) O(n)      O(n)
LinkedList            O(n) O(1) O(n)     O(1) O(1)      O(1)
CopyOnWrite-ArrayList O(1) O(n) O(n)     O(1) O(n)      O(n)

実装の設定:

                      add      contains next     notes
HashSet               O(1)     O(1)     O(h/n)   h is the table capacity
LinkedHashSet         O(1)     O(1)     O(1) 
CopyOnWriteArraySet   O(n)     O(n)     O(1) 
EnumSet               O(1)     O(1)     O(1) 
TreeSet               O(log n) O(log n) O(log n)
ConcurrentSkipListSet O(log n) O(log n) O(1)

マップの実装:

                      get      containsKey next     Notes
HashMap               O(1)     O(1)        O(h/n)   h is the table capacity
LinkedHashMap         O(1)     O(1)        O(1) 
IdentityHashMap       O(1)     O(1)        O(h/n)   h is the table capacity 
EnumMap               O(1)     O(1)        O(1) 
TreeMap               O(log n) O(log n)    O(log n) 
ConcurrentHashMap     O(1)     O(1)        O(h/n)   h is the table capacity 
ConcurrentSkipListMap O(log n) O(log n)    O(1)

キューの実装:

                      offer    peek poll     size
PriorityQueue         O(log n) O(1) O(log n) O(1)
ConcurrentLinkedQueue O(1)     O(1) O(1)     O(n)
ArrayBlockingQueue    O(1)     O(1) O(1)     O(1)
LinkedBlockingQueue   O(1)     O(1) O(1)     O(1)
PriorityBlockingQueue O(log n) O(1) O(log n) O(1)
DelayQueue            O(log n) O(1) O(log n) O(1)
LinkedList            O(1)     O(1) O(1)     O(1)
ArrayDeque            O(1)     O(1) O(1)     O(1)
LinkedBlockingDeque   O(1)     O(1) O(1)     O(1)

java.utilパッケージの javadoc の下部には、いくつかの適切なリンクが含まれています。

于 2009-02-18T04:35:20.220 に答える
164

この Web サイトは非常に優れていますが、Java に特化したものではありません: http://bigocheatsheet.com/ このリンクが機能しない場合の画像は次のとおりです

于 2010-10-29T07:41:28.640 に答える
13

各コレクション クラスの Sun からの Javadoc は、通常、必要なものを正確に示します。HashMap、例:

この実装は、ハッシュ関数が要素をバケット間で適切に分散すると仮定すると、基本操作 (get および put)に対して一定時間のパフォーマンスを提供します。コレクション ビューの反復には、HashMap インスタンスの「容量」 (バケットの数) とそのサイズ (キーと値のマッピングの数) に比例する時間が必要です。

ツリーマップ:

この実装では、containsKey、get、put、remove 操作の保証された log(n) 時間コストが提供されます。

ツリーセット:

この実装は、基本的な操作(追加、削除、および含む)の保証された log(n) 時間コストを提供します。

(私のものを強調)

于 2009-02-18T04:31:55.080 に答える
6

上記の人は、HashMap / HashSet と TreeMap / TreeSet の比較を行いました。

ArrayList と LinkedList について説明します。

配列リスト：

  • O(1)get()
  • 償却 O(1)add()
  • ListIterator.add()またはを使用して途中の要素を挿入または削除するIterator.remove()と、後続のすべての要素をシフトするのに O(n) になります

リンクリスト:

  • の上）get()
  • O(1)add()
  • ListIterator.add()またはを使用して途中で要素を挿入または削除するIterator.remove()と、O(1) になります。
于 2009-05-02T00:52:30.650 に答える