Informatiker Board | Theoretische Informatik | Erste Anfänge mit der O-Notation

Informatiker Board » Themengebiete » Theoretische Informatik » Erste Anfänge mit der O-Notation

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Seiten (2): [1] 2 nächste »

Erste Anfänge mit der O-Notation

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Erste Anfänge mit der O-Notation

Zitatantwort auf diesen Beitrag erstellen

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Shizmo: 03.03.2016 21:48.

03.03.2016 21:42

Nehmen Sie Shizmo in Ihre Freundesliste auf

Tomato
unregistriert

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

03.03.2016 22:36

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

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

03.03.2016 23:31

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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.

__________________
Syntax Highlighting fürs Board (Link)

04.03.2016 08:58

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

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?

Shizmo hat dieses Bild (verkleinerte Version) angehängt:

04.03.2016 21:38

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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.

__________________
Syntax Highlighting fürs Board (Link)

05.03.2016 06:34

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

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?

05.03.2016 09:49

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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

__________________
Syntax Highlighting fürs Board (Link)

05.03.2016 09:56

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

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

05.03.2016 10:09

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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

__________________
Syntax Highlighting fürs Board (Link)

05.03.2016 11:11

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

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

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Shizmo: 05.03.2016 11:42.

05.03.2016 11:30

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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.

__________________
Syntax Highlighting fürs Board (Link)

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von eulerscheZahl: 05.03.2016 11:42.

05.03.2016 11:41

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

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

Shizmo hat dieses Bild (verkleinerte Version) angehängt: