Skonstruuj dwie funkcje

19

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

  1. f,g są ciągłe;
  2. f,g wzrastają monotonicznie;
  3. fO(g) i .gO(f)
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 = O ( g ) g = O ( f )f,gf=O(g)g=O(f)
Yuval Filmus

Odpowiedzi:

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 fO(g) i gO(f) ma na przemian między ich rzędów wielkości. Na przykład moglibyśmy zdefiniować

f(n)={nn is oddn2n is even

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,n2

, a g ( n ) = { n 2 n - 1 n  jest nieparzysty n 2 n n  jest parzystyf(n)={n2nn is oddn2n1n is eveng(n)={n2n1n is oddn2nn is even

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

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 cos oscylują, a szczyt na przemiennych punktach.sincos

Shaull
źródło
Można powiedzieć, że i g ( n ) O ( n 2 n ) ? F ( n ) i g ( n ) są takie jak określono w odpowiedzi. f(n)O(n2n)g(n)O(n2n)f(n)g(n)
mayank
Tak. Można nawet powiedzieć, że (podobnie do g ), która jest silniejsza niż O . f(n)n2ngO
Shaull
-3

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

f(n)=2x+sin(x)
g(n)=2x+cos(x)
fO(g)
gO(f)
użytkownik15305
źródło
5
W rzeczywistości są one zarówno od siebie. O
Karolis Juodelė