Construire deux fonctions et satisfaisant

19

Construisons deux fonctions satisfaisant: $f,g: R^+ → R^+$

$f, g$ sont continus;
$f, g$ augmentent de façon monotone;
$f \ne O(g)$ et . $g \ne O(f)$

asymptotics landau-notation Jessie
la source

2

Avez-vous envisagé la possibilité que de telles fonctions n'existent pas?

jmite

Si les deux sont logarithmico-exponentielles, alors ou . La plupart des fonctions rencontrées dans la pratique sont de cette forme.

f, g

$f,g$

f = O (g)

$f=O(g)$

g = O (f)

$g=O(f)$

Yuval Filmus

16

Il existe de nombreux exemples de telles fonctions. La façon la plus simple de comprendre comment obtenir un tel exemple est peut-être de le construire manuellement.

Commençons par la fonction sur les nombres naturels, car ils peuvent être continuellement remplis en réels.

Un bon moyen de s'assurer que et consiste à alterner entre leurs ordres de grandeur. Par exemple, nous pourrions définir $f\neq O(g)$ $g\neq O(f)$

$f(n)=\begin{cases} n & n \text{ is odd}\\ n^2 & n \text{ is even}\\ \end{cases}$

Ensuite, nous pourrions avoir se comporter à l'opposé sur les cotes et égalise. Cependant, cela ne fonctionne pas pour vous, car ces fonctions n'augmentent pas de manière monotone. $g$

Cependant, le choix de était quelque peu arbitraire, et nous pouvions simplement augmenter les grandeurs pour avoir la monotonie. De cette façon, nous pouvons proposer: $n,n^2$

$f(n)=\begin{cases} n^{2n} & n \text{ is odd}\\ n^{2n-1} & n \text{ is even}\\ \end{cases}$ , et $g(n)=\begin{cases} n^{2n-1} & n \text{ is odd}\\ n^{2n} & n \text{ is even}\\ \end{cases}$

Il s'agit clairement de fonctions monotones. De plus, , puisque sur les entiers impairs, se comporte comme tandis que se comporte comme , et vice-versa sur les mêmes. $f(n)\neq O(g(n))$ $f$ $n^{2n}$ $g$ $n^{2n-1}=n^{2n}/n=o(n^{2n})$

Maintenant, tout ce dont vous avez besoin est de les compléter aux réels (par exemple en ajoutant des parties linéaires entre les entiers, mais c'est vraiment à côté du point).

De plus, maintenant que vous avez cette idée, vous pouvez utiliser les fonctions trigonométriques afin de construire des `` formules fermées '' pour de telles fonctions, car et oscillent et culminent sur des points alternés. $\sin$ $\cos$

Shaull
la source

Peut-on dire que et ? et sont tels que définis dans votre réponse.

f (n) \in O (n^{2 n})

$f(n) \in O(n^{2n})$

g (n) \in O (n^{2 n})

$g(n) \in O(n^{2n})$

f (n)

$f(n)$

g (n)

$g(n)$

Mayank

Oui. On peut même dire que (même pour ), qui est plus fort que .

f (n) \leq n^{2 n}

$f(n)\le n^{2n}$

g

$g$

O

$O$

Shaull

-3

Une bonne illustration pour moi est: http://www.wolframalpha.com/input/?i=sin%28x%29%2B2x%2C+cos%28x%29%2B2x

f (n) = 2 x + s i n (x)

$f(n) =2x+sin(x)$

g (n) = 2 x + c o s (x)

$g(n) =2x+cos(x)$

f \neq O (g)

$f\neq O(g)$

g \neq O (f)

$g\neq O(f)$

user15305
la source

5

En fait, ils sont tous deux de l'autre.

O

$O$

Karolis Juodelė

Construire deux fonctions et satisfaisant

Réponses: