Построим две функции удовлетворяющие:
- непрерывны;
- монотонно возрастают;
- и .
asymptotics
landau-notation
Джесси
источник
источник
Ответы:
Есть много примеров для таких функций. Возможно, самый простой способ понять, как получить такой пример, - это создать его вручную.
Давайте начнем с функции над натуральными числами, так как они могут непрерывно пополняться действительными числами.
Хороший способ убедиться, что и g ≠ O ( f ), состоит в чередовании их порядков. Например, мы могли бы определитьf≠O(g) g≠O(f)
Тогда мы могли бы ведут себя противоположным по коэффициентам и эвенов. Тем не менее, это не работает для вас, потому что эти функции не монотонно растут.g
Однако выбор был несколько произвольным, и мы могли бы просто увеличить величины, чтобы иметь монотонность. Таким образом, мы можем придумать:n,n2
, а g ( n ) = { n 2 n - 1 n является нечетным n 2 n n является четнымf(n)={n2nn2n−1n is oddn is even g(n)={n2n−1n2nn is oddn is even
Понятно, что это монотонные функции. Кроме того, , поскольку на нечетных целых числах f ведет себя как n 2 n, в то время как g ведет себя как n 2 n - 1 = n 2 n / n = o ( n 2 n ) , и наоборот по вечерам.е( n ) ≠ O ( г( н ) ) е N2 н грамм N2 n - 1= n2 н/ n=o( n2 н)
Теперь все, что вам нужно, это завершить их до действительного числа (например, путем добавления линейных частей между целыми числами, но это действительно не относится к делу).
Кроме того, теперь, когда у вас есть эта идея, вы можете использовать тригонометрические функции для построения «закрытых формул» для таких функций, поскольку и cos колеблются и достигают максимума в чередующихся точках.грех соз
источник
Хорошая иллюстрация для меня: http://www.wolframalpha.com/input/?i=sin%28x%29%2B2x%2C+cos%28x%29%2B2x
g ( n ) = 2 x + c o s ( x ) f ≠ O ( g ) g ≠ O ( f )
источник