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

Question

Если у нас есть цикл с приведенным ниже, и мы знаем, что c = 5:

for ( int i = 0 ; i < c; i++ )
{
  // some logic
}

Мы получим O (1).

, если у нас есть другой цикл:

for ( int i = 0 ; i < n; i++ )
{
  // some logic
}

Мы получаем O (n),

, но что произойдет, если у нас есть вложенные циклы, такие как:

for ( int i = 0 ; i < n; i++ )
{
   for ( int j = 0 ; j < c; j++ )
   {
     // some logic
   }

}

какова будет временная сложность этого?

Answer 1

Эти оба цикла имеют сложность O (c * n).

Answer 2

Сложность времени - это время, затрачиваемое кодом на выполнение.Таким образом, в случае вложенных циклов, которые вы упомянули, время выполнения кода будет равно c*n.

Также сложность времени представлена ​​в Big O нотации .Так что это будет зависеть от размера c.

Если c является постоянной величиной, такой как 1 или 5 , то общая сложность будет O(n) (потому что O(постоянная * n) = O (n) ).Однако, если c имеет порядок n (то есть c = n ), то сложность будет O(n*n).

Answer 3

Если бы оба были O (n), вы бы выполняли внутреннее O (n) n-раз, давая O (n * n) = O (n ^ 2).Так как один - O (n), а другой - O (1), вы выполняете O (1) n раз, давая O (n * 1) = O (n)

Итак, сложность временибудет O (n)