预期时间复杂度为 O(n^2)，但结果为 O(n)。有人能解释一下为什么吗？

Question

以下代码的时间复杂度应该是多少？我试图思考并提出 O(n ² ) 但输出说它是 O(n)。有人可以通过代码解释吗？

for(int i = 0; i < n; i++){
    for(; i < n; i++){
        cout << i << endl;
    }
}

Answer 1

代码的复杂度是 O(n)。

为什么？

因为，即使您编写了两个 for 循环，这可能让您认为复杂性是 O(n ² )，但您的代码实际上是一个 for 循环，例如：

for (i = 0; i < n; i++){
    std::cout << i << std::endl;
}

一旦内部 for 循环完成，i等于n，因此i < n不再满足外部 for 循环的条件。