Skonstruuj dwie funkcje

19

Skonstruuj dwie funkcje spełniające: $f,g: R^+ → R^+$

$f, g$ są ciągłe;
$f, g$ wzrastają monotonicznie;
$f \ne O(g)$ i . $g \ne O(f)$

asymptotics landau-notation

— Jessie
źródło

2

Czy rozważałeś możliwość, że takie funkcje mogą nie istnieć?

— jmite

Jeśli oba są logarytmiczno-wykładnicze, to albo albo . Większość funkcji spotykanych w praktyce ma tę postać.

f, g

$f,g$

f = O (g)

$f=O(g)$

g = O (f)

$g=O(f)$

— Yuval Filmus

16

Istnieje wiele przykładów takich funkcji. Być może najłatwiejszym sposobem, aby zrozumieć, jak uzyskać taki przykład, jest ręczne skonstruowanie go.

Zacznijmy od funkcji nad liczbami naturalnymi, ponieważ można je ciągle uzupełniać do liczb rzeczywistych.

Dobrym sposobem na zapewnienie $f\neq O(g)$ i $g\neq O(f)$ ma na przemian między ich rzędów wielkości. Na przykład moglibyśmy zdefiniować

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

Następnie mogliśmy $g$ zachowywać przeciwnej na kursie i wyrównuje. Nie działa to jednak dla ciebie, ponieważ funkcje te nie zwiększają monotonicznie.

Jednak wybór był nieco arbitralny i moglibyśmy po prostu zwiększyć wielkości, aby uzyskać monotoniczność. W ten sposób możemy wymyślić: $n,n^2$

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

Oczywiście są to funkcje monotoniczne. Również , ponieważ na nieparzystych liczbach całkowitych zachowuje się jak podczas gdy zachowuje się jak , i odwrotnie, na równi. $f(n)\neq O(g(n))$ $f$ $n^{2n}$ $g$ $n^{2n-1}=n^{2n}/n=o(n^{2n})$

Teraz wystarczy uzupełnić je do liczb rzeczywistych (np. Dodając części liniowe między liczbami całkowitymi, ale to naprawdę nie ma sensu).

Ponadto, skoro masz już ten pomysł, możesz użyć funkcji trygonometrycznych, aby skonstruować `` zamknięte formuły '' dla takich funkcji, ponieważ i oscylują, a szczyt na przemiennych punktach. $\sin$ $\cos$

— Shaull
źródło

Można powiedzieć, że

i

?

i

są takie jak określono w odpowiedzi.

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

Tak. Można nawet powiedzieć, że

(podobnie do

), która jest silniejsza niż

.

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

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

g

$g$

O

$O$

— Shaull

-3

Dobra ilustracja dla mnie to: 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)$

— użytkownik15305
źródło

5

W rzeczywistości są one zarówno

od siebie.

O

$O$

— Karolis Juodelė