生成小于O(N)的N个准随机数

Question

这是受到求职面试中的一个问题的启发:你如何有效地生成N个独特的随机数？他们的安全和分配/偏见并不重要.

我提出了一种天真的方式来调用rand()N次并通过反复试验消除欺骗,从而得到效率低下且有缺陷的解决方案.然后我读了这个问题,这些算法非常适合获得高质量的唯一数字,它们是O(N).

但我怀疑有些方法可以在低于O(N)时间复杂度的情况下为虚拟任务获得低质量的唯一随机数.我有一些可能的想法:

• 存储许多预先计算的列表,每个列表包含N个数字并随机检索一个列表.对于固定的N,复杂度是O(1).使用的存储空间是O(NR),其中R是列表的数量.
• 生成N/2个唯一的随机数,然后将它们除以2个不等的部分(奇数的floor/ceil,偶数的n + 1/n-1).我知道这是有缺陷的(重复可以弹出)而O(N/2)仍然是O(N).这更像是一种思考的食物.
• 生成一个大的随机数,然后通过一些固定的操作(如按位运算,分解,递归,MapReduce或其他)从中挤出更多变体.
• 以某种方式使用准随机序列(不是数学家,只是谷歌搜索这个术语).

你的想法？

Answer 1

据推测,这个例程有某种输出(即结果被写入某种数组).填充大小为N的数组(或其他一些数据结构)至少是O(N)操作,因此您不能比O(N)做得更好.