大O符号解释嵌套while循环

Question

我想知道以下(java)代码的重要符号是什么:

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次迭代,实际上你指的是两个不同的循环.