python - 辞書メソッド 'get(key)' の BigO

Question

Python の辞書 'get(key)' メソッドの O(?) を知っている人はいますか?

cProfile モジュールでテストしたところ、辞書内の 100、1000、10000、100000、1000000、100000000 レコードで同じ結果が得られました。

Python の辞書が任意のキーに対して O(1) アクセス時間を提供するということですか?

Answer 1

答えは「はい」です。Python dict はハッシュを使用してキーを格納するためです。また、ハッシュ テーブルにはO(1)、そのキーにアクセスするための平均的な時間の複雑さがあります。詳細については、http://en.wikipedia.org/wiki/Hash_tableを参照してください。

キー取得の最悪のシナリオは ですO(n)。ここnで、 は 内のキーの数ですdictionary。(@マイケル・ブッチャー)。