Построить две функции и удовлетворяющие

19

Построим две функции удовлетворяющие:е,грамм:р+р+

  1. е,грамм непрерывны;
  2. е,грамм монотонно возрастают;
  3. еО(грамм) и .граммО(е)
Джесси
источник
2
Рассматривали ли вы возможность того, что такие функции могут не существовать?
Jmite
Если оба логарифмически-экспоненциальные, то либо либо . Большинство функций, встречающихся на практике, имеют такую ​​форму. f = O ( g ) g = O ( f )е,граммезнак равноО(грамм)граммзнак равноО(е)
Юваль Фильмус

Ответы:

16

Есть много примеров для таких функций. Возможно, самый простой способ понять, как получить такой пример, - это создать его вручную.

Давайте начнем с функции над натуральными числами, так как они могут непрерывно пополняться действительными числами.

Хороший способ убедиться, что и g O ( f ), состоит в чередовании их порядков. Например, мы могли бы определитьfO(g)gO(f)

f(n)={nn is oddn2n is even

Тогда мы могли бы ведут себя противоположным по коэффициентам и эвенов. Тем не менее, это не работает для вас, потому что эти функции не монотонно растут.g

Однако выбор был несколько произвольным, и мы могли бы просто увеличить величины, чтобы иметь монотонность. Таким образом, мы можем придумать:n,n2

, а g ( n ) = { n 2 n - 1 n  является нечетным n 2 n n  является четнымf(n)={n2nn is oddn2n1n is eveng(n)={n2n1n is oddn2nn is even

Понятно, что это монотонные функции. Кроме того, , поскольку на нечетных целых числах f ведет себя как n 2 n, в то время как g ведет себя как n 2 n - 1 = n 2 n / n = o ( n 2 n ) , и наоборот по вечерам.е(N)О(грамм(N))еN2NграммN2N-1знак равноN2N/Nзнак равноо(N2N)

Теперь все, что вам нужно, это завершить их до действительного числа (например, путем добавления линейных частей между целыми числами, но это действительно не относится к делу).

Кроме того, теперь, когда у вас есть эта идея, вы можете использовать тригонометрические функции для построения «закрытых формул» для таких функций, поскольку и cos колеблются и достигают максимума в чередующихся точках.грехсоз

Shaull
источник
Можно ли сказать, что и g ( n ) O ( n 2 n ) ? F ( N ) и G ( N ) , как определено в вашем ответе. е(N)О(N2N)грамм(N)О(N2N)е(N)грамм(N)
Mayank
Да. Можно даже сказать , что (аналогично для г ), которая сильнее , чем O . е(N)N2NграммО
Шауль
-3

Хорошая иллюстрация для меня: 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 )

е(N)знак равно2Икс+sяN(Икс)
грамм(N)знак равно2Икс+соs(Икс)
еО(грамм)
граммО(е)
user15305
источник
5
На самом деле они оба друг друга. О
Каролис Юоделе