c# - Dictionary の時間と空間の複雑さとは何ですか?

Question

サイズ N (ieN 要素) のデータがあり、ディクショナリが容量 N で作成されたとします。複雑さは次のとおりです。

• スペース -- 辞書全体
• time -- 辞書にエントリを追加

MS は、エントリの検索が O(1) に近いことだけを明らかにしました。しかし、残りはどうですか？

Answer 1

空間の複雑さは何ですか -- 辞書全体の

Dictionaryは、O(N) 空間の複雑さを持つ連想配列データ構造を使用します。

Msdn は次のように述べています。「Dictionary クラスはハッシュ テーブルとして実装されています」。そして、ハッシュテーブルは連想配列を順番に使用します。

時間の複雑さは何ですか - 辞書へのエントリの追加

1 回の追加には、償却 O(1) 時間かかります。ほとんどの場合、これは O(1) ですが、基になるデータ構造を拡大または縮小する必要がある場合は O(N) に変更されます。後者はまれにしか発生しないため、人々は「償却」という言葉を使用します。

Answer 2

新しいエントリを追加する時間の複雑さは、以下に記載されていDictionary<T>.Add()ます。

Count が容量より小さい場合、このメソッドは O(1) 操作に近づきます。新しい要素に対応するために容量を増やす必要がある場合、このメソッドは O(n) 操作になります。ここで、n はカウントです。

Answer 3

正式に文書化されていませんが、基礎となるストレージは名前と値のペアの配列であると広く述べられています (逆アセンブルで確認できます)。したがって、空間の複雑さはO(n)です。

これは仕様の一部ではないため、理論上は変更される可能性があります。しかし、実際には、表示される可能性のあるさまざまな操作 (列挙など) のパフォーマンスが変わるため、そうなる可能性はほとんどありません。