www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

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
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
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.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]