0

这是片段：

sum1=0;
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        sum1++
sum2=0
    for(k=1;k<=n;k*=2)
      for(j=1;j<=k;j++)
        sum2++

以下是答案：

2 个赋值语句 – 每个第一个嵌套循环 O(1) – O(n2) 第二个嵌套循环 – O(n) 代码片段的运行时间复杂度 = O(1) + O(n^2) + O(1) + O (n) = O(n2)

但这是我的解决方法：

2 个作业：- O(1)。第一个嵌套循环：O(n*n)=O(n^2) 第二个嵌套循环：

外循环运行 n 次。现在内循环将被执行 (1+2+3+.....+(n-1)+n) 次，得到 n(n+1)/2 =O(n ^2)

总运行时间 = O(n^2)+O(n^2)+O(1)=O(n^2)

是的，我做了一些研究，发现了以下内容：

在循环中，如果索引在每次迭代中跳跃量增加，则序列的复杂度为 log n。

在那种情况下，我想第二个循环将具有复杂性 (n-1)/2*logn...这将等于 O(n*log n)。

我真的对第二个循环感到困惑，它应该是 O(n)..O(n^2) 还是 O(nlogn)..

请帮忙

4

1 回答 1

0

由于你 k 每次增加一倍。你的计算不正确。它应该是 (1+2+4+....n/2+n)

     for(k=1;k<=n;k*=2)

所以，O(nlogn) 是对的。

于 2012-05-08T11:38:16.677 回答