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 wachsendSorry, 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+2xHmjo 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ösungist 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)nichtbeides gelten. Damit dies gelten könnte müssten die beidenFunktionensichbeliebig oft schneiden. Dazu müsste eine der beiden FunktionenmeinerIntuition nach beliebig oft gegen null gehen, was eine monotone Funktionabernicht kann. Weshalb ist mir allerdings nicht klar :Pist 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-- 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: //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