Итак, во время моей лекции мой профессор продемонстрировал, как решить эту проблему ...
Prove n^2 + 2n + lgn = O(n^2)
Так что для этой проблемы, если я прав, я могу заменить lgn и 2n на n ^ 2, потому что они растутбыстрее, чем те условия.После этого мы получим n^2 + 2n^2 + n^2 as our g(n)
0 <= n^2 2n + lgn <= n^2 + 2n^2 + n^2 for all n >= 1
Однако разрешено ли это только при проверке вопросов большого О, или же можно использовать ту же методологию при попытке доказать Большую Омегу?
Итак, сказанное приводит нас к этой проблеме ...
Prove 2n^3 - 3n^2 + 2n is Big Omega (n^3)
Для этой проблемы он полностью избавился от -3n ^ 2 и поменял местами только 2n с n ^ 3.Итак, после выполнения всего этого g (n) будет следующим:
2n^3 - 3n^2 + 2n >= 2n^3 - n^3 for all n >= 3
Почему -3n ^ 2 не было заменено на n ^ 3?