Erste Anfänge mit der O-Notation

03.03.2016, 21:42

Auf diesen Beitrag antworten »

Shizmo

Erste Anfänge mit der O-Notation

Hallo, die Ferien sind vorbei und es geht wieder los mit meinen lästigen Fragen großes Grinsen

großes Grinsen

Dieser Thread wird vermutlich etwas länger werden, aber ich stelle die Fragen nach und nach und zwar fange ich mal mit der Definition an:

Also laut Vorlesung sieht die so aus:

Sei $[latex]g: \mathbb N \rightarrow \mathbb R^{+}[/latex]$ eine Funktion.

$[latex]$\mathcal O(g(n))$[/latex]$ [latex]:= f(n):[/latex]

[latex]:= f(n):[/latex]

Es existierten Konstanten $[latex]c>0, n_{0}[/latex]$ , sodass für alle $[latex]n \geq n_{0}[/latex]$ gilt $[latex]0 \leq f(n) \leq c \cdot g(n)[/latex]$

Also:
$[latex]\exists\ c > 0\ \exists\ n_0 > 0\ \forall\ n > n_0: 0 \le f(n) \le c\cdot g(n)[/latex]$

Frage 1: [latex]c[/latex]

[latex]c[/latex]

ist eine Konstante. Was genau ist [latex]n_0[/latex]

[latex]n_0[/latex]

?

Frage 2: Ich suche eine "formal mathematisch exakte Definition", ist die oben geschriebene Definition mathematisch exakt? Oder lt. Wikipedia gäbe es auch noch diese Definition:

$[latex]\limsup_{x \to a} \left|\frac{f(x)}{g(x)}\right| < \infty[/latex]$

Was wäre denn die formale mathematische exakte Definition? verwirrt

verwirrt

LG

03.03.2016, 22:36

Auf diesen Beitrag antworten »

Tomato

[latex]n_0[/latex]

ist die natürliche Zahl, ab der die Ungleichung gilt. Die beiden Definitiinen sind äquivalent und mathematisch korrekt.

03.03.2016, 23:31

Auf diesen Beitrag antworten »

Shizmo

RE: Erste Anfänge mit der O-Notation

Vielen Dank für deine Antwort.

Hmm, warum steht bei uns in den Folien

Zitat:

$[latex]$\mathcal O(g(n))$[/latex]$ [latex]:= f(n):[/latex]

[latex]:= f(n):[/latex]

Es existierten Konstanten $[latex]c>0, n_{0}[/latex]$ , sodass für alle $[latex]n \geq n_{0}[/latex]$ gilt $[latex]0 \leq f(n) \leq c \cdot g(n)[/latex]$

Also $[latex]n \geq n_{0}[/latex]$

Und auf Wiki:

Zitat:

$[latex]\exists\ c > 0\ \exists\ n_0 > 0\ \forall\ n > n_0: 0 \le f(n) \le c\cdot g(n)[/latex]$

[latex]n > n_0[/latex]

Also ich mein das größer bzw. größer-gleich...

04.03.2016, 08:58

Auf diesen Beitrag antworten »

eulerscheZahl

Letztendlich läuft es aufs gleiche hinaus:
Bei $[latex]n \geq n_{0}[/latex]$ musst du $[latex]n_{0}[/latex]$ eben um 1 größer wählen als bei [latex]n > n_0[/latex]

[latex]n > n_0[/latex]

. Da du das $[latex]n_{0}[/latex]$ aber beliebig wählen darfst, ist das egal.

Anzeige

04.03.2016, 21:38

Auf diesen Beitrag antworten »

Shizmo

Ah okay alles klar vielen Dank.

Dann zum nächsten, siehe Anhang.

Also rein intuitiv würde ich halt mit den log-Ausdrücken anfangen, dann mit den Konstanten, dann quatratischen, kubischen und zuletzt die exponentiellen Ausdrücke.

Aber man sollte das ja auch irgendwie berechnen können oder? Wie geh ich da am besten vor?

05.03.2016, 06:34

Auf diesen Beitrag antworten »

eulerscheZahl

Die Konstante ist kleiner als der Logarithmus.
Nach deiner Definition:
$[latex]f(n) = 42,\, g(n) = \log(n)[/latex]$
Wähle [latex]c=42[/latex]

[latex]c=42[/latex]

$[latex]42 \leq 42\cdot \log(n_0) \Rightarrow 1 \leq \log(n_0) \Rightarrow n_0 \geq 2[/latex]$ (für Basis 2 im Logarithmus).
Damit ist gezeigt $[latex]42 = \mathcal{O}(\log(n))[/latex]$ . In die andere Richtung geht das nicht.

In der O Notation sind Konstanten am kleinsten, dann Logarithmen, Polynome (nach Grad sortiert), dann exponentielle Funktionen.

05.03.2016, 09:49

Auf diesen Beitrag antworten »

Shizmo

Vielen, vielen Dank.

Ich kann dein Beispiel sehr gut nachvollziehen, nur noch generell, kann ich [latex]n_0[/latex]

[latex]n_0[/latex]

und

[latex]c[/latex]

immer beliebig wählen, sodass es in meine Ungleichung passt? Und das [latex]n_0[/latex]

[latex]n_0[/latex]

ersetzt einfach immer mein [latex]n[/latex]

[latex]n[/latex]

von den Ausdrücken?

Also zB:
[latex]f(n) = n, g(n) = 42[/latex]

[latex]f(n) = n, g(n) = 42[/latex]

Wähle

[latex]c = 1[/latex]

$[latex]0 \le n_0 \le c \cdot 42 \Rightarrow 0 \le 1 \le 42[/latex]$

Also
$[latex]n = \mathcal{O}(42)[/latex]$

Stimmt das so? Kann ich mein [latex]n_0[/latex]

[latex]n_0[/latex]

und

[latex]c[/latex]

beliebig wählen, also in dem Fall beide 1?

05.03.2016, 09:56

Auf diesen Beitrag antworten »

eulerscheZahl

Du kannst c erstmal beliebig wählen.
Das n0 musst du dann aber berechnen.
Wenn du das c geschickt wählst, kannst du es dir beim n aber leichter machen.

Und die Ungleichung muss nicht nur für n0 gelten, sondern auch für jedes n darüber.
In deinem Beispiel ist das nicht der Fall (n=43 geht nicht).
Deshalb ist auch $[latex]n \neq \mathcal{O}(42)[/latex]$ , wohl aber $[latex]42 = \mathcal{O}(n)[/latex]$

05.03.2016, 10:09

Auf diesen Beitrag antworten »

Shizmo

Zitat:

Original von eulerscheZahl
[...]
Und die Ungleichung muss nicht nur für n0 gelten, sondern auch für jedes n darüber.
[...]

Ahh, perfekt, genau das wollte ich wissen.
Aber was meinst du genau damit, dass ich n0 berechnen muss?

Anderes Beispiel:

$[latex]f(n) = \sqrt{n}, g(n) = n[/latex]$
Wähle [latex]c=1[/latex]

[latex]c=1[/latex]

$[latex]0 \le \sqrt{n_0} \le c \cdot n_0 \Rightarrow[/latex]$ (wenn n0=1) $[latex]0 \le 1 \le 1[/latex]$

Und es dürfte auch für größere n's gelten, zB n0=9
$[latex]0 \le \sqrt{9} \le 1 \cdot 9 \Rightarrow 0 \le 3 \le 9[/latex]$

Also
$[latex]\sqrt{n} = \mathcal{O}(n)[/latex]$

Was hältst du davon?? großes Grinsen

großes Grinsen

großes Grinsen

05.03.2016, 11:11

Auf diesen Beitrag antworten »

eulerscheZahl

Passt.
Mit n0 berechnen meine ich du musst ein n0 finden, das die Ungleichung erfüllt.

05.03.2016, 11:30

Auf diesen Beitrag antworten »

Shizmo

Okay passt, wenn ich jetzt aber alles so durchrechne und vergleiche, bin ich ewig dabei, wie finde ich das schneller raus?

05.03.2016, 11:41

Auf diesen Beitrag antworten »

eulerscheZahl

Wenn du das nach Definition zeigen willst, musst du wohl in den sauren Apfel beißen.

Letzendlich ist das aber eine Grenzwertberechnung: welche Funktion wächst im Unendlichen schneller.
$[latex]f(x) = n,\, g(x) = \sqrt n[/latex]$
$[latex]\lim_{x\to\infty} = \frac{f(x)}{g(x)} = \infty[/latex]$ heißt, dass f schneller wächst als g, daher ist $[latex]g(x) = \mathcal{O}(f(x))[/latex]$ .
Berechnest du den Grenzwert von g(x)/f(x), ist das Ergebnis 0, was heißt g wächst langsamer als f.
Kriegst du eine echt positive Konstante, sind sie in der $[latex]\Theta[/latex]$ Notation äquivalent.

05.03.2016, 11:46

Auf diesen Beitrag antworten »

Shizmo

Ok vielen Dank, werde das gleich mal durchprobieren.

Hab mir grad gedacht ich hau alles in einen Plotter und schaus mir da an, ist aber gar nicht so leicht, die alle zu vergleichen großes Grinsen

großes Grinsen

Aber nochwas was ich nicht verstehe: (siehe Grafik)

Dass x*log(x) schneller steigt als x macht für mich sinn, aber warum steigt x*log(log(x)) weniger schnell als x???

x*log(x)
x
x*log(log(x))

05.03.2016, 11:55

Auf diesen Beitrag antworten »

eulerscheZahl

Alles eine Frage der Betrachtungsweise smile

smile

Schau mal auf die Achsenbeschriftung.

05.03.2016, 12:00

Auf diesen Beitrag antworten »

Shizmo

Haha

großes Grinsen

großes Grinsen

Ja soweit habe ich nicht nach vorne geschaut großes Grinsen

großes Grinsen

großes Grinsen

05.03.2016, 13:46

Auf diesen Beitrag antworten »

Shizmo

Okay, also meine Sortierung würde dann so ausschauen:

$[latex]\sqrt{n}[/latex]$
$[latex]n \cdot log(log(2^n))[/latex]$
$[latex]n \cdot log(n)^2[/latex]$
$[latex]n \cdot log(log(n))[/latex]$
$[latex]n \cdot log(n)[/latex]$
$[latex]4^{log(n)}[/latex]$
$[latex]n^{1,5}[/latex]$
$[latex]2^{log(n)}[/latex]$
$[latex]\frac{2^{n+1}}{2}[/latex]$

Und bei den letzten 2 habe ich eine Konstante ( $[latex]\frac{1}{4}[/latex]$ ) rausbekommen, also eine $[latex]\Theta[/latex]$ -Äquivalenz.

Ich bin mir nur nicht ganz sicher, ist $[latex]n \cdot log(n)^2[/latex]$ das gleiche, wie Punk4 bei der Aufgabe auf dem Bild?

05.03.2016, 14:47

Auf diesen Beitrag antworten »

eulerscheZahl

Wir hatten uns doch schon darauf geeinigt, dass n langsamer wächst als n*log(n). Also muss es weiter nach oben (direkt nach sqrt(n)).
Dann schreiben wir die anderen mal ein wenig um:
$[latex]n \cdot \log(\log(2^n)) = n \cdot \log(n\cdot\log(2)) = n \cdot \log(n)[/latex]$
$[latex]n \cdot \log(n)^2 = n \cdot \log(n) \cdot \log(n)[/latex]$
Es gilt: $[latex]n \cdot \log(\log(n)) < n\cdot\log(n)=n \cdot \log(\log(2^n))<n \cdot \log(n)^2[/latex]$

$[latex]2^{\log(n)} = n[/latex]$ (für n > 0)
$[latex]4^{\log(n)} = 2^{2\cdot\log(n)} = (2^{\log(n)})^2 = n^2[/latex]$
Und $[latex]\frac{2^{n+1}}{2} = 2^n[/latex]$

05.03.2016, 19:50

Auf diesen Beitrag antworten »

Shizmo

Zitat:

Original von eulerscheZahl
Wir hatten uns doch schon darauf geeinigt, dass n langsamer wächst als n*log(n). Also muss es weiter nach oben (direkt nach sqrt(n)).

Natürlich, da hab ich wohl was durcheinander gebracht.

Zitat:

Dann schreiben wir die anderen mal ein wenig um:
$[latex]n \cdot \log(\log(2^n)) = n \cdot \log(n\cdot\log(2)) = n \cdot \log(n)[/latex]$
$[latex]n \cdot \log(n)^2 = n \cdot \log(n) \cdot \log(n)[/latex]$
Es gilt: $[latex]n \cdot \log(\log(n)) < n\cdot\log(n)=n \cdot \log(\log(2^n))<n \cdot \log(n)^2[/latex]$

$[latex]2^{\log(n)} = n[/latex]$ (für n > 0)
$[latex]4^{\log(n)} = 2^{2\cdot\log(n)} = (2^{\log(n)})^2 = n^2[/latex]$
Und $[latex]\frac{2^{n+1}}{2} = 2^n[/latex]$

Ahh, auf die Idee einfach mal Umzuformen bin ich nicht gekommen großes Grinsen

großes Grinsen

großes Grinsen

Vielen, vielen Dank.
Aber noch eine Frage, aber was anderes, du kennst dich ja sicher auch sehr gut mit LaTeX aus, wenn ich:

code:
1:	$\lim_{n \to \infty} \frac{42}{n} = 0$

schreibe, sollte doch eine schöne Limes Funktion kommen, allerdings ist bei mir das $[latex]n \to \infty[/latex]$ nicht unter dem lim, hast du eine Idee warum das so ist?

Der Codeabschnitt schaut so aus:

code:
1: 2:	\item Beispiel: $\lim_{n \to \infty} \frac{42}{n} = 0$\\\\ Also $42 = \mathcal{O}(n)$

05.03.2016, 20:56

Auf diesen Beitrag antworten »

eulerscheZahl

Sehr gut ist übertrieben. Aber bei der Bachelorarbeit hat es gute Dienste geleistet.
In LaTeX gibt es 2 Modi für Formeln: abgesetzt und inline.
Mit $$ schreibst du im inline Modus. Der ist darauf ausgelegt, nicht mehr Platz zu brauchen, als der Fließtext (ausgenommen Dinge wie underbrace).
Wenn du mit \begin{align*}...\end{align*} oder \[...\] arbeitest, geht der limes über 2 Zeilen.
Du kannst aber auch im inline Modus zweizeilig schreiben:

code:
1:	$\lim\limits_{\substack{n \to \infty}} \frac{42}{n} = 0$

06.03.2016, 10:25

Auf diesen Beitrag antworten »

Shizmo

Perfekt, vielen, vielen Dank für deine Hilfe!!!!!! Daumen hoch

Daumen hoch

Daumen hoch

Daumen hoch

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »