0

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

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

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

4

3 回答 3

1

内部循环执行 n 次，耗时 O(n)。外循环执行内循环 n 次，但您必须为这 n 次外循环执行中的每一个计算内循环的成本。这使得它 O(n * O(n)) = O(n^2)。

于 2013-02-26T10:05:02.547 回答
1

外循环将运行 n 次，内循环将运行 n 次，每次外循环迭代使内循环运行 n^2 次。因此，内部循环中的语句将被执行 n^2 次。

于 2013-02-26T10:05:10.997 回答
0

假设 n = 7 ; 然后

for(int i=0 ; i< 7 ; i++) //time complexity is : (1) + (7+1) + (7)
{
    for(int j=0;j<7;j++) //  time complexity is: (1) + [(7+1)+(7+1)+(7+1)+(7+1)+(7+1)+(7+1)+(7+1)] + (7)
    {
         .....
    }
}

总时间复杂度= [2+2(7)] + [1 + (7+1)^2 + 7]

现在替换 7 = n ; 我们将得到

总时间复杂度= [2+2n] + [1 + (n+1)^2 + n] = 2 + 2n + 1 + (n^2 + 2n + 1) + n = n^2 + 5n + 4

这里的主导项是 n^2。所以最坏的情况是O(n^2)

于 2013-08-23T16:24:32.900 回答