Pythonでのdict.keys（）の時間の複雑さは何ですか？

私がthis LeetCode problemを解決するとき、私は質問に出会った。 What is the time complexity of dict.keys() operation?キーのビューまたはキーの実際のリスト（メモリに格納されている）が返されますか？Pythonでのdict.keys（）の時間の複雑さは何ですか？

2016-08-30 Jason

複雑さはPython 3.xでは '0（1）'です。 Python 2.xでは、リストを返すので、そのリストに値を設定するか、またはルックアップを実行するには '0（n）'が必要です。 – ozgur

Python2またはPython3について質問していますか？ –

@ozgur - どちらのバージョンでも真ですが、 '_ for {} .keys（）：pass'は' O（n） 'です。 –

Python 2では、それはO（n）であり、新しいリストを作成します。 Python 3では、O（1）ですが、リストは返されません。 dictのkeysからランダムな要素を描画するには、リストに変換する必要があります。

おそらくその問題のパート3にrandom.choice(d.keys())を使用していたようです。もしそうなら、それはO（n）であり、あなたは間違っています。平均ケースのO（1）の挿入と削除を犠牲にすることなく、独自のハッシュテーブルを実装するか、要素の別のリストを維持する必要があります。

2016-08-30 05:08:22 user2357112

私は 'return self.elements.keys（）[randint（0、len（self.elements） - 1）]'を使用して受け入れました（ 'self.elementsはdictオブジェクトです'）。 – Jason

@Jason：そうです、それはO（1）ではありません。 – user2357112

あなたが「Python 3では、それはO（1）です」と言ったように。 'self.elements.keys（）'が 'O（1）'の場合、式全体は 'O（1）'で実行されます。私が間違いを犯した場合は、私を修正してください:) – Jason

答えて