O-Notation vereinfachen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:40 So 14.10.2018 | | Autor: | Hela123 |
| Aufgabe | Finden Sie für folgende Funktionen [mm]f_i[/mm] eine möglichst einfache Funktion [mm]g_i[/mm], sadass [mm]f_i = \Theta(g_i)[/mm] gilt.
1) [mm]f_1(n) = n^{18} + e^n[/mm]
2) [mm]f_2(n) = log_2(25n + 175)[/mm]
3) [mm]f_3(n) = \frac{1}{n^2} + 3,5[/mm]
4) [mm]f_4(n) = log_2(log_2(n + 7))[/mm] |
Hallo Forum,
ich habe die Aufgabe so gelöst:
1) [mm]g_1(n) = e^n[/mm]
2) [mm]g_2(n) = log_2(n)[/mm]
3) [mm]g_3(n) = \frac{1}{n^2}[/mm]
4) [mm]g_4(n) = log_2(log_2(n))[/mm]
Es kommt mir aber komisch einfach vor. Ist es korrekt?
Schönen Dank im Voraus!
Hela123
|
|
| |
|
Falls dies die Definition von O ist:
f(x)=O(g(x)) [mm] \gdw \left|\bruch{f(x)}{g(x)}\right| \mapsto [/mm] 1 für x nach [mm] \infty,
[/mm]
ist fast alles richtig.
Bei 3) gibt es da ein kleines Problem...
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:42 Mo 15.10.2018 | | Autor: | Hela123 |
Hallo HJKweseleit,
vielen Dank für Deine Antwort!
> Falls dies die Definition von O ist:
> f(x)=O(g(x)) [mm]\gdw \left|\bruch{f(x)}{g(x)}\right| \mapsto[/mm]
> 1 für x nach [mm]\infty,[/mm]
Die O-Notation ist wie folgt definiert:
[mm]O(f) = \{g| \mbox{ es existiert ein } n_0 \ge 0 \mbox{ und ein } C>0, \mbox{ so dass } g(n) \le C f(n) \mbox{ für alle } n \ge n_0\}[/mm]
> Bei 3) gibt es da ein kleines Problem...
Ok, heißt es, 3.5 ist "stärkere" Summand und g(x)=3.5?
Noch mal danke und viele Grüße
Hela123
|
|
|
| |
|
Also dann etwa
f(x) [mm] \in [/mm] O(g(x)) [mm] \gdw \left|\bruch{f(x)}{g(x)}\right| \le [/mm] C für x nach [mm] \infty. [/mm] Dann enthielte für g(x) = ganzrationale Fkt. n-ter Ordnung O(g(x)) alle ganzrationalen Fkt. n-ter oder kleinerer Ordnung.
Ok, heißt es, 3.5 ist "stärkere" Summand und g(x)=3.5?
Ja, bei 3) kannst du 3,5 oder auch 1 nehmen, weil C ja noch eine beliebige Kontante ist.
|
|
|
|
