 Frage zu Groß-Omega |
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
 |
|
Hallo 
![[latex]f(n):= 5n \cdot log(n) \,\,\,\, g(n) := 10n+5[/latex]](http://www.matheboard.de/latex2png/latex2png.php?f(n):= 5n \cdot log(n) \,\,\,\, g(n) := 10n+5)
Eigentlich soll ich zeigen ![[latex]g \not\in \Theta(f)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?g \not\in \Theta(f))
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]](http://www.matheboard.de/latex2png/latex2png.php?c_1 \cdot 5n\cdot log(n) \leq 10n+5)
Vor allem er will: ![[latex]c_1 \in \mathbb{R^+}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?c_1 \in \mathbb{R^+})
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.
LG
|
|
06.05.2016 02:40 |
|
|
|
|
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]](http://www.matheboard.de/latex2png/latex2png.php?\lim_{n \to \infty}\log(n) = \infty) . Daran kannst du mit einem Konstanten Faktor nichts ändern.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
06.05.2016 06:27 |
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
Hmm ja theoretisch versteh ich das eigentlich, aber ich wähl ein c: =1 und n = 8
![[latex]1 \cdot 120 \leq 85[/latex]](http://www.matheboard.de/latex2png/latex2png.php?1 \cdot 120 \leq 85)
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.
|
|
|
06.05.2016 09:30 |
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
Ok, ok, dann nehm ich das mal so hin. 
Vielen Dank!!
|
|
|
06.05.2016 11:05 |
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
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]](http://www.matheboard.de/latex2png/latex2png.php?c_1 \cdot 5n\cdot log(n) \leq 10n+5 \equiv c_1 \cdot n \cdot log(n) \leq 2n+1)
dann hat er abgeschätzt: ![[latex]\leq 3\cdot n[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\leq 3\cdot n)
![[latex]\Rightarrow c_1 \cdot n\cdot log(n) \leq 3\cdot n \equiv c_1 \cdot log(n) \leq 3[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\Rightarrow c_1 \cdot n\cdot log(n) \leq 3\cdot n \equiv c_1 \cdot log(n) \leq 3)
Widerspruch
|
|
|
21.05.2016 23:16 |
|
|
|
