algorithm - for循环的计算复杂度-自相矛盾

Question

通过分析一个程序的运行时间，我有一个矛盾。例如，考虑以下代码:

for(int i=0;i<n;i++)
{
    for(int j=0;j<n;j++)
    {
         .....
    }
}

这里，第一个 for 循环的计算复杂度是 O(n²)，第二个循环是 O(n)。但是，第二个循环执行了 n² 次，而第一个循环执行了 n 次。例如，如果我们将 cout 语句放在内部循环中，它会输出 n² 次，但是如果我们将 cout 语句放在第一个循环内部但内部循环之外的某处，它会输出 n 次。那为什么我们说内层循环的复杂度是O(n)，而外层循环的复杂度是O(n²)。我们说外层循环的复杂度是O(n< sup>2) 但它执行了 n 次，为什么会这样？ 我做错了什么吗？谢谢。

Answer 1

内层循环执行n次，耗时O(n)。外循环执行内循环 n 次，但您必须考虑这 n 次外循环执行中每一次的内循环成本。这使得 O(n * O(n)) = O(n^2)。