2 
int a = 0;  //1 unit
for (int b = 0; b < N; b++) // (1 + N + N) = 2n + 1
    for (int c = b+2; c > 0; c--) //2 + (N+1) + N = 2N+3
        a += b*c; //3 units

产量：1 + (2n+1)(2n+3) = 4n^2+8n+4

我是算法分析的新手，我不能 100% 确定这是正确的。谁能帮助我，让我知道我这样做是否正确？如果没有，请指出我哪里出错了。

我几乎计算出了最坏情况下的运行时间4n^2+8n+4

4

5 回答 5

1

内循环对外循环中的每个 b 值执行 b+2 次。所以内循环执行的总次数等于 (2 + 3 + 4 + .... + (N+2))。每次它执行 3 个单位的工作。所以内部循环执行的总时间是 [ ((N+2) (N+3)/2 ) - 1 ] * 3 。

但通常我们会渐近地测量运行时间，这就是 Big O (N ^ 2)

于 2013-06-10T05:54:03.710 回答
1

通常，使用大 O 表示法时，系数会被忽略，算法按其增长最快的函数进行分类。在这种情况下，您有两个O(n)嵌套的循环。嵌套是乘法的，给算法O(n²)又名“二次”复杂性。有关大 O 表示法和计算复杂性的 Wikipedia 文章可能会为您提供进一步阅读的起点。

于 2013-06-10T05:54:08.967 回答
1

如果你想说内循环中的语句需要 3 个单位，那么内循环需要 ( b + 2 ) * 3 个单位。现在，如果我们让 b 的范围从 0 到 N - 1 并求和，我们得到

( 0 + 2 ) * 3 + ( 1 + 2 ) * 3 + (2 + 2) * 3 + ... + ( 2 + N - 1 ) * 3

= 3 * ( 2 + 3 + 4 + 5 + ... + ( N + 1 ) )

= 3 * ( ( 1 + 2 + ... + N+1 ) - 1)

= 3 * ( ( ( N +1 ) ( N + 2 ) / 2 ) - 1 )

= 3 * ( N^2 + 3*N + 2 - 2 ) / 2

= 3/2 * N^2 + 9/2 * N

请注意，我没有将循环标头中执行的操作算作操作，通常不会这样做。事实上，人们通常只会计算执行次数最多的最昂贵的操作（在这种情况下是乘法）。

顺便说一句，我使用了前 n 个整数之和为 n ( n+ 1 ) / 2 的事实

于 2013-06-10T05:55:03.203 回答
1

让我们考虑您的代码，

for (int b = 0; b < N; b++)
    for (int c = b+2; c > 0; c--) 
        a += b*c;

外循环执行N次数，而内循环b+2每次执行外循环迭代的次数。

因此，该语句a += b*c;总共执行了2 + 3 + 4 + ... + N+2多次。

因此，该指令总共执行了([1 + 2 + 3 + ... + N+2] - 1)多次。

它等于，[(N+2)(N+3)]/2-1因为前 N 个整数的和是N(N+1)/2。

给定代码的复杂度是 Θ(((N 2 +5N+6)/2) - 1)，也就是Θ(N 2 )。

于 2013-06-10T08:19:12.553 回答
0

你的例子：

int a = 0;  // 1

for (int b = 0; b < N; b++) // 1 + (N+1) + N
{
    for (int c = b+2; c > 0; c--) // 1 + (((N+2)*(N+3)/2)+1) + ..) * N
    {
        a += b*c; // 3 * ((N+2)*(N+3)/2) * N
    }
}

做数学我们得到：

= 1 + 1 + (N+1) + N + 1 + [(((N+2)*(N+3)/2)+1) + ((N+2)*(N+3)/2)) * N] + [3 * ((N+2)*(N+3)/2) * N]

= 4 + 2 N + 1/2 N^3 + 3 N^2 + 11/2 N + 4 + 9 N + 15/2 N^2 + 3/2 N^3

= 8 + 33/2 N + 21/2 N^2 + 2 N^3

给我们O(N^3)

于 2013-06-10T06:28:30.163 回答