[infostudents] Re: [infostudents]reRe: Info3 Blatt 10

  • From: Horst <braunma@xxxxxxxxxxxxxxxxxxxxxxxxxx>
  • To: infostudents@xxxxxxxxxxxxx
  • Date: Mon, 14 Jan 2008 22:57:59 +0100

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

Other related posts: