Am Dienstag 15 Januar 2008 schrieb Guido Solbach:
Das steht im Forum (wurde von einer wichtigen und vor allem
entscheidenden Person geschrieben):
"Die Aussage f=O(g) bedeutet, dass es ein n_0 und ein c gibt mit
für alle n ≥ n_0: f(n) ≤ c g(n)."
und das gibt es nicht!
doch:
c=2, n beliebig
f(n) ≤ c g(n)
f(n) ≤ 2(2^x - 2^x /4) ≤ 2(2^x + (-1)^x (2^x)/4)
da -2^x /4 ≤ (-1)^x (2^x)/4
und f(n)=2^x ≤ 2(2^x - 2^x /4)
es steht also dann da f(n) ≤ .. ≤ 2*g(n)
Horst schrieb:
ja so ist es monoton, aber so ist auch g in O(f) und f in O(g)
Am Montag 14 Januar 2008 schrieb Guido Solbach:
Meine Rechnungen waren natürlich falsch ;-)
So ists richtig (kann man im Zweifelsfall aber nachrechnen, bei geraden
Werten immer +):
g(2) = 4 (+1) 4/4 = 5
g(3) = 8 (-1)8/4 = 6
g(4) = 16 (+1)16/4= 20
g(5) = 32 (-1) 32/4 = 24
g(6) = 64 (+1) 64/4 = 80
und dann noch g(1) = 3/2
und g(0) = 3/4
und das alles ohne Gewehr ....Päng
Horst schrieb:
Am Montag 14 Januar 2008 schrieb Guido Solbach:
Ich habe da nen + vergessen. So ists richtig:
g(x)=2^x + (-1)^x (2^x)/4
(-1)^x (2^x)/4 lässt sich durch - 2^x /4 nach unten abschätzen
- 2^x /4 <= (-1)^x (2^x)/4
also ist a(x)=2^x - 2^x /4 <= g(x)
eine untere schranke für g.
mit konstante c=2:
g(x) <= 2*a(x) <= f(x)
also g \in O(f)
Guido Solbach schrieb:
g(2) = 4 (-1) 4/4 =3
g(3) = 8 (+1)8/4 =10
g(4) = 16 (-1)16/4=12
g(5) = 32 (+1) 32/4 =40
g(6) = 64 (-1) 64/4 =48
etc
ich würde sagen streng monoton steigend
Horst schrieb:
ist g(x)=2^x (-1)^x 2^x/4 denn monoton steigend?
g(2) = 4
g(3) = -16
für monotonie muss für alle a>b : g(a) >= g(b) gelten...
Am Montag 14 Januar 2008 schrieb Guido Solbach:
Hier schon mal was von mir.....
---
Sent through the Infostudents Mailinglist
List Archive:
//www.freelists.org/archives/infostudents/
Subscribe / Unsubscribe:
//www.freelists.org/list/infostudents
---
Sent through the Infostudents Mailinglist
List Archive:
//www.freelists.org/archives/infostudents/
Subscribe / Unsubscribe:
//www.freelists.org/list/infostudents
---
Sent through the Infostudents Mailinglist
List Archive:
//www.freelists.org/archives/infostudents/
Subscribe / Unsubscribe:
//www.freelists.org/list/infostudents
---
Sent through the Infostudents Mailinglist
List Archive:
//www.freelists.org/archives/infostudents/
Subscribe / Unsubscribe:
//www.freelists.org/list/infostudents
---
Sent through the Infostudents Mailinglist
List Archive:
//www.freelists.org/archives/infostudents/
Subscribe / Unsubscribe:
//www.freelists.org/list/infostudents
---
Sent through the Infostudents Mailinglist
List Archive:
//www.freelists.org/archives/infostudents/
Subscribe / Unsubscribe:
//www.freelists.org/list/infostudents
---
Sent through the Infostudents Mailinglist
List Archive:
//www.freelists.org/archives/infostudents/
Subscribe / Unsubscribe:
//www.freelists.org/list/infostudents
---
Sent through the Infostudents Mailinglist
List Archive:
//www.freelists.org/archives/infostudents/
Subscribe / Unsubscribe:
//www.freelists.org/list/infostudents
