algorithm - 在小于 O(N) 的时间内生成 N 个准随机数

Question

这受到求职面试中的一个问题的启发:如何有效地生成 N 个唯一的随机数？他们的安全和分布/偏见无关紧要。

我提出了一种天真的方法，即调用 rand() N 次并通过反复试验消除重复，从而得到低效且有缺陷的解决方案。然后我读了this SO question ，这些算法非常适合获得高质量的唯一数字，并且它们是 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 或其他方式)从中压缩更多变体。
• 使用 quasi-random sequence不知何故(不是数学家，只是用谷歌搜索了这个词)。

你的想法？

Answer 1

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