c - 求大 O 时间复杂度

Question

i = 1;     
while (i <= n) {
     j = n - i;
     while (j >= 2) {
         for (k = 1; k <= j; k++) {
             s = s + Arr[k];
         }
         j = j - 2;
     }
     i = i + 1;
}

让我困惑的部分是它说的地方

j = n - i;
while(j >= 2){

我不太确定如何展示我在那部分的工作。不过，我很确定该算法是 O(n^3)。

Answer 1

为了看得更清楚，你可以稍微简化一下:

for(i = 1; i <= n; i++)
{
    for(j = n - i; j >= 2; j -= 2)
    {
        for(k = 1; k <= j; k++)
        {
            s = s + Arr[k];
        }
    }
}

现在事情应该更简单了

• for(i = 1; i <= n; i++) : O(n) [实际上恰好执行 n 次]
• for(j = n - i; j >= 2; j -= 2) : (n-1)/2在第一次迭代中，(n-3)/2在第二个等等... O(n)
• for(k = 1; k <= j; k++) n-2在第一次迭代中，n-3在第二个等等... O(n)
• s = s + Arr[k]; 【操作简单】:O(1)

将每一步相乘，得到 O(n^3)

如果您仍然遇到问题，我建议您使用不同的 n 运行此代码的一些模拟。值和循环内的计数器。希望您能够看到 O(n) 是如何实现的 是每个循环的复杂度