Сложность обозначений Big 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) с <code>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)