Python中标准随机数生成器的Big-O运行时是什么？(最坏情况)

问题描述

python2示例代码：

for i in range(N):
    print str(random.randint(0, N))

假设随机数生成器在O(1)中运行，那么上面的循环(简单地打印0-N范围内的N个随机数)是O(N)，是否安全？

---

解决方案

random.randint(0, N)可能是O(log N)，即它与N中的位数成比例。

The implementation confirms it如果我们假设.getrandbits(k)是O(k)。

It seems to be true for CPython如果genrand_int32()为O(1)。The source (for Mersenne Twister PRNG implementation) suggests that it is。