具有不确定迭代次数的 while 大 O 循环

Question

我似乎无法合理化迭代次数不确定的 while 循环的 Big-O 表示法。

在我的个人项目代码中，我有一个包含全 0 的列表。然后我实现一个 while 循环，它会生成一个介于 0 和 9 之间的随机整数。如果列表中随机数索引处的值为 0，则该值被写入 1 并且 while 循环退出。否则，将再次生成一个随机数并重复该过程。

不过，我不完全确定这样做的时间复杂度是多少。例如，如果在算法的 9 次迭代之后，列表中除索引 9 之外的每个值都是 1，并且如果随机数生成器恰好没有为 99 次迭代生成数字 9，那么它将在 99 次后退出+ 9 次迭代。最坏的情况不是 O(infinity) 吗？我不认为这是可能的，但我想我会问，因为我不确定。

我的教科书和在线资源似乎没有对此类示例提供太多见解。我确定最好的情况是 O(1)，但我不确定平均情况和最坏情况。

我发现了一个具有相同前提的类似问题。这是伪代码，其中 n 是任意大小的整数：

sample_found = false
while(!sample_found) {
    if (rand(0,n) == 0) {
        sample_found = true
    }
}

在最坏的情况下，这将运行无限，对吧？我也不确定平均情况。

Answer 1

听起来您正在使用 IID Bernoulli trials to control looping, with a probability p=0.1 of continuing. Assuming that's the case, you can just use the Geometric distribution。

这个分布的平均值只是 1/p，所以 10，我会使用 quantiles 来进一步了解需要多少次抽奖才能完成。例如：

10% 的时间您希望立即完成
50% 的运行你需要循环 6 次或更少
90% 的运行以 21 个循环完成
99% 的运行完成 43 次循环

在 R 中计算，使用 qgeom(c(0.1, 0.5, 0.9, 0.99), 0.1)。

最坏的情况显然是无穷大，但实际上您不太可能循环 200 次。 1-pgeom(200, 0.1) 给出 6e-10，因此您可以期望循环迭代超过 10 亿次，然后才需要等待这么多次迭代。

具有不确定迭代次数的 while 大 O 循环

Big-O of while loop with an indeterminate number of iterations

random

big-o

time-complexity