Landau-Notation beweisen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Gegeben sei folgende Funktion:
[mm] f(x)=\left\{\begin{matrix}
3^x + 2 log(x), & \mbox{wenn }x < 10^5 \\
x log(x) + 5x, & \mbox{sonst}
\end{matrix}\right.
[/mm]
Beweisen oder widerlegen Sie f(x) = [mm] O(3^x), [/mm] f(x) = O(5x log(x)), f(x) = [mm] O(x^2) [/mm] |
Ich habe hierfür einmal die Definition von O angeschrieben:
O(g(x)) = {f(x) | [mm] (\exists [/mm] c,x0 > 0), [mm] (\forall [/mm] x [mm] \ge [/mm] x0) : 0 [mm] \le [/mm] f(x) [mm] \le [/mm] c g(x)}
Dann habe ich die Funktion eingesetzt. Ich muss es aber nur bei großen Werten beachten!
0 [mm] \le [/mm] log(x) + 5x [mm] \le [/mm] c x log(x)
Das durchdividieren:
0 [mm] \le \bruch{5}{log(x)} \le [/mm] c
Wie muss ich jetzt weiterrechnen? Ich weiß, dass [mm] \limes_{n \to \infty}\bruch{5}{log(x)} [/mm] = 0, aber hilft mir das?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:05 Di 28.10.2008 | | Autor: | Gilga |
aber hilft mir das?
Ja. man kann die Definition auch über Grenzwerte schreiben.
Dann sieht man es deutlicher.
Es geht ja darum zu zeigen dass die Funktion falls man x [mm] ->\infty [/mm] gehen lässt diese nicht stärker als die Funktion c x log(x) wächst.
PS: Die anderen Möglichkeiten sind auch wahr, da man nur noch oben beschränken muss
|
|
|
| |
|
Danke! Das ist mir klar, dass O(5x log(x)) < [mm] O(n^2) [/mm] > [mm] O(3^n) [/mm] ist.
Aber ich verstehe leider noch immer nicht warum das jetzt bewiesen ist. Wenn ich z.B. n0 = 2 und c = 5 einsetze, dann stimmt diese Ungleichung ja nicht mehr???? 0< 16,61 < 5
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:24 Do 30.10.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
