Блог

Я пытаюсь изучить сложности времени. Я столкнулся с проблемой, которая сбивает меня с толку. Мне нужна помощь, чтобы понять это:

my_func принимает входные данные массива размером n. Он проходит три цикла for. В третьем цикле он вызывает другую функцию, которая выполняется O(1) раз.

 def my_func(A): 
  for (int i=1; i<n; i  )
    for (int j=1; j<i; j  )
      for (int k=1; k<j; k  )
        some_other_func(); 
 

Мои Вопросы:

1. Прав ли я, если скажу, что общее количество шагов, выполняемых my_func (), равно O(n^3), потому что:
   1. первый цикл for идет от 1 до n-1
   2. второй цикл for идет от 1 до n-2
   3. третий цикл идет от 1 до n-3
2. Что такое асимптотическое время выполнения и каково асимптотическое время выполнения для приведенного выше алгоритма?
3. В чем смысл следующего:

Прав ли я, если скажу, что общее количество шагов, выполняемых my_func (), равно O(n^3)

Да, его временная сложность такова O(n^3) .

Что такое асимптотическое время выполнения и каково асимптотическое время выполнения для приведенного выше алгоритма?

Предельное поведение времени выполнения алгоритма, когда размер задачи стремится к бесконечности [здесь]. например:

 lim (n^3) when n-> infinite 
 

В чем смысл следующего

1-й, он показывает зависимые переменные k->j->i как есть. Более того, что, если бы все переменные(i, j, k) были независимы друг от друга? например, константа x , тогда каждый цикл будет повторяться несколько x раз, но здесь k зависит от j, а j зависит от I. например:

 x(x(x)) = sigma(sigma(sigma(O(1))))
 

2-й, исследуется временная сложность при больших входных данных. Следовательно, либо переменные зависят, либо не зависят, большой O будет O(n^3) .

Да, это O(n^3), и это асимптотическое время выполнения. Выражение суммы в конце означает то же самое, что и три вложенных цикла вверху, предполагая, что «some_other_func ()» sum = sum 1 .