Итак, давайте практиковать идею сравнения двух полиномов,
например, и решить,
принадлежат ли они одному и тому же классу.
Таким образом, мы определяем сам класс.
Для того, чтобы сделать это, мы начинаем с
идеи Big-o нотации,
которая иногда обозначается
подчеркиванием o в рукописном тексте.
Процедура здесь выглядит следующим образом.
В принципе, предполагает, что у нас есть две из наших функций
, как х в квадрате и 5х в квадрате минус 100х.
Мы, как-то, говорим
о верхней границе
одной функции по отношению к другой.
В принципе, это означает, что одна функция
больше, чем в некотором фиксированном
количестве раз, чем другая.
Другими словами, нам нужно записать здесь неравенство.
В принципе, предположим, что у нас есть
некоторая окрестность данной точки, например, a.
Мы называем одну функцию
Big-O из другой функции в этом районе.
Если есть какая-то постоянная,
положительная константа, C такая как
отношение, абсолютное значение отношения
функций f и g не превышает
этого значения c. Так давайте рассмотрим,
например, наш случай.
У
нас есть х в квадрате, например, назовем его f x в квадрате,
g - 5x в квадрате минус
100x, и я предположим, что х приближается к бесконечности.
То, что мы собираемся сделать, мы собираемся сказать,
что какая-то функция больше, чем
другая в некоторой окрестности бесконечности.
Нам нужно записать что-то
вроде абсолютного значения f
меньше или равно какой-то
константы, умноженной на абсолютное значение g, хорошо?
Другими словами, x в квадрате меньше или больше, чем какая-то
константа, умноженная на Эпсилон
[неразборчивый] 5x в квадрате минус 100x.
Очень легко понять, какая
константа на самом деле хороша для нас здесь.
Например, начнем с
константы c, равной единице.
Ну, очевидно, что это
так, потому что если мы просто предположим, что c равняется одному.
Таким образом, мы получаем x в квадрате с одной стороны и
5x квадраты минус 100x с другой стороны.
Если мы вычитаем x в квадрате
с обеих сторон, таким образом, мы получаем функции,
которые явно положительны с какой-то точки,
потому что мы смотрим на
параболические функции с положительным.
Мой коэффициент, таким образом,
есть корень и после этого корня
у нас есть только положительные значения.
Таким образом, это неравенство сохраняется и один.
F является Big-o в сторону G,
это был один из примеров.
Один код легко утверждает, что если нам
нужно поменять эту функцию, которая все еще удерживается,
просто потому, что вместо того, чтобы писать c равен единице.
Давайте попробуем сделать это интерпретировать здесь.
Так что, по сути, нам нужно что-то доказать, вот так.
Поэтому для того, чтобы сделать каждый,
мы должны рассмотреть другой c naught
, маленький, но большой.
Итак, в основном, мы начинаем с, как c равняется пяти.
Тогда мы получим хороший результат здесь.
Но это не всегда так, потому что, например,
давайте посмотрим на более интересный случай.
Например, что делает [неразборчивые] функции,
синус x и x,
поскольку x приближается к нулю? Мы знаем что?
Они в основном эквивалентны, как следует ожидать,
что синус х в основном является большим о х.
Это довольно легко, потому что
абсолютное значение синуса х, как мы заявили, в
то время как мы говорили о нашем втором важном пределе,
теперь больше, чем модель х,
потому что абсолютное значение х
- это фактически площадь сектора,
а синус x - площадь треугольника соответственно.
Таким образом, мы считаем, что,
используя константу c, равную единице,
мы получаем это абсолютно правильно.
Но что, если мы заменим точку интереса от нуля,
скажем, бесконечность?
Прежде всего, идеи о том, что синус х
является большим о к х,
все еще сохраняются в этой самой точке, потому что в основном
синус х не больше одного и х является наибольшим.
Как вы можете себе представить, x приближается к бесконечности.
Таким образом, это неравенство по-прежнему сохраняется,
например, за ту же константу, равную единице.
Но если мы изменим его,
если мы изменим две функции,
то мы получим 380,
[неразборчиво] здесь, потому что синус
х и х не связаны во времени.
Потому что синус х все еще, извините,
я сказал вам, что нам
нужно менять функции и не делали этого.
Так что это отличный обман.
Это менее обманчиво.
Таким образом, x является big-o из синуса х.
Таким образом, в основном, синус х
ограничен одним и минус один и х не ограничен.
Таким образом, если мы попытались придумать идею
, что х должен быть меньше какой-то константы,
умноженный на синус х, и мы говорим, что эта
константа, например, 10,000.
Так в чем же ошибка?
Тогда мы можем, например,
взять х больше, чем два, так как n
, это уравнение, мы почти
определенно просто упасть, и
это крайне не так.
Это неправильно. Поэтому, когда
мы говорим о большой нотации,
вам всегда нужно учитывать порядок здесь.
Какую функцию, в отношении какой функции? Это Биг-О?