Python3 中 random.choice(list) 的大 O 复杂度 [英] Big-O complexity of random.choice(list) in Python3

问题描述

Python3 中 random.choice(list) 的 Big-O 复杂度是多少，其中 n 是列表中元素的数量?

What is Big-O complexity of random.choice(list) in Python3, where n is amount of elements in a list?

谢谢大家给我的答案，现在我明白了.

Thank You all for give me the answer, now I understand.

推荐答案

O(1).或者更准确地说，它相当于在任何序列中查找单个索引的 big-O 随机访问时间，并且 list 具有 O(1) 随机访问索引(与 tuple 一样).简化，它所做的只是seq[random.randrange(len(seq))]，显然等价于单次索引查找操作.

O(1). Or to be more precise, it's equivalent to the big-O random access time for looking up a single index in whatever sequence you pass it, and list has O(1) random access indexing (as does tuple). Simplified, all it does is seq[random.randrange(len(seq))], which is obviously equivalent to a single index lookup operation.

O(n) 的一个例子是 collections.deque，其中 deque 中间的索引是 O(n)(虽然有一个较大的常数除数，所以它不会那么昂贵，除非 deque 达到数千个元素范围或更高).所以基本上，如果 deque 会很大并且你打算从它重复选择随机元素，不要使用 deque，坚持使用 list, tuple、str、byte/bytearray、array.array 和其他O(1) 索引.

An example where it would be O(n) is collections.deque, where indexing in the middle of the deque is O(n) (with a largish constant divisor though, so it's not that expensive unless the deque is reaching the thousands of elements range or higher). So basically, don't use a deque if it's going to be large and you plan to select random elements from it repeatedly, stick to list, tuple, str, byte/bytearray, array.array and other sequence types with O(1) indexing.

这篇关于Python3 中 random.choice(list) 的大 O 复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！