[infostudents] Re: Info3 Blatt 10

  • From: Guido Solbach <ich@xxxxxxxxxxxxxxxx>
  • To: infostudents@xxxxxxxxxxxxx
  • Date: Tue, 15 Jan 2008 19:28:28 +0100

Oh da habe ich wohl nen Denkfehler :-D
Aber einen habe ich noch:
#
Ich lasse zwei Funktionen abwechselnd exponentiell zulegen.
Die eine bei jedem geraden Schritt, die andere bei jedem ungeraden Schritt. Und das wird dann noch potenziert. Hier haben wir dann zwei Funktionen, die sich jeweils überholen und durch das weitere Potenzieren haben wir ein so starkes Wachstum, dass uns Konstanten egal sein können.

Grüssle



Horst schrieb:
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:
http://www.freelists.org/archives/infostudents/

Subscribe / Unsubscribe:
http://www.freelists.org/list/infostudents
---
Sent through the Infostudents Mailinglist

List Archive:
http://www.freelists.org/archives/infostudents/

Subscribe / Unsubscribe:
http://www.freelists.org/list/infostudents
---
Sent through the Infostudents Mailinglist

List Archive:
http://www.freelists.org/archives/infostudents/

Subscribe / Unsubscribe:
http://www.freelists.org/list/infostudents
---
Sent through the Infostudents Mailinglist

List Archive:
http://www.freelists.org/archives/infostudents/

Subscribe / Unsubscribe:
http://www.freelists.org/list/infostudents
---
Sent through the Infostudents Mailinglist

List Archive:
http://www.freelists.org/archives/infostudents/

Subscribe / Unsubscribe:
http://www.freelists.org/list/infostudents
---
Sent through the Infostudents Mailinglist

List Archive:
http://www.freelists.org/archives/infostudents/

Subscribe / Unsubscribe:
http://www.freelists.org/list/infostudents
---
Sent through the Infostudents Mailinglist

List Archive:
http://www.freelists.org/archives/infostudents/

Subscribe / Unsubscribe:
http://www.freelists.org/list/infostudents


---
Sent through the Infostudents Mailinglist

List Archive:
http://www.freelists.org/archives/infostudents/

Subscribe / Unsubscribe:
http://www.freelists.org/list/infostudents


Other related posts: