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

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

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

来源

2013-10-31 nicolas.wong

这是一个非常糟糕的重复 - N有1000，这里可能是“非常大”。 – jrok

@j_random_hacker使用O（N）内存（不是O（n））。 – Dukeling

@jrok：足够公平，近距离投票撤回。但是我注意到该页面上的O（1） - 空间解决方案：http://stackoverflow.com/a/202225/47984。 –

你可以做很小的n，但只是使检查效率更高。例如，检查您是否已经生成一个数字的简单方法是仅仅线性搜索先前生成的值的列表。对于未知的n您可以保留先前生成的值的集合，以便您可以使用更高效的搜索来识别重复。使用天真的方法，该算法需要O（n ）时间，但通过先前结果的更明智搜索可以将其减少到O（n * log _n n）。

来源

2013-10-31 15:23:27 bames53

虽然将值插入排序数组中的时间为O（n）。如果n是足够大的N的一小部分，经常出现重复，那么时间复杂度就会出现一个指数项，以说明重新运行它的时间，并将支配它。 –

@j_random_hacker：数组不需要排序。它可以很容易地是一个哈希表。 – rici

@j_random_hacker所以不要使用数组。一棵树可以有O（log n）搜索和插入，并且很容易保持排序。 – bames53

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

回答

相关问题