c++ - 预期时间复杂度为 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因此外部 for 循环的条件 i < n不再满足。