问：Python3中random.choice（list）的Big-O复杂性是什么

Question

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

编辑。谢谢大家给我答案，现在我明白了。

Answer 1

虽然问题是关于 的random.choice，并且之前的答案有几个解释，但当我搜索 的复杂性时np.random.choice，我没有找到答案，所以我决定解释一下np.random.choice。

选择（a，大小=无，替换=真，p=无）。假设a.shape=(n,)和size=m。

更换时：

如果未指定（假设为均匀分布），则复杂度为np.random.choiceO(m) ；如果指定，则复杂度为 O(n + n log m )。pp

github 代码可以在这里找到np.random.choice。

当p不指定时，choice通过 生成索引数组randint并返回a[index]，因此复杂度为 O(m)。（我假设通过 randint 生成随机整数的操作是 O(1)。）

当p指定时，该函数首先计算 的前缀和p。然后从 [0, 1) 中抽取 m 个样本，然后使用二分查找在每个抽取样本的前缀和中找到对应的区间。使用二分搜索的证据可以在这里找到。所以这个过程是O(n + m log n)。如果在这种情况下需要更快的方法，可以使用Alias Method，该方法需要 O(n) 时间进行预处理，并需要 O(m) 时间来采样 m 个项目。

不替换时：（有点复杂，也许以后会完成。）

如果p未指定，复杂度与 相同np.permutation(n)，即使 m 仅 1。请参阅此处。

如果p指定，则预期复杂度至少为 $n \log n \log\frac{n}{n + 1 - m}$。（这是一个上限，但并不严格。）

Answer 2

O(1)。或者更确切地说，它等于按任何传递顺序查找单个索引的big-O随机访问时间，并且list具有O(1)随机访问索引（也是如此tuple）。简化后，它所做的全部是seq[random.randrange(len(seq))]，这显然等效于单个索引查找操作。

在那里将是一个例子O(n)是collections.deque，其中，在分度的中间deque是O(n)（具有相当大的恒定除数虽然，所以它不贵，除非deque在到达数千个元素范围或更高）。所以基本上，不要使用deque，如果它要大，并计划一再从中选择随机元素，棍子list，tuple，str，byte/ bytearray，array.array和其他序列类型与O(1)索引。

Answer 3

random.choice(list) 的复杂度为 O(log n)，其中 n 是列表中元素的数量。

cpython 实现使用_randbelow(len(seq))获取伪随机索引，然后返回该索引处的项目。

瓶颈是_randbelow()函数，它使用拒绝采样来生成 [0, n) 范围内的数字。该函数通过调用getrandbits(k)生成 k 个伪随机位，其中 k 是 ceil(log N)。这些位表示 [0, 2**k) 范围内的数字。重复这个过程，直到生成的数字小于n。对伪随机数生成器的每次调用都以 O(k) 的时间运行，其中 k 是生成的位数，即 O(log n)。