Fkt. ordnen anhand O-Symbol < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 00:17 Mi 29.10.2008 | | Autor: | Klemme |
| Aufgabe | Gegeben sind die folgenden 6 Funktionen
a) n [mm] \mapsto 4^{n/3}
[/mm]
b) n [mm] \mapsto n\wurzel[3]{n}
[/mm]
c) n [mm] \mapsto \bruch{n^{7}}{log(n^{2}+42)}
[/mm]
d) n [mm] \mapsto 3^{log(4/(n+1))} [/mm] + [mm] 3\wurzel[3]{n}
[/mm]
e) n [mm] \mapsto 42n^{2} [/mm] + n cos [mm] (\pi n^{2})
[/mm]
f) n [mm] \mapsto \bruch{n}{n + 42}
[/mm]
Bringen Sie die Funktionen in eine Reihenfolge f1, f2, f3, f4, f5, f6, so dass f1 [mm] \in [/mm] O(f2), f2 [mm] \in [/mm] O(f3), f3 [mm] \in [/mm] O(f4) usw. Begründen Sie kurz jede dieser 5 Beziehungen anhand der Definition des O-Symbols.) |
Hallo,
ich habe zu dieser Aufgabe eine Idee, weiß aber nicht ob ich die Groß Oh- Notation so richtig verstanden habe.
Es gilt ja g(n) [mm] \le [/mm] c* f(n)
Dies bedeutet dass z.B. wenn da steht "f1 [mm] \in [/mm] O(f2)", dass sie Menge aller Funktionen von f2 *c in f1 enthalten sind.
Definiere ich jetzt z.B. [mm] n_{0} [/mm] =1 und c =70. Kann ich jetzt ein beliebiges c definieren und dann die Funktionen ausrechnen und ordnen?
Ist der Beweis dann schon geführt wenn ich z.B. sage f1 = n [mm] \mapsto 4^{n/3} [/mm] und f2 = n [mm] \mapsto \bruch{n}{n + 42}
[/mm]
und dann zeige:
[mm] 4^{n/3}\in O(\bruch{n}{n + 42})
[/mm]
[mm] \to 4^{n/3}\le [/mm] c [mm] *(\bruch{n}{n + 42})
[/mm]
[mm] \to \bruch{4^{n/3}}{(\bruch{n}{n + 42})}\le [/mm] c
jetzt setze ich für [mm] n_{0}1 [/mm] ein:
68,25 [mm] \le [/mm] c
Falls dieser Ansatz stimmen sollte, wäre meine Frage, wie ich dann das "richtige" c finde. Falls das totaler Blödsinn ist, wäre ich für einen Lösungsansatz sehr dankbar.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:23 Mi 29.10.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
