[infostudents] Re: Info3 Blatt 10

  • From: Oleg <olegus@xxxxxxx>
  • To: infostudents@xxxxxxxxxxxxx
  • Date: Tue, 15 Jan 2008 19:25:48 +0100

Servus!

Wie wär's damit: wenn f \notin O(g), dann heißt das doch, dass f(n) > k_1 *g(n) und zwar für alle n und k_1. Analog: g \notin O(f) => g(n) > k_2 * f(n).

Somit:
f(n) > k_1 * g(n)  // g(n) ersetzen
f(n) > k_1 * k_2 * f(n)

Das liefert einen Widerspruch, weil die Gleichung für alle k gelten muss.

Oleg


Jonas Gehring schrieb:
Am 15.01.08 schrieb Horst <braunma@xxxxxxxxxxxxxxxxxxxxxxxxxx>:
Am Dienstag 15 Januar 2008 schrieb Jonas Gehring:
Am 15.01.08 schrieb Horst <braunma@xxxxxxxxxxxxxxxxxxxxxxxxxx>:
Am Dienstag 15 Januar 2008 schrieb Jonas Gehring:
Hm,

Mir ist immer noch nicht ganz klar wo das Problem bei Alex' Lösung
liegt. So wie ich das verstehe gilt cos(x) \notin O(sin(x)),
jup, als lösung für a passts denk ich.
Ist b) nicht genau das gleiche, nur dass die Funktionen zusätzlich
monoton sein müssen? Obige sind das ja.
sin(x) ist nicht auf ganz R monoton wachsend

Sorry, meinte natürlich sin(x)+2x bzw. cos(x)+2x.

also auch
cos(x)+2x \notin O(sin(x)+2x).
cos(x)+2x kann man nach oben abschätzen durch 1+2x
sin(x)+2x kann man nach unten abschätzen durch -1+2x
Hmjo wohl wahr aber das zeigt ja nichts bezüglichder Aufgabenstellung,
oder?

Man kann den cosinus eben nicht durch
den sinus nach oben hin abschätzen, auch mit einem beliebigen
Vorfaktor nicht, da dadurch lediglich die Amplitude der Funktion
geändert wird. Die "für alle n > n0"-Bedingung gilt nicht, da sich
immer Punkte finden lassen, bei denen c*(sin(x)+2x) < cos(x)+2x gilt.

Gruß.
Jonas

Am 14.01.08 schrieb Silvan Sievers <SilSie@xxxxxx>:
ah ok, kapiert, wo das problem liegt.

-------- Original-Nachricht --------

Datum: Mon, 14 Jan 2008 22:57:59 +0100
Von: Horst <braunma@xxxxxxxxxxxxxxxxxxxxxxxxxx>
An: infostudents@xxxxxxxxxxxxx
Betreff: [infostudents] Re: [infostudents]reRe: Info3 Blatt 10

er hat funktionen angegeben, für die f \in O(g) und g \in O(f)
gilt... man
soll zeigen, dass es monoton steigende funktionen f, g gibt oder
eben nicht
gibt so dass f \notin O(g) und g \notin O(f)

Am Montag 14 Januar 2008 schrieb Silvan Sievers:
ich finde dass ist genau der Punkt der zu zeigen war, sprich
Alex'
Lösung

ist korrekt! Denn wie er selbst schon schrieb, überschneiden sich
beide Funktionen beliebig oft, und genau deshalb gilt natürlich
auf bestimmen nicht dass f in O(g) und in anderen nicht, dass g
in O(f). Dass beides "gleichzeitig" nie gelten kann, sollte klar
sein. Aber es wir auch für unendlich große x-Werte nie nur einer
von beiden Fällen eintreten, da sin/cos periodisch sind. Sprich
entweder ich habe den Einwand falsch verstanden, oder er war
unberechtigt :) Grüße, Silvan


-------- Original-Nachricht --------

Datum: Mon, 14 Jan 2008 21:11:19 +0100
Von: Alexander Nutz <alex_nutz@xxxxxx>
An: infostudents@xxxxxxxxxxxxx
Betreff: [infostudents] Re: [infostudents]reRe: Info3 Blatt 10

das ist ein Punkt...
Hab's verplant mit dem konstanten Faktor.
beliebig oft schneiden tun sie sich ja, aber sie driften nicht
immer weiter auseinander, anschaulich gesprochen - das sollten
sie wohl auch noch tun.
danke

Horst wrote:
Am Montag 14 Januar 2008 schrieb Alexander Nutz:
wie wär's z.B. mit f(x)=sin x + 2x, g(x)=cos x + 2x ?
Bei der verrenkt man sich auch nicht schon beim Lesen das
Gehirn..
die sind monoton, aber:

g \in O(f):

cos(n) kann man mit cos(n)<=1 abschätzen also ist

g(n) = cos(n) + 2n <= 2n+1

sin x kann man nach unten mit -1 abschätzen also ist:
f(n) = sin n + 2n >= 2n -1

mit c=2 z.B. also

g(n) < 2* f(n) für n > 1

andersrum genauso...

ich glaube wenn f und g monoton sind kann f \in O(g) und g
\in O(f)
nicht

beides gelten. Damit dies gelten könnte müssten die beiden
Funktionen

sich

beliebig oft schneiden. Dazu müsste eine der beiden
Funktionen
meiner

Intuition nach beliebig oft gegen null gehen, was eine
monotone Funktion
aber

nicht kann. Weshalb ist mir allerdings nicht klar :P

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
--
Ist Ihr Browser Vista-kompatibel? Jetzt die neuesten
Browser-Versionen downloaden: http://www.gmx.net/de/go/browser
---
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: