Сложность блока else, содержащего цикл внутри блока цикла

Question

Я пытаюсь найти частоту каждого утверждения и большую букву этого метода.

Но я борюсь с остальной частью, я знаю, что мы принимаем наихудшую сложность, если и еще

Но логически, в этом случае, я должен умножить частоту внешнего цикла (n) на частоту цикла else (n + 1)?Хотя я знаю, что блок else будет выполняться только один раз, когда i = 0 Но когда мы следуем правилам, мы должны умножить его, поэтому я застрял здесь и не знаю, что делать в этом случае, яНадеюсь, вы, ребята, могли бы помочь мне Спасибо!

int i, j, sum = 0;
for (i = 0 ; i < n; i++)
if ( i != 0)
    Sum += i;
else
    for (j = 0 ; j< n; j++)
        Sum + = j;

Answer 1

Итак, у вас есть цикл O (n), а внутри него есть O (n).Но в вашем коде мы выполняем оператор else только один раз.

Таким образом, у вас есть цикл for, и внутри if вы выполняете O (1) работу (n - 1) раз и один раз (i == 0) вы выполняете O (n) работу (когда достигается оператор else)

Таким образом, сложность будет O (n) = (n - 1) * O (1) + O (n) ~O (2n), что также является O (n), потому что мы отбрасываем константы при асимптотическом анализе.