生成随机数字字符串的算法,长度为 10,000 个字符?

标签 algorithm string big-o

可以是任何语言甚至是伪代码。我在一个面试问题中被问到这个问题,我很好奇你们能想出什么。

最佳答案

我认为这是一个棘手的问题 - 使用标准库例程生成数字的明显答案几乎肯定是有缺陷的,如果您想以相同的概率生成所有可能的 10000 位数字...

如果算法随机数生成器维护 n 位状态,那么显然它可以生成最多 2n 种可能的不同输出序列,因为只有 2n 个不同的初始配置。

233219 < 1010000 < 233220,因此如果您的算法使用少于 33220 位的内部状态,它不可能生成 1010000 个可能的 10000 位(十进制)数字中的一些。

典型的标准库随机数生成器不会使用如此多的内部状态。即使是 Mersenne Twister (据我所知,最常提到的具有较大状态的生成器)仅保留 624 个 32 位字(= 19968 位)的状态。

关于生成随机数字字符串的算法,长度为 10,000 个字符?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4221001/

相关文章:

c++ - 我使用 bool 运算符错了吗?

algorithm - 什么是平滑多个二次贝塞尔曲线的好算法?

algorithm - 算法中使用的 O() 表示法

.net - String.Split 的异常行为

algorithm - 什么是 exp(O(n)) 以及它与 O(exp(n)) 有什么不同?

java - 为什么计算复杂度是 O(n^4)?

c# - 如何使用 Math.pow 或 Math.log 描述方法的 Big O 表示法?

python - 计算 Dijkstra 算法中的跳跃次数?

python - Python 中的递归字符串替换和转义

iphone - 如何在 Objective-C 中将字符串转换为数组?