algorithm - 对于这段代码，这种最坏情况分析是否正确？

Question

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

yield :1 + (2n+1)(2n+3) = 4n^2+8n+4

我是算法分析的新手，我不能 100% 确定这是正确的。任何人都可以帮助我，让我知道我是否做对了？如果不是，请指出我哪里出错了。

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

Answer 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²+5N+6)/2) - 1) 这就是 Θ(N²).