python 中标准随机数生成器的 Big-O 运行时间是多少? (最坏的情况下)

What is Big-O runtime of the standard random number generator in python? (Worst-case)

示例 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 if genrand_int32() is O(1). The source (for Mersenne Twister PRNG implementation) suggests that it is.