O Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:18 Sa 12.04.2008 | | Autor: | wolle238 |
| Aufgabe | Gegeben seien die Funktionen
[mm] f_1 (n) = 2n + 5 \, log \, n [/mm]
[mm] f_2 (n) = 3n \cdot log n + 4 \cdot \wurzel{n} [/mm]
[mm] f_3 (n) = 7n^2 \cdot \wurzel{n} [/mm]
[mm] g_1 (n) = \wurzel{n} [/mm]
[mm] g_2 (n) = n [/mm]
[mm] g_3 (n) = n \, log \, n [/mm]
[mm] g_4 (n) = n^2 [/mm]
Geben Sie (ohne Beweis) die Paare (i, j) an, für die [mm] f_i (n) \in O(g_j (n)) [/mm] gilt. Verwenden Sie hierbei die in der Vorlesung erwähnte Verallgemeinerung der Notation O(f) für [mm] f : \IN \rightarrow \IR [/mm]! |
Hallo alle samt!!
Ich hab mal eine Frage zur der oben gestellten Aufgabe! Entweder habe ich die Aufgabe oder die O - Notation nicht verstanden. Als Definition für O-Notation habe ich mir aufgeschrieben:
O(f) := Alle Funktionen, die maximal so schnell wachsen wie die Funktion f.
Das heißt doch, dass [mm] g \in O(f) [/mm] auf jeden Fall langsamer, bzw. maximal genau so schnell wie f wächst (also immer unter dem Graphen von f bleibt), oder??
Weiter stand auf der Folie: [mm] O(f) = {g : \IN \rightarrow \IN | [/mm] Es existieren [mm] c_1 > 0 [/mm] und [mm] c_2 > 0 [/mm] für alle [mm] n \in \IN : g(n) \le c_1 \cdot f(n) + c_2} [/mm]
(http://www-wi.uni-muenster.de/pi/lehre/ss08/info2/folien/info2k1.pdf, Folie 6)
Ich habe mir die Funktionen mal gezeichnet. Bei diesen Aufgaben (http://www.wi.uni-muenster.de/pi/lehre/ss08/info2/uebungen/Uebung01.pdf; kompletter Aufgabenzettel) sollen die f-Funktionen ja maximal so schnell wachen wie die g-Funktionen (weil [mm] f_i (n) \in O(g_j (n)) [/mm] sein soll), oder sehe ich das falsch?? Aber beim Zeichnen hat sich ergeben, dass alle f-Funktionen schneller als die g-Funktionen! Irgendwie läuft das alles mal nicht! :(
Ich hoffe mir kann einer helfen!!
MfG und schonmal vielen Dank im Voraus!
Wolle
|
|
| |
|
So findet man also seine Kommilitonen wieder, hallo J. ;D
Also, pass auf.
g [mm] \in [/mm] O(f(n)) bedeutet nur, dass du entweder für alle n sagen kannst g(n) [mm] \le [/mm] a [mm] \times [/mm] f(n) + b
oder
ab einem bestimmten N sind alle g(n) [mm] \le [/mm] a [mm] \times [/mm] f(n)
Wobei a und b halt irgendwelche Konstanten sind. Das heißt, wenn du f multiplizierts (also die Steigung konstant vergrößerst) oder etwas addierst (also die ganze Funktion "höher legst") dann ist f größer/gleicht g.
Nimm zum Beuspiel f(n)=n und g(n) = 10.
Es gilt g(n) [mm] \le [/mm] f(n) + 11 oder ab n=10 gilt g(n) [mm] \le [/mm] f(n) (je nach dem welche Notation du bevorzugst).
Das geht auch so direkt aus dem Skript zum Übungszettel hervor.
Du musst eigentlich immer nur den Teil der Funktion mit dem heftigsten Wachstum betrachten. Zum Beispiel gilt für jedes Polynom vierten Gerades (auch wenn es 100000000000000 * [mm] n^{4} [/mm] + 100000000000000 * [mm] n^{3} [/mm] + 100000000000000 * [mm] n^{2} [/mm] + 100000000000000 * n + 100000000000000 ist), dass es in [mm] O(n^{4}) [/mm] liegt.
So und den Rest schaffst du alleine!
|
|
|
|
