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

What is Big-O runtime of the standard random number generator in python? (Worst-case)(Python中标准随机数生成器的Big-O运行时是什么?(最坏情况))

本文介绍了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运行时是什么?(最坏情况)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!

本文标题为:Python中标准随机数生成器的Big-O运行时是什么?(最坏情况)

基础教程推荐