Informatiker Board | Druckvorschau: Erste Anfänge mit der O-Notation

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Erste Anfänge mit der O-Notation (http://www.informatikerboard.de/board/thread.php?threadid=2897)

Geschrieben von Shizmo am 03.03.2016 um 21:42:

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

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]

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]

ist eine Konstante. Was genau ist [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

Geschrieben von Tomato am 03.03.2016 um 22:36:

[latex]n_0[/latex]

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

Geschrieben von Shizmo am 03.03.2016 um 23:31:

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]

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]$

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

Geschrieben von eulerscheZahl am 04.03.2016 um 08:58:

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]

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

Geschrieben von Shizmo am 04.03.2016 um 21:38:

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?

Geschrieben von eulerscheZahl am 05.03.2016 um 06:34:

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]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.

Geschrieben von Shizmo am 05.03.2016 um 09:49:

Vielen, vielen Dank.

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

und

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

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

von den Ausdrücken?

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

Wähle

$[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]

und

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

Geschrieben von eulerscheZahl am 05.03.2016 um 09:56:

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]$

Geschrieben von Shizmo am 05.03.2016 um 10:09:

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]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

Geschrieben von eulerscheZahl am 05.03.2016 um 11:11:

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

Geschrieben von Shizmo am 05.03.2016 um 11:30:

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

Geschrieben von eulerscheZahl am 05.03.2016 um 11:41:

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.

Geschrieben von Shizmo am 05.03.2016 um 11:46:

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

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))