Omega und Omega(inf) < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
wir haben in der Vorlesung zwei verschiedene Notationen für (groß)Omega durchgenommen. Die normale und die (groß)Omega(infinity) notation. Also so ein Symbol mit nem kleinem Infinity Symbol angehängt. Irgendwie wird mir der unterschied nicht so klar. Wäre über eine kurze Erklärung, die man auch als Laie nachvollziehen kann, dankbar.
f = Omega∞(g) ∧ g =Omega∞(h) != f = Omega∞(h):
(( Also nicht transitiv im Gegensatz zu allen anderen Landau-Symbolen...))
Wähle hierzu die Funktionen wie folgt f(n) = [mm] 1+(1+(-1)^n)n, [/mm] g(n) = n, und h(n) = n + (1 + [mm] (-1)^n)n² [/mm] = n · f(n).
Also das wäre eine Anwendung für Omega(inf)... Also nicht transitiv... Aber ich versteh hier irgendwie grad nur Bahnhof. Also wie gesagt wäre über eine kleine Hilfe sehr dankbar.
Hier mal übrigens die Definitionen für Omega und Omega(inf):
Omega(f) := {g : N → R+ : ∃c∈R.c>0, n0∈N: ∀n∈N.n≥n0: g(n) ≥ c · f(n)}
Omega∞(f) := {g : N → R+ : ∃c∈R.c>0: ∀m∈N: ∃n∈N.n>m: g(n) ≥ c · f(n)}
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Mi 21.05.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
