java - 嵌套 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

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

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