找到大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){

我真的不确定如何展示我的工作.我很确定algorthim是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)每个循环的复杂程度