无限循环的大O？

Question

考虑以下代码：

int value = 0;

while(getRandomNumber() != 1000) {
    value++;
}

return value;

上述代码的大 O（最坏情况、最佳情况和平均情况）是什么？

Answer 1

如果 some_statement 在整个循环过程中为假并且保持为假，那么，是的，循环是无限的并且具有 O(Infinity) 复杂度。然而，一旦 some_statement 变为真，循环就变得有限。它甚至可以是 O(1) - 如果 some_statement 在开始时为真，则为常量。

Answer 2

在谈到复杂性时，n 是以位为单位的输入大小。这里，有no输入。所以 n 是固定的，等于 0。所以技术上没有复杂性，因为输入大小不能有任何变化。

但是您可以提出以下问题：循环平均最多或最少执行多少次...

Answer 3

最坏的情况是O(∞)，最好的情况是0(1)。
是的，但是每个算法都有复杂性O(∞)，因此不是很有用的信息。

Answer 4

您要查找的是预期时间复杂度。在您的特定情况下，这是 geometric distribution.

的预期值（平均值）

例如，循环的预期迭代次数为：

E[iterations] = (1 - p) / p

其中 p 是恰好得到 1000 的概率。

p = P(X=1000)

Answer 5

你在这里的问题没有多大意义。首先大O符号依赖于输入，这里你的算法根本没有输入。

此处的执行时间取决于 getRandomNumber 的可能值集及其基础分布。

例如，如果您的 RNG returns 号码来自 [1 to 100] - 算法永远不会完成。另一方面，如果它以相同的概率仅生成 1000 和 1001，则平均需要 2 次迭代才能完成。最坏的情况是无穷大，但这根本没有任何意义，因为它不太可能。

Answer 6

总结

其他人指出了很好的信息，但未能解决一些非常重要的问题。一旦引入随机化，您就需要查看预期时间，而不是确定性分析。回答您的问题：

最佳情况： Ω(1)
更坏的情况： O(∞)
平均情况：请参阅下面的预期分析。

最佳案例说明

注意最好的情况是它是 big omega，而不是 big O (https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-omega-notation)

预期分析

引入随机化后，您将不再依赖确定性分析。相反，你开始处理 "expected analysis"。正如 Mateen 指出的那样，您的实例可以用几何分布来解决。由于我不知道您的获取随机数函数可以取值的范围 return （也不知道数字的分布），因此我们无法直接回答您的问题。 Mateen 的分析看起来不错，因为他没有假设您获得 1000 的概率。

旁注

对于其他类型的随机问题，您可以使用其他工具，例如Marchov Chains (https://en.wikipedia.org/wiki/Markov_chain). I've seen tools like these used in analysis of Randomized Online Algorithms (https://en.wikipedia.org/wiki/Adversary_model)，如果您对此感兴趣，那么链接应该为您提供丰富的其他链接阅读。

随机化的引入为算法分析增添了新的乐趣。希望这对您有所帮助，祝您玩得开心:)

无限循环的大O？

Big O of an infinite loop?

algorithm

big-o

time-complexity