Учитывая, что f (n) = 10000000n и g (n) = n ^ 2. Почему f (n) есть O (g (n))?

Question

Я пытаюсь решить следующую проблему, но не уверен в объяснении, приведенном в решении. f2 (n) выглядит как O (n), а f4 (n) выглядит как O (n ^ 2). Почему же тогда f2 (n) есть O (f4 (n))?

Answer 1

Ваше текущее утверждение не соответствует действительности. Пример противоречия - f2(n) = n = O(n) и f4(n) = 1 = O(n^2). Но f2(n) не является O(f4(n)).

Однако, как уже упоминалось в ответе, f4(n) является квадратичным, а f2(n) является линейным, по определению символа big-Oh мы можем сказать,f2(n) = O(f4(n)).

Answer 2

Прочтите страницу Википедии о системе обозначений Big O, и вы поймете ее лучше. Неформально, описание функции в терминах обозначений больших О обычно дает только верхнюю границу скорости роста функции.

Учитывая, что f (n) = 10000000n и g (n) = n², когдаВы говорите, что f (n) - это O (g (n) ), это означает, что существуют c> 0 (например, c = 1) и n0 такие, что f (n) ≤ cg (n) всякий раз, когдаn ≥ n0.

Если f2 равно O (f4), это означает, что f2 растет асимптотически медленнее, чем f4.