17n ^ 2 + 5n ^ 3 в нотации Биг-Омега

Question

Вопрос в названии:

Я понял, что Большой-О есть

O (n ³ ).

Как это будет представлять наивысшую степень полинома.И наихудший случай сложности времени.

По показаниям дозы Биг-Омега означает самую низкую степень?т.е.

Ом (n ² )

, если это так, как мы можем оправдать игнорирование 3-й степени?

Спасибо

Answer 1

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

Когда мы говорим, что f = O(g), это означает, что функция f не растет быстрее, чем g (когда постоянные факторы не учитываются).Итак, 17n^2 + 5n^3 = O(n^3), но это также тот случай, когда 17n^2 + 5n^3 = O(n^4), 17n^2 + 5n^3 = O(n^5) и 17n^2 + 5n^3 = O(18036523n^38576), но это не тот случай, когда 17n^2 + 5n^3 = O(n^2.9999999).

Когда мы говорим, что f = Omega(g),это означает, что функция f не растет медленнее, чем g (когда постоянные факторы не учитываются).Итак, 17n^2 + 5n^3 = Omega(n^3), и 17n^2 + 5n^3 = O(n^2), и 17n^2 + 5n^3 = O(n), и 17n^2 + 5n^3 = O(1), но это не тот случай, когда 17n^2 + 5n^3 = O(n^3.000001).

Так что, если вы хотите быстрое правило, это то, что f = O(g) если наивысшая степень f равна <=, наивысшая степень g и f = Omega(g), если наивысшая степень f равна >= наивысшая степень g.