Asymptotische Laufzeitnotation < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 11:47 Sa 24.11.2007 | | Autor: | Smex |
| Aufgabe | Zur Geschwindigkeits- und Speicherverbrauchsanalyse bei Algorithmen verwendet man folgende Notationen:
[mm] O(g(n)):=\{f:\IN \to \IN / \exists c>0 und \exists n_0 \in \IN mit f(n) \le c*g(n) \forall n\gen_0\}
[/mm]
[mm] o(g(n)):=\{f:\IN \to \IN / \forall c>0 \exists n_0 \in \IN mit f(n) \le c*g(n) \forall n\gen_0\}
[/mm]
[mm] H(g(n)):=\{f:\IN \to \IN / \exists c>0 und \exists n_0 \in \IN mit f(n) \ge c*g(n) \forall n\gen_0\}
[/mm]
[mm] \odot(g(n)):=O(g(n)) \cap [/mm] H(g(n))
Wenn bspw. die Anzahl der Rechenschritte eine Programms durch f(n) in Abhängigkeit der Eingabegröße n gegeben ist, bedeuten obige Definitionen:
f(n)=O(g(n)): Auf jedem Rechner benötigt man maximal irgendeine Konstante mal g Rechenschritte (spätestens ab einem gewissen n)
f(n)=o(g(n)):Die Laufzeit von f hat echt kleinere Größenordnung als g (man könnte schreiben O(f(n))<O(g(n)) [mm] \gdw [/mm] f(n) < o(g(n)))
f(n)=H(g(n)):man braucht mindestens c*g(n) Rechenoperationen (untere Schranke)
[mm] f(n)=\odot(g(n)):wegen [/mm] f(n)=O(g(n)) braucht f maximal c*g Schritte und wegen f(n)=H(g(n)) braucht f minimal c*g Schritte.
Sind die folgenden Aussagen wahr oder falsch? Führen sie einen Beweis.
1. [mm] n^6 [/mm] = [mm] O(2^n)
[/mm]
2.log(n+1) = O(logn)
3. [mm] 42n^3+13n^2+2n+500 [/mm] = [mm] O(n^3) [/mm] |
Naja, also ich verstehe die Aufgabe so mehr oder weniger gar nicht und ich wäre sehr dankbar, wenn mir jemand erklären könnte was ich machen soll, oder vielleicht eine der Aufgaben mal exemplarisch vorrechenen könnte.
Vielen Dank
Lg Smex
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:37 So 25.11.2007 | | Autor: | wilhelm |
Hi,
du kannst mal unter Wikipedia nach Landau-Symbolen gucken, dann sollte es etwas klarer werden. Unser Tutor meinte auch, dass es reicht, um es zu beweisen, zuzeigen wogegen [mm] \limes_{n\rightarrow\infty} \bruch{f(x)}{g(x)} [/mm] strebt.
|
|
|
|
