Блог

Если у вас есть функция линейной сложности, которая выполняется только один раз в конце цикла, какова будет сложность конечной функции?

 def f(n):  for i in range(0,n):  if i==n-1:  some_linear_complexity_function()  return  

Будет ли сложность равна 0(n) или O(n^2)? Спасибо.

Функция, которую вы определили, практически эквивалентна следующему коду:

 def f(n):  for i in range(0,n-1):  continue # do nothing  some_linear_complexity_function()  return  

Теперь, предполагая, что some_linear_complexity_function это зависит от того же n , for что и цикл, временная сложность f(n) будет O(n) .

Однако, если some_linear_complexity_function это зависит от какого-то другого значения m , временная сложность f(n) на самом деле будет O(max(m,n)) .