Q：Python3のrandom.choice（リスト）のBig-Oの複雑さは何ですか？

Question

Python3のrandom.choice（list）のBig-Oの複雑さは何ですか？nはリストの要素の量ですか？

編集。私に答えを与えてくれてありがとう、今私は理解する。

Answer 1

O(1)。または、より正確には、で1つのインデックスを参照する場合のbig-Oランダムアクセス時間に相当します。listはのようにO(1)ランダムアクセスインデックスを持っています（tuple）。それはO(n)あろうSimplified, all it does is seq[random.randrange(len(seq))], which is obviously equivalent to a single index lookup operation.

例はdequeの中央にインデクシングはしかし大きめ定数除数と（O(n)ので、deque、要素の数千に到達されていない限り、それは高価ではない範囲で以上collections.deque、あります）。だから、基本的には、大きなことになるだろう場合dequeを使用すると、あなたが繰り返し、それからランダム要素を選択することを計画し、list、tuple、str、byte/bytearray、array.arrayとO(1)インデックスと他のシーケンス型に固執しないでください。