c - 三环复杂度

Question

谁能告诉我下面代码的复杂度并解释一下计算过程？

int count=0;
for(int i=0; i<n;i++)
    for(int j=i; j<n;j++)
        for(int k=j;k>i;k--)
            count++;

谢谢

Answer 1

这只是一个“简单”的数学运算:

对于第一个循环，它非常简单，它将执行 n 次迭代。

第二个循环并没有那么复杂:

• i=0:您将有 n 次迭代。
• i=1:n-1 次迭代
• i=2:n-2 次迭代
• ...
• i=n-1:1 次迭代

它的总和是n(n+1)/2。

对于第三个循环，我们只对 j>i 感兴趣:

• i=n-1:您有 0 次迭代。
• i=n-2:1次迭代，也就是当j=n-1
• i=n-3:当 j=n-1 时 2 次迭代和 1 次迭代时 j=n-2
• i=n-4:3迭代时j=n-1，2迭代时j=n-2，1迭代时j=n-3
• ...
• i=0:j=n-1时n-1次迭代，n-2次迭代当 j=2, ..., 1 迭代时 当 j=1

运行时间为:

O((n-1)n/2 + (n-2)(n-1)/2+...+(n-n+2)(n-n+1)/2+(n-n+1)(n-n)/2)=O((n-1)*(n^2)/2)=O(n^3)