在范围内生成不同的随机数

Question

我希望生成n个不同的数字，这些数字在1到N之间（当然n<=N）。N可能非常大。 如果n很小，一种有效的方法是生成一个数字并将其与我们已经得到的集合进行比较，以确保它是一个新数字。它需要O(n^2)时间和O(n)内存。 如果n相当大，我们可以使用Fisher-Yates随机置换算法生成随机排列（在n步后停止）。它需要O(n)时间，但我们也必须使用O(N)内存。

问题在于，如果我们不知道n有多大怎么办？ 我希望该算法只使用O(n)内存，并在O(n)时间内停止。这是否可能？

- nicolas.wong

---

这是一个相当差的副本 - N 在此处为1000，这里可能是“非常大的”。 - jrok

@j_random_hacker 这使用的是O(N)内存（而不是O(n)）。 - Bernhard Barker

@Floris：我的理解是他们想要一个在线算法——也就是说，随时可以廉价地添加新的、不同的样本。 - j_random_hacker

如果你将集合实现为哈希表，你可以获得O(1)的时间复杂度（至少是期望时间）。 - Jerry Coffin

@JerryCoffin：你说得对，我把n和N搞混了...但不知怎么地只是在哈希表中出现了这种情况，而不是在树中！ - j_random_hacker

Answer 1

对于非常小的n，您可以基本上做相同的事情，但只需使该检查更有效。例如，检查是否已生成数字的天真方法是仅线性搜索先前生成的值列表。对于未知的n，您可以保持先前生成的值集合排序，以便可以使用更高效的搜索来识别重复项。使用天真方法，算法需要O(n²)时间，但通过对先前结果进行更智能的搜索，可以将其减少到O(n*log₂n)。

- bames53

---

将一个值插入到已排序的数组中的时间复杂度为O(n)。如果n是N的相当大的一部分，经常出现重复，则指数项会出现在时间复杂度中，以解释重新运行所花费的时间，并占主导地位。 - j_random_hacker

@j_random_hacker：数组不需要排序，也可以很容易地使用哈希表。 - rici

@j_random_hacker 所以不要使用数组。树可以具有O(log n)的搜索和插入，并且很容易保持排序。 - bames53

@bames53: 我建议你修改你的回答，但我认为它并没有解决我所发现的主要问题——在已选择的数字变得足够密集时导致指数时间复杂度的问题。 - j_random_hacker

@j_random_hacker：您可以指数级地重新散列哈希表，从而获得摊销的线性插入成本，就像向量一样。随机数也是作为哈希表键的理想选择。 - rici

@rici：抱歉，我把我的 n 和 N 搞混了...这里严重缺咖啡因。评论已删除。 - j_random_hacker