O-notation(Landau) < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
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.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 05:21 Di 25.08.2015 | | Autor: | tobit09 |
Hallo dr.dolittle und herzlich ![[willkommenmr]](/images/smileys/willkommenmr.png "[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
|
|
|
| |
|
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?
|
|
|
|
![[]](/images/popup.gif){kind=small}
hier