c - 需要帮助找出该算法的复杂性

Question

您好，我需要帮助找出该算法的复杂性。您能否逐行回答复杂性，而不仅仅是最终结果？

算法如下:

int algorithm(int x)
{
    int y = 1;
    while (y <= x-1)
    {
        int z = y*2;
        while (z <= x)
        {
            int w = 1;
            while (w <= z)
            {
                w++;
            }
            z++;
        }
        y++;
    }
}

如有任何帮助，我们将不胜感激!

谢谢

Answer 1

int algorithm(int x)
{
    int y = 1;
    while (y <= x-1)    // <<< loop 1
    {
        int z = y*2;
        while (z <= x)  // <<< loop 2
            int w = 1;
            while (w <= z) // <<< loop 3
            {
                w++;
            }
            z++;
        }
        y++;
    }
}

让我们分解一下。

循环 1:绕 (x-1) 次:我们称之为 O(x)。简单。

循环 2:我们以 2*y 开始 Z，因此 2, 4, 6, ... 从那里开始直到 x >。让我们把它们加起来:

sum((x-2) + (x-4) + (x-6) + ... + (x - x)) =
x * x / 2 - 2 * (1+2+3+...+x/2) =
x * x / 2 - 2 * (x/2)*(x/2+1) / 2 ~
x * x / 2 - x * x / 4 =
x * x / 4
= O(x^2)

现在是最内层循环:它从 w = 1 到 w = z；所以它循环 z 次。我们知道

z = 2, 4, 6, ... x

因此，最里面的循环添加了一些 x 的顺序(x/2...相同的东西)。

将循环 3 的 O(x) 与循环 2 的 O(x^2)(包括第一个循环的效果)相结合，我们得出结论，“算法”的阶数为 x^3。为了进行验证，我们可以修改您的代码:

#include <stdio.h>

int algorithm(int x)
{
    int c = 0;
    int y = 1;
    while (y <= x-1)
    {
        int z = y*2;
        while (z <= x)
        {
            int w = 1;
            while (w <= z)
            {
                c++; // count complexity
                w++;
            }
            z++;
        }
        y++;
    }
    return c;
}

int main(void) {
    int ii;
    for(ii = 200; ii <= 400; ii+=10) {
      printf("%d   %d\n", ii, algorithm(ii));
    }
}

输出为:

200   1338350
210   1549030
220   1780735
230   2034465
240   2311220
250   2612000
260   2937805
270   3289635
280   3668490
290   4075370
300   4511275
310   4977205
320   5474160
330   6003140
340   6565145
350   7161175
360   7792230
370   8459310
380   9163415
390   9905545
400   10686700

将其绘制在线性对数图上，您会得到一条非常直线。

当您计算algorithm(400)/algorithm(300)的比率时，您将得到2.369。当您采用 (400/300)^3 时，答案为 2.370。我认为这足以令人信服。