嵌套 while 循环的大 O 符号解释

Question

我想知道以下 (java) 代码的大 o 表示法是什么：

while (n > 0) {
     while (n > 0){
        n-- ;
    }
 }

如果我使用 n = 10 它将在外循环中进行一次迭代，在内循环中进行 10 次迭代。
所以总共 11 次迭代 对吗？
如果我使用 n = 100 它将在外循环中进行一次迭代，在内循环中进行 100 次迭代。
所以总共 101 次迭代 对吗？
但这就是我卡住的地方。因为我认为符号是 O(n)。仅仅是因为我认为迭代几乎等于 n。但是不知道怎么证明？

我数学不太好，所以需要一个清晰的解释

Answer 1

它是 O(n)，因为外循环运行一次。当内循环完成时，外循环的条件也为假。因此外层循环对于 O 表示法并不重要。

Answer 2

通俗地说，对于正参数，外循环恰好进行一次迭代，因为在内循环中 n 减少到零。内循环将恰好进行 n 次迭代，因此内循环的运行时复杂度为 O(n)。总的来说，虽然外层循环的终止条件在句法上取决于n，但实际上它独立于n。整体复杂度可以看成O(n+c)，其中c是一个常量，表示外层循环的执行。但是，O(n+c) 等于 O(n).

您可能感到困惑的是，在您的术语中，您说的是 101 次迭代 的循环，实际上您指的是两个不同的循环。

Answer 3

是的，是 O(n)。然而，即使是简单算法的数学证明也并不容易。

你可以做的是应用最弱的前提条件来正式分析它。看到这个 https://en.wikipedia.org/wiki/Predicate_transformer_semantics#While_loop

非正式地，很容易看出在内部 while n >= 0 之后必须为真，而不管内部循环内部发生了什么。如果 n >= 0 则外部 while 将结束。由于这种情况在内部 while 之后每次都会发生（无论其内容如何），因此外部循环永远不会执行超过一次。

最弱的前提条件可以更正式地证明这一点，但如果你把它应用到更大的问题上，你肯定会头疼。不过很有教育意义。

嵌套 while 循环的大 O 符号解释

Big O notation explanation nested while loop

java

math

big-o