使用随机数生成器的 Big-O 代码是什么？

Question

我想用从 1 到 N 的随机值（无重复值）填充数组 'a'。假设 randInt(i, j) 的 Big-O 是 O(1) 并且此函数生成从 i 到 j 的随机值。
输出示例为：

{1,2,3,4,5} 或 {2,3,1,4,5} 或 {5,4,2,1,3} 但不是 {1,2,1,3 ,4}

#include<set>
using std::set;

set<int> S;// space O(N) ?
int a[N];  // space O(N)
int i = 0; // space O(1)
do {
    int val = randInt(1,N);   //space O(1), time O(1) variable val is created many times ?
    if (S.find(val) != S.end()) { //time O(log N)? 
        a[i] = val; // time O(1)
        i++; // time O(1)
        S.insert(val); // time O(log N)  <-- we execute N times O(N log N)
    }
 } while(S.size() < N); // time O(1)

While 循环将继续，直到我们生成从 1 到 N 的所有值。我的理解是 Set 将值按对数时间 log(N) 排序，然后插入到 log(N) 中。

Big-O = O(1) + O(X*log N) + O(N*log N) = O(X*log N)

其中X越大，产生不在Set中的数的概率就高

time O(X log N)

space O(2N+1) => O(N), we reuse the space of val

哪里??每次执行 randInt 都很难生成所有不同的数字，所以至少我希望执行 N 次。
变量X是不是创建了很多次？
X 的合适价值是多少？

Answer 1

对于实现您的目标来说，这是一个非常糟糕的算法。

只需用数字 1 到 N 填充数组，然后随机播放。

那是 O(N)

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

要随机播放，请在 0 和 N-1 之间选择一个索引并将其与索引 0 交换。然后在 1 和 N-1 之间选择一个索引并将其与索引 1 交换。一直到列表末尾.

就您的具体问题而言，这取决于您的随机数生成器的行为。如果它真的是随机的，它可能永远不会完成。如果是伪随机，则取决于生成器的周期。如果它的周期为 5，那么您将永远不会被骗。

Answer 2

这是具有复杂行为的灾难性错误代码。生成第一个数字是 O(1)，然后第二个数字涉及二进制搜索，所以一个 log N，如果找到该数字，再加上生成器的重新运行。得到一个新数字的机会是 p = 1- i/N。所以重新运行的平均次数是倒数，并且给你 N 的另一个因子。所以 O(N^2 log N).

方法是生成数字，然后将它们洗牌。那是 O(N)。

Answer 3

假设RNG是理想的。也就是说，重复调用 randInt(1,N) 会生成 i.i.d。（独立同分布）在 {1,...,N} 上均匀分布的值序列。

（当然，在现实中，RNG 不会是理想的。但让我们继续吧，因为它使数学更容易。）

平均情况

在第一次迭代中，选择了一个随机值 val₁，当然它还不在集合 S 中。

在下一次迭代中，选择另一个随机值。

以概率(N-1)/N，它将与val₁不同，并且内部条件将被执行。在这种情况下，将所选值称为 val₂.
否则（概率为 1/N），所选值将等于 val₁。重试。

在选择有效（不同于 val₁）val₂ 之前平均需要多少次迭代？好吧，我们有一个独立的尝试序列，每次尝试的成功概率为 (N-1)/N，我们想知道在第一次成功之前平均需要多少次尝试。这是一个几何分布，一般来说，成功概率为 p 的几何分布的均值为 1/p。因此，平均需要 N/(N-1) 次尝试才能选择 val₂.

类似地，平均需要 N/(N-2) 次尝试才能选择 val₃ 与 val₁ 和 val₂，依此类推。最后，第 N 个值平均需要 N/1 = N 次尝试。

总共将执行 do 循环

平均

次。总和 is the N-th harmonic number which can be roughly approximated by ln(N). (There's a well-known better approximation which is a bit more complicated and involves the Euler-Mascheroni constant，但 ln(N) 足以找到渐近复杂度。）

所以为了近似，平均迭代次数将是 N ln N。

算法的其余部分呢？像将 N 个东西插入集合这样的事情最多也需要 O(N log N) 时间，所以可以忽略不计。剩下的重要事情是每次迭代你都必须检查所选择的随机值是否位于 S 中，这需要 S 的当前大小的对数时间。所以我们必须计算

从数值实验来看，对于大 N，它似乎近似等于 N/2 * (ln N)^2。~~（考虑在 [=79 上寻求证明=]，也许。）~~ 编辑：请参阅 this math.SE answer for a short informal proof, and the other answer to that question 以获得更正式的证明。

所以总的来说，总的平均复杂度是Θ(N (ln N)^2)。同样，这是假设 RNG 是理想的。

最坏的情况

就像 xaxxon 提到的那样，算法根本不会终止在原则上是可能的（尽管不太可能）。因此，最坏情况下的复杂度为 O(∞).

使用随机数生成器的 Big-O 代码是什么？

What is the Big-O of code that uses random number generators?

c++

algorithm

big-o

平均情况

最坏的情况