c++ - 使用随机数生成器的代码的 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

假设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 循环

平均次数。总和是第 N 个 harmonic number可以粗略地近似为ln(N)。 (有一个众所周知的 better approximation ，它有点复杂，涉及 Euler-Mascheroni constant ，但 ln(N) 足以找到渐近复杂性。)

因此，近似而言，平均迭代次数将为 N ln N。

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

从数值实验来看，对于较大的 N，它似乎大约等于 N/2 * (ln N)^2。(也许可以考虑在 math.SE 上寻求这一点的证明。) 编辑:参见 this math.SE answer一个简短的非正式证明，以及 other answer to that question以获得更正式的证明。

所以总而言之，总的平均复杂度为 θ(N (ln N)^2)。再次强调，这是假设 RNG 是理想的。

最坏情况

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