algorithm - 三种情况下的大 O 符号复杂度

Question

以下算法是否在 O(n) 时间内运行？

1

s=0
for(i=0; i<n; i++)
{
    for (j=0; j<n; j++)
    {
        s=s+i*j;
    }

    s=s+1
}

这是一个 O(n^2)，因为这里的性能与输入数据集 N 大小的平方成正比

2

 s=0
    for(i=0; i<n; i++)
    { if (i>20)
        for (j=0; j<n; j++)
        {
            s=s+i*j;
        }

        s=s+1
    }

3

 s=0
    for(i=0; i<n; i++)
    { if(i<4)
        for (j=0; j<n; j++)
        {
            s=s+i*j;
        }

        s=s+1
    }

您能解释一下 if 语句如何影响 O(n) 吗？在这两种情况下(#2 和#3)，第一个循环是 O(n)，如果 N > 20 或 N < 4，第二个循环将分别运行。但这如何影响复杂性？这些仍然是 O(n^2) 与 if i > 20减少 20^2 次操作，if i < 4少 4^2？ Big O 还假设 N 会趋于无穷大吗？

Answer 1

2

还是 O(N^2)。循环总共运行

20 + (N - 20) * N 次迭代(每次迭代都是常数)==> O (N^2)

3

O(N)。循环一共运行了

N * 4 + (N - 4) 次迭代(每次迭代都是常数)==> O(N)