matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenAnalysis des R1O-notation(Landau)
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Analysis des R1" - O-notation(Landau)
O-notation(Landau) < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Analysis des R1"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

O-notation(Landau): Korrektur,Tipp
Status: (Frage) beantwortet Status 
Datum: 17:10 Mo 24.08.2015
Autor: dr.dolittle

Hallo leute,

ich hab eine frage bzgl. der Groß $O$-notation. Ich bin Informatiker und muss die O-Notation beherrschen, um die Laufzeit von Algorithmen in
$O(g(n)), [mm] \Omega(g(n)), \Theta(g(n)), \omega(g(n)), [/mm] & o(g(n)) $ einordnen zu können.

Nun haben wir diese wie folgt definiert


$f(n) [mm] \in [/mm] O(g(n))$ heißt : [mm] $c\cdot{}f(n))$ [/mm] ist die obere Schranke für $g(n)$

formale Definition : $f(n) [mm] \in [/mm] O(g(n)) [mm] \gdw \exists [/mm] c>0, [mm] n_0$ [/mm] mit [mm] $\forall n\geq n_0 [/mm] : [mm] 0\leq [/mm] g(n) [mm] \leq c\cdot{}f(n) [/mm] $ oder alternativ

$f(n) [mm] \in [/mm] O(g(n)) [mm] \gdw \limes sup_{n\rightarrow\infty} \frac{g(n)}{f(n)} [/mm] = c [mm] \geq [/mm] 0 $ mit $ c [mm] \neq \infty [/mm] $



$f(n) [mm] \in \Omega(g(n))$ [/mm] heißt : [mm] $c\cdot{}f(n))$ [/mm] ist die untere Schranke für $g(n)$

formale Definition : $f(n) [mm] \in [/mm] O(g(n)) [mm] \gdw \exists [/mm] c>0, [mm] n_0$ [/mm] mit [mm] $\forall n\geq n_0 [/mm] :   [mm] c\cdot{}f(n) \leq [/mm] g(n) $ oder alternativ

$f(n) [mm] \in \Omega(g(n)) \gdw \limes inf_{n\rightarrow\infty} \frac{g(n)}{f(n)}>0 [/mm] $


$f(n) [mm] \in \Theta(g(n))$ [/mm] heißt : [mm] $\Theta$ [/mm] ist die Menge der Funktionen die genauso schnell wachsen wie $g(n)$

formale Definition : $f(n) [mm] \in [/mm] O(g(n)) [mm] \gdw \exists c_1,c_2>0, n_0$ [/mm] mit [mm] $\forall n\geq n_0 [/mm] :   [mm] c_1\cdot{}f(n) \leq [/mm] g(n) [mm] \geq c_2\cdot{}f(n)$ [/mm] oder alternativ

$f(n) [mm] \in \Theta(g(n)) \gdw \limes_{n\rightarrow\infty} \frac{g(n)}{f(n)}=c [/mm] $ mit $ [mm] 0

$f(n) [mm] \in [/mm] o(g(n)) [mm] \gdw \forall [/mm] c>0, [mm] \exists n_0$ [/mm] mit [mm] $\forall n\geq n_0 [/mm] : [mm] 0\leq [/mm] g(n) < [mm] c\cdot{}f(n) [/mm] $

$f(n) [mm] \in \omega(g(n)) \gdw \forall [/mm] c>0, [mm] \exists n_0$ [/mm] mit [mm] $\forall n\geq n_0 [/mm] :  [mm] c\cdot{}f(n) [/mm] <g(n)$
____________________________________________________________


so jetzt bekommen wir aufgaben wie :

Ordnen Sie die folgenden Klassen von Funktionen in aufsteigender Größe an und setzen Sie dabei benachbarte Funktionenmengen mit [mm] $"\subset" [/mm] $(echte Teilmenge) und $=$ in Beziehung.


[mm] $O(n^2),O(3^n),O(n!),O(n+log_2(n)),O(\summe_{i=0}^{\lceil\wurzel{n}\rceil} i),O(\frac{1}{n}),O(log_2(n)),O(n^n),O(\summe_{i=0}^{n-1}i),O(n)$ [/mm]


Schreiben sie bspl.weise $ O(f(n)) [mm] \subset [/mm] O(g(n))=O(h(n))$


wenn $O(f(n))$ eine echte Teilmenge von $ O(g(n))$ ist und $O(g(n)) $ und $O(h(n))$ identisch sind.




1. Ich weis nicht,wie mit den summenzeichen umgehen soll. ich habe mir präventiv mal den kleinen gauß und die geo.summenformel rausgesucht.Muss da jetzt einen Indexverschiebung gemacht werden oder nicht ? es verwirrt mich irgendwie :/ 2. wie sieht man jetzt die echte Teilmenge oder die gleichheit , ich habe keine Ahnung, wie ich das zeigen kann?


Bitte helft mir...:/



Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

        
Bezug
O-notation(Landau): Antwort
Status: (Antwort) fertig Status 
Datum: 05:21 Di 25.08.2015
Autor: tobit09

Hallo dr.dolittle und herzlich [willkommenmr]!


> [mm]f(n) \in O(g(n))[/mm] heißt : [mm]c\cdot{}f(n))[/mm] ist die obere
> Schranke für [mm]g(n)[/mm]

(Solche oberen Schranken sind im Falle ihrer Existenz keineswegs eindeutig. Es muss also EINE obere Schranke statt DIE obere Schranke heißen.)

> formale Definition : [mm]f(n) \in O(g(n)) \gdw \exists c>0, n_0[/mm]
> mit [mm]\forall n\geq n_0 : 0\leq g(n) \leq c\cdot{}f(n)[/mm] oder
> alternativ
>  
> [mm]f(n) \in O(g(n)) \gdw \limes sup_{n\rightarrow\infty} \frac{g(n)}{f(n)} = c \geq 0[/mm]
> mit [mm]c \neq \infty[/mm]

(Ich nehme an, es sollen $f$ und $g$ Abbildungen [mm] $f,g\colon\IN\setminus\{0\}\to\IR_{>0}$ [/mm] sein?
Davon gehe ich im Folgenden aus.)

Hier sind leider f und g vertauscht! Angeben sind jeweils Charakterisierungen von [mm] $g(n)\in [/mm] O(f(n))$, nicht von [mm] $f(n)\in [/mm] O(g(n))$.


Unpräzise Intuition: [mm] $g(n)\in [/mm] O(f(n))$ bedeutet "g wächst höchstens so schnell wie f" ("von konstanten Faktoren abgesehen").

Man sollte im Hinterkopf die Vorstellung haben, dass folgende Reihenfolge von langsam wachsend echt aufsteigend zu schnell wachsend vorliegt:

konstante Funktionen z.B. 5

Logarithmusfunktionen z.B. [mm] $\log_{10}n$ [/mm]

lineare Funktionen z.B. n
quadratische Funktionen z.B. [mm] $n^2$ [/mm]
kubische Funktionen z.B. [mm] $n^3$ [/mm] (oder auch [mm] $7n^3+2n+4$) [/mm]
...

Exponentialfunktionen z.B. [mm] $2^n$ [/mm] (wobei z.B. [mm] $3^n$ [/mm] wiederum schneller wächst als [mm] 2^n) [/mm]


Diese Vorstellungen sind hilfreich, um Aufgaben wie die von dir genannte (bei der anscheinend kein Beweis verlangt ist) in akzeptabler Zeit lösen zu können.

Daneben ist das "lim-sup-Kriterium" sehr nützlich, da in vielen "praktisch vorkommenden" Fällen der

       [mm] $\lim_{n\to\infty}\frac{g(n)}{f(n)}$ [/mm]

als reelle Zahl oder uneigentlich als [mm] $+\infty$ [/mm] existiert.
Dann gilt

       [mm] $\limsup_{n\to\infty}\frac{g(n)}{f(n)}=\lim_{n\to\infty}\frac{g(n)}{f(n)}$. [/mm]



> so jetzt bekommen wir aufgaben wie :
>  
> Ordnen Sie die folgenden Klassen von Funktionen in
> aufsteigender Größe an und setzen Sie dabei benachbarte
> Funktionenmengen mit [mm]"\subset" [/mm](echte Teilmenge) und [mm]=[/mm] in
> Beziehung.
>  
>
> [mm]O(n^2),O(3^n),O(n!),O(n+log_2(n)),O(\summe_{i=0}^{\lceil\wurzel{n}\rceil} i),O(\frac{1}{n}),O(log_2(n)),O(n^n),O(\summe_{i=0}^{n-1}i),O(n)[/mm]
>  
>
> Schreiben sie bspl.weise [mm]O(f(n)) \subset O(g(n))=O(h(n))[/mm]
>  
>
> wenn [mm]O(f(n))[/mm] eine echte Teilmenge von [mm]O(g(n))[/mm] ist und
> [mm]O(g(n))[/mm] und [mm]O(h(n))[/mm] identisch sind.
>  
>
>
>
> 1. Ich weis nicht,wie mit den summenzeichen umgehen soll.
> ich habe mir präventiv mal den kleinen gauß und die
> geo.summenformel rausgesucht.Muss da jetzt einen
> Indexverschiebung gemacht werden oder nicht ? es verwirrt
> mich irgendwie :/

Gute Idee mit dem kleinen Gauß!
Es gilt für alle [mm] $m\in\IN$ [/mm]

     [mm] $\sum_{i=0}^mi=0+1+2+\ldots+m=1+2+\ldots+m=\sum_{i=1}^mi=\frac{m(m+1)}{2}$. [/mm]

Eine Indexverschiebung ist hier nicht nötig.


> 2. wie sieht man jetzt die echte
> Teilmenge oder die gleichheit , ich habe keine Ahnung, wie
> ich das zeigen kann?

Es gilt die Äquivalenz

        [mm] $O(g(n))\subseteq O(f(n))\iff g(n)\in [/mm] O(f(n))$ ("g wächst höchstens so schnell wie f").

Daraus kann man weitere Äquivalenzen folgern:

        [mm] $O(g(n))\subsetneq O(f(n))\iff g(n)\in O(f(n))\text{ und }f(n)\notin [/mm] O(g(n))$ ("g wächst echt langsamer als f")

      [mm] $O(g(n))=O(f(n))\iff g(n)\in O(f(n))\text{ und }f(n)\in [/mm] O(g(n))$ ("f und g wachsen gleich schnell")



Falls [mm] $a:=\lim_{n\to\infty}\frac{g(n)}{f(n)}$ [/mm] existiert (als reelle Zahl oder uneigentlich als [mm] $+\infty$), [/mm] gelten darüber hinaus die Äquivalenzen:

      [mm] $a<\infty\iff g(n)\in [/mm] O(f(n))$ ("g wächst höchstens so schnell wie f")

      [mm] $a=0\iff O(g(n))\subsetneq [/mm] O(f(n))$ ("g wächst echt langsamer als f")
      [mm] $0       [mm] $a=\infty\iff O(g(n))\supsetneq [/mm] O(f(n))$ ("g wächst schneller als f").


Untersuche in den Beispielen aus der Aufgabenstellung also Existenz und Wert von [mm] $\lim_{n\to\infty}\frac{g(n)}{f(n)}$. [/mm]


Viele Grüße
Tobias

Bezug
                
Bezug
O-notation(Landau): Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:09 Di 25.08.2015
Autor: dr.dolittle

heeeyyy:))

danke für deine hilfreiche antwort die aufgabe hat geklappt:)

kannst du mir die "limesgesetzte" für $g(n) [mm] \in \omega(f(n))$ [/mm] und $g(n) [mm] \in [/mm] o(f(n))$ noch sagen:)?  oder wo ich die finden kann?

Bezug
                        
Bezug
O-notation(Landau): Antwort
Status: (Antwort) fertig Status 
Datum: 15:27 Di 25.08.2015
Autor: DieAcht

Hallo dr.dolittle und [willkommenmr]


Schau mal []hier.


Gruß
DieAcht

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Analysis des R1"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]