c - 运行时分析

Question

int i, j;

for(i=0; i<n*n; i++) 
{
    if(i % n == 0)
        for(j=0; j<n; j++)
             x++;
    else 
        x--;
}

我是运行时分析的新手，所以我只是在这里检查我的答案，看看我是否有正确的想法。

我必须为该段找到一个严格的运行时界限并给出一个推理。

我想出了 O(n²)。

我的理由是因为它运行第一个 for 循环 n² 次。如果 i 可以被 n 整除，它只会运行第二个 for 循环。

这是可以的还是我的分析完全错了？

Answer 1

外循环运行n²次数。每n第 - 次运行（因此 n 总共运行一次），它会启动另一个循环，该循环运行n时间。这n² + n * n等于等于2n²O(n²) 的运行时间。