сложность времени относительно elses?

я не могу найти никакой информации об этом, поэтому я надеюсь, что вы можете мне помочь. вопрос касается вложенных else-if в циклах for и расчете временной сложности.

общий код у меня есть:

for(i=0; i<n; i++)
{
  if(___);
  else 
  {
    if(___);
    else(___);
  }
}

каждый (___) является сложностью, если O (1). проблема, с которой я сталкиваюсь, заключается в том, что я продолжаю путаться в том, как вычислить неупрощенную сложность big-O из-за else и вложенного if-else. это O(n*1+1+1+1)? или, может быть, O (n * 1 + 1 * (1 + 1))? как мне к этому подойти?


java nested-if time-complexity big-o
person Eric Parker    schedule 08.06.2018    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Поскольку O(1) асимптотически незначителен по сравнению с O(n), не имеет значения, какой из них вы используете, результат все равно будет O(n).

Если бы вы сделали худший случай, это было бы O(n) * [O(1) + O(1) + O(1)] = O(2n) => O(n), поскольку для каждой итерации цикла вы выполняете каждое из условных выражений, поэтому это n * 2 операций.

person Sam    schedule 08.06.2018
comment
для лерификации я смотрю на первое if и вижу, что это O (1), а затем я добавляю к нему первое else, которое, как я знаю, состоит из 2 операторов O (1) (второе if и еще), и поэтому мой окончательный расчет O (n) * [O (1) + O (1)]? - person Eric Parker; 08.06.2018
comment
ну, так что у каждого if есть условие (которое само по себе имеет сложность) и последующие операции. Скажем, каждое условие имеет сложность O(1), а каждый код if/else имеет сложность O(1). В худшем случае нужно проверить, если (O(1)), перейти к соответствующему else, выполнить операцию else, которая является другим условием if (O(1)), затем перейти к последнему else, который будет O(1). Таким образом, в худшем случае будет O(1) + O(1) + O(1) для каждой итерации. - person Sam; 08.06.2018