Используя формальное определение больших обозначений O, разве f (x) не будет O (g (x)) почти для всех функций функции g (x)? - Математика
Винтажный Клуб для гитаристов
1 голос
/

Формальное определение обозначений больших О

$$f(x)=O(g(x)) \text{ as } x \rightarrow \inf \leftrightarrow |f(x)| \leq Mg(x) \text{ for all } x \geq x_0 $$

Но не будет ли это означать, например, когда $f(x) = 2x^2$, $f(x) = O(x!)$?

Установка $M=1$ и $x_0 = 5$, показывает, что $2x^2 \leq x!,\text{ } x \geq 5$.

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

Мой вопрос заключается в том, верно ли это, что означало бы, что для любой функции существуют бесконечные большие функции O,или если я делаю что-то не так.

1 Ответ

4 голосов
/

Ваше понимание верно. Например, если $f \in O(x^n)$, то также $f \in O(x^{n+m})$.

Обычно, когда кого-то просят показать $f \in O(g)$ для некоторого $g$, вы хотите, чтобы $g$ рос как можно медленнее. Сказать $f \in O(x!)$ не очень полезно, потому что этот класс огромен.

Не существует «уникального» или «лучшего» класса big-O для любого данного $f$, но обычно пытаются найти лучшего среди$O(g)$ где $g$ среди мономов, логарифмов, экспонент и т. Д.

...