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

Question

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

我想用 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)

Run Code Online (Sandbox Code Playgroud)

While 循环会一直持续下去，直到我们生成从 1 到 N 的所有值。我的理解是 Set 将值以对数时间 log(N) 排序，并插入到 log(N) 中。

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

Run Code Online (Sandbox Code Playgroud)

其中X越多，生成不在Set中的数的概率就越高。

time O(X log N)

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

Run Code Online (Sandbox Code Playgroud)

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

Answer 1

nom*_*ype 5

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

\n\n

（当然，实际上 RNG 并不理想。但我们就这样吧，因为它让数学变得更容易。）

\n\n

平均情况

\n\n

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

\n\n

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

\n\n

以 (N-1)/N 的概率，它将与 val ₁不同，并且将执行内部条件。在本例中，将所选值称为 val ₂。
否则（概率为 1/N），所选值将等于 val ₁。重试。

\n\n

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

\n\n

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

\n\n

总共将执行 do 循环

\n\n

$1 + N/(N-1) + N/(N-2) + ... + N/1 = N sum_{i=1}^N 1/i$