Python中标准随机数生成器的Big-O运行时是什么?(最坏情况) [英] What is Big-O runtime of the standard random number generator in python? (Worst-case)
本文介绍了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。
这篇关于Python中标准随机数生成器的Big-O运行时是什么?(最坏情况)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文