Объяснение
Если метод f находится внутри O(g), где g является другой функцией, это означает, что в какой-то момент (существуют некоторые n_0 такие, что для всех n > n_0) функция f всегда будет выведите меньшее значение, чем g для этой точки. Однако g может иметь произвольную константу k. Так что f(n) <= k * g(n) для всех n выше некоторых n_0. Так что f разрешено сначала быть больше, если затем оно начинает уменьшаться и продолжает уменьшаться.
Мы говорим, f равен , асимптотически ограничен g. Асимптотически означает, что нам все равно, как f ведет себя в начале. Только то, что он будет делать, приближаясь к бесконечности. Поэтому мы отбрасываем все входы ниже n_0.
Иллюстрация
Иллюстрация будет такой:
Синяя функция k * g с некоторой константой k, красная - f. Мы видим, что сначала f больше, но затем, начиная с x_0, оно всегда будет меньше k * g. Таким образом f in O(g).
Определение
Математически это можно выразить как
что является обычным определением Big-O. Из объяснения выше, определение должно быть ясным. В нем говорится, что с определенного значения n_0 функция f должна быть меньше, чем k * g для всех входов. k разрешено быть некоторой константой.
Оба изображения взяты из Википедия .
Примеры
Вот несколько примеров, чтобы ознакомиться с определением:
n в O(n) (тривиально) n в O(n^2) (тривиально) 5n в O(n^2) (начиная с n_0 = 5) 25n^2 находится в O(n^2) (принимая k = 25 или выше) 2n^2 + 4n + 6 находится в O(n^2) (взять k = 3, начиная с n_0 = 5)
Примечания
На самом деле, O(g) - это набор в математическом смысле. Он содержит все функции с вышеупомянутым свойством (которые асимптотически ограничены g).
Итак, хотя некоторые авторы пишут f = O(g), это на самом деле неправильно и должно быть f in O(g).
Существуют также другие похожие наборы, которые отличаются только в направлении границы:
- Big-O: меньше равно
<=
- Small-o: меньше
<
- Биг-Омега: больше равно
>=
- Малый омега: больше
>
- Тета: Биг-О и Биг-Омега одновременно ( равно )