Informatiker Board | Druckvorschau: Frage zu Groß-Omega

Geschrieben von Shizmo am 06.05.2016 um 02:40:

Frage zu Groß-Omega

Hallo Wink

$[latex]f(n):= 5n \cdot log(n) \,\,\,\, g(n) := 10n+5[/latex]$

Eigentlich soll ich zeigen $[latex]g \not\in \Theta(f)[/latex]$
Ich hab mir gedacht ich teils auf, ich zeige dass es entweder nicht in Groß-O oder nicht in Groß-Omega ist, in Groß-O ist es, das ist nicht schwer zu zeigen, aber wie zeige ich am einfachsten, dass es nicht in Groß-Omega ist.

$[latex]c_1 \cdot 5n\cdot log(n) \leq 10n+5[/latex]$

Vor allem er will: $[latex]c_1 \in \mathbb{R^+}[/latex]$

Wenn ich jetzt ewig rumprobiere find ich trotzdem immer wieder eine Konstante (eine sehr kleine Konstante zB 0.000000000000000000000000000000000000000000000001) und dann ist der linke Teil wieder kleiner.

verwirrt

Geschrieben von eulerscheZahl am 06.05.2016 um 06:27:

Und wenn du dann das n wählst, findest du eins, das die Ungleichung nicht mehr erfüllt.
Und da das c zuerst gewählt wird, kann im Anschluss immer ein solches n gefunden werden.
$[latex]\lim_{n \to \infty}\log(n) = \infty[/latex]$ . Daran kannst du mit einem Konstanten Faktor nichts ändern.

Geschrieben von Shizmo am 06.05.2016 um 09:30:

Hmm ja theoretisch versteh ich das eigentlich, aber ich wähl ein c: =1 und n = 8
$[latex]1 \cdot 120 \leq 85[/latex]$
okay das passt, aber ich kanns ja auch immer so wählen dass es nicht passt bsp c=0.5 und n=8

Also ich mein damit, ich find immer ein c wo es passt, und ein c wo es nicht passt.
Also kann ich ja nie was zeigen, da ich mir immer wieder selbst widersprechen kann.

Geschrieben von eulerscheZahl am 06.05.2016 um 10:41:

Du wählst aber erst das c.
Und dann findest du ein passendes n.

Geschrieben von Shizmo am 06.05.2016 um 11:05:

Ok, ok, dann nehm ich das mal so hin. Augenzwinkern

Vielen Dank!!

Geschrieben von Shizmo am 21.05.2016 um 23:16:

Also mein Prof hat auch gesagt, dass man immer wieder ein kleineres c finden kann (so wie mein vorletzter Beitrag).

Seine Lösung war dann so:

$[latex]c_1 \cdot 5n\cdot log(n) \leq 10n+5 \equiv c_1 \cdot n \cdot log(n) \leq 2n+1[/latex]$

dann hat er abgeschätzt: $[latex]\leq 3\cdot n[/latex]$

$[latex]\Rightarrow c_1 \cdot n\cdot log(n) \leq 3\cdot n \equiv c_1 \cdot log(n) \leq 3[/latex]$

Widerspruch

Geschrieben von eulerscheZahl am 22.05.2016 um 06:58:

Kann man so machen.
Aber letztendlich läuft es auch wieder darauf hinaus, dass man zuerst das c wählt, dann das n.