Временная сложность для вложенного n / 2 - PullRequest
Новая
       7

Временная сложность для вложенного n / 2

0 голосов
/ 16 октября 2018

Я знаю, что сложность времени для вложенного цикла n равна O (n ^ 2).Но если у меня есть вложенный цикл, как показано ниже, 

for(i=0;i<n/2;i++)
  for(j=0;j<n/2;j++)
    ...
    ...

Как рассчитать сложность времени для этого кода.Это тоже O (n ^ 2)?Если да, то как?

1 Ответ

0 голосов
/ 16 октября 2018

Это тоже O (n ^ 2)?Если да, то как?

Да, это так.

Все, что вам нужно сделать, - это подсчитать общее количество итераций (которое по правилу продукта составляет n/2 * n/2 = n^2 / 4),и имейте в виду, что запись Big-O игнорирует константы.Асимптотический анализ отбрасывает константы, потому что они не имеют значения, когда n стремится к бесконечности.Другими словами, f(n) = n и g(n) = 2n являются линейными функциями, несмотря на то, что g растет быстрее, чем f.Асимптотический анализ касается только классов темпов роста.

См. Также:

...