Kan noen forklare, eller henvise til en god (kanskje helst norsk) side der dette er forklart grundig? om eksempel er nødvendig, git denne oppgaven her:
Finn det minste heltallet n, slik at f(x) is O(x^n) for dette utrykket:
F(x) = 3x^5 + (logx)^4
trenger en god forklaring hva som skjer her, hva det kan brukes til , og hvordan man skal regne seg fram til slikt. Det jeg også trenger litt forklaring på er disse konstantene C og K , som for meg er litt difuse akkurat nå....
Bog O notasjon
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Har ingen gode sider å by på men i dette tilfellet er vel
F(x) element i mengden O(x^5)...
Dette er fordi log(x) vokser asymptotisk saktere enn x, dvs [log(x)]^4 vokser saktere enn x^4. Dvs at det er x^5 leddet som dominerer, og dermed at du kan velge en konstant C slik at Cx^5 er større enn F(x)...
Noen som har bedre peiling??
F(x) element i mengden O(x^5)...
Dette er fordi log(x) vokser asymptotisk saktere enn x, dvs [log(x)]^4 vokser saktere enn x^4. Dvs at det er x^5 leddet som dominerer, og dermed at du kan velge en konstant C slik at Cx^5 er større enn F(x)...
Noen som har bedre peiling??
-
Gjest
Her står det litt om Big Oh.
Det er rett som Cauchy skriver at F(x) er element i mengden O(x^5). Når en har et polynom som du har så vil det alltid være element i O(x^n) hvor n er den største potensen i polynomet.
Konstanten c må her være minst 4 fordi 3x^5 + (logx)^4 alltid er mindre enn 4x^5 [/url]
Det er rett som Cauchy skriver at F(x) er element i mengden O(x^5). Når en har et polynom som du har så vil det alltid være element i O(x^n) hvor n er den største potensen i polynomet.
Konstanten c må her være minst 4 fordi 3x^5 + (logx)^4 alltid er mindre enn 4x^5 [/url]
-
Solar Plexsus
- Over-Guru
- Innlegg: 1686
- Registrert: 03/10-2005 12:09
Generelt betyr f=O(g) at |f(x)| < C*g(x) for alle x i D[sub]f[/sub], der C er en konstant uavhengig av x.
I ditt tilfelle innebærer denne definisjonen at f(x)=3x[sup]5[/sup] + (log x)[sup]4[/sup] og g(x)=x[sup]n[/sup] der n er et heltall, dvs. at
(1) 3x[sup]5[/sup] + (log x)[sup]4[/sup] < Cx[sup]n[/sup].
For at (1) skal være tilfredsstilt, må C>0 og n>=5. Nå har ikke du opplyst hva D[sub]f[/sub] er, men jeg antar at x>=1 (Ulikheten (1) gjelder nemlig ikke når x→0[sup]+[/sup]).
Gitt at n>=5. Ved å dele begge sider med x[sup]5[/sup], får vi at
(2) C > 3x[sup]5-n[/sup] + (log x)[sup]4[/sup]/x[sup]5[/sup].
Siden x>=1 og 5-n<=0, blir
(3) 3x[sup]5-n[/sup] <= 3.
Dessuten gir ulikheten log x < x for alle x>=1 at
(log x)[sup]4[/sup]/x[sup]5[/sup] = (log x/x)[sup]4[/sup] * (1/x) < (1^4)/x = 1/x < 1/1 = 1.
Gjennom å anvende likhetene (2) og (3) på ulikheten (1), finner vi at
(4) C > 3x[sup]5-n[/sup] + (log x)[sup]4[/sup]/x[sup]5[/sup] > 3 + 1 = 4
for alle x>=1. M.a.o. følger det av (4) at
(5) f=O(x[sup]n[/sup]) for n=5 (og C>4),
og at denne heltallsverdien av n er den minste som tilfredsstiller (5).
I ditt tilfelle innebærer denne definisjonen at f(x)=3x[sup]5[/sup] + (log x)[sup]4[/sup] og g(x)=x[sup]n[/sup] der n er et heltall, dvs. at
(1) 3x[sup]5[/sup] + (log x)[sup]4[/sup] < Cx[sup]n[/sup].
For at (1) skal være tilfredsstilt, må C>0 og n>=5. Nå har ikke du opplyst hva D[sub]f[/sub] er, men jeg antar at x>=1 (Ulikheten (1) gjelder nemlig ikke når x→0[sup]+[/sup]).
Gitt at n>=5. Ved å dele begge sider med x[sup]5[/sup], får vi at
(2) C > 3x[sup]5-n[/sup] + (log x)[sup]4[/sup]/x[sup]5[/sup].
Siden x>=1 og 5-n<=0, blir
(3) 3x[sup]5-n[/sup] <= 3.
Dessuten gir ulikheten log x < x for alle x>=1 at
(log x)[sup]4[/sup]/x[sup]5[/sup] = (log x/x)[sup]4[/sup] * (1/x) < (1^4)/x = 1/x < 1/1 = 1.
Gjennom å anvende likhetene (2) og (3) på ulikheten (1), finner vi at
(4) C > 3x[sup]5-n[/sup] + (log x)[sup]4[/sup]/x[sup]5[/sup] > 3 + 1 = 4
for alle x>=1. M.a.o. følger det av (4) at
(5) f=O(x[sup]n[/sup]) for n=5 (og C>4),
og at denne heltallsverdien av n er den minste som tilfredsstiller (5).
-
Gjest
Hjertlig takk for mange gode svar. Skal sette meg ned og FORSTÅ dette... blir på en måte mye på en gang, men likevel virker det litt logisk når jeg ser på svaret (iallefall det siste) , selvom jeg ikke ser dette helt ved første øyekast på en oppgave....