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：我们从 Z 开始2*y，所以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

将其绘制在 lin-log 图上，您会得到一条非常直线。

当你取 的比率时algorithm(400) / algorithm(300)，你得到 2.369。而当你服用时(400/300)^3，答案是2.370。我认为这足以令人信服。

Answer 2

按照下面的正式步骤（我希望您对 Sigma 表示法感到满意），您将能够获得算法的确切增长顺序：