问题描述
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 复杂度的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!