Я правильно рассчитываю биг-о? - PullRequest
0 голосов
/ 31 марта 2020

Следующие циклы:

for(var i = 0; i < A; i++) {
  for(var j = 0; j < B; j++) {
    for(var k = 0; k < C; k++) {
      //not concerned with instructions here
    }
  }
}

Как я понимаю, каждая сложность l oop равна 2n+2, поэтому на основании этого я вычисляю сложность вышеупомянутых вложенных циклов как (2A+2)*((2B+2)*(2C+2)). Это правильно? если да, то как мне извлечь из этого биг-о?

Редактировать

На самом деле неправильно. Вместо правильного (2A+2)*(2B+2)*(2C+2) (проверьте ответ), распределение внешней сложности l oop не требовалось.

Ответы [ 2 ]

1 голос
/ 31 марта 2020

Самый внешний for-l oop работает в общей сложности A раз. Для каждой итерации второй уровень для -l oop выполняется B раза, каждый раз вызывая C итерации пропущенных инструкций.

Таким образом, сложность времени составляет O(A * B * C).

0 голосов
/ 31 марта 2020

Константы игнорируются при расчете сложности времени

   O((2A+2)*((2B+2)*(2C+2)))
=> O((2A)(2B)(2C))
=> O(8*ABC)
=> O(ABC)
...