Временная сложность циклов с операторами If

Question

Если у меня есть al oop, например:

for(int i=0;i<n;i++)
{
    if(i%2==0)
    {
        // do something
    }
}

Какая будет временная сложность, если временная сложность кода // делать что-то, скажем, линейная.

Answer 1

Когда вы говорите о временной сложности, вы обычно говорите о худшем случае, поэтому вы считаете, что условие в if истинно, а затем решаете сложность.

В данном коде псевдо выполняется do something в половину времени, так что O(n/2) => O(n) раз. Таким образом, do something выполняется O (n) раз. Если do something - линейное время, то фрагмент кода имеет сложность O(n^2).

Answer 2

Оператор if выполняется каждую итерацию и имеет постоянное время. Давайте предположим, что защищенный код является линейным. Это будет выполнено половину времени, но этот коэффициент 1/2 уменьшается из-за того, как работает большая O-нотация. Следовательно, общая сложность времени равна квадратичной c или O(n*n).