1

这是受求职面试中一个问题的启发：如何有效地生成 N 个唯一随机数？他们的安全性和分布/偏见并不重要。

我提出了一种调用 rand() N 次并通过反复试验消除欺骗的幼稚方法，从而得到低效且有缺陷的解决方案。然后我读了这个 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 或其他方法）从中挤出更多变体。
  • 以某种方式使用准随机序列（不是数学家，只是在谷歌上搜索了这个术语）。

你的想法？

4

2 回答 2

6

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

于 2012-04-08T16:55:34.833 回答
0

因此，您可以生成一个随机数，如果结果数组包含它，只需将已生成数字的最大数量添加到其中。

检测已经生成的数字是否为 O(1)（使用哈希集）。所以它是 O(n) 并且只有 Nrandom()次调用。

当然，这是假设我们没有溢出上限（即 BigInteger）。

于 2012-04-08T17:02:23.697 回答