сложность времени в отношении остальных?

Question

Я не могу найти какую-либо информацию об этом, поэтому я надеюсь, что вы можете мне помочь.вопрос касается вложенных циклов 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))?как мне к нему подойти?

Answer 1

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

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