O-Notation Wahr oder Falsch < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:29 So 27.03.2005 | | Autor: | Tyvan |
Hallo Leute,
ich habe vor kurzem eine Klausur gehabt und es gab Fragen zur O-Notation, dabei waren diese nur Wahr/Falsch Fragen, ich musste also nur ankreuzen, habe bei der Klausureinsicht dann gesehen das ich gut die Hälfte falsch hatte.
Deswegen habe ich hier mal einiges, ich würde das ganze mal gerne besser verstehen, ich habe das Gefühl das ich das genau andersrum versteh.
Hier 4 Beispiele:
1. [mm] Omega(n^{2}) \supseteq [/mm] Omega(n)
2. O(n * log n) [mm] \supseteq O(n^{2})
[/mm]
3. [mm] O(n^{4}) \in Omega(n^{4})
[/mm]
4. [mm] 2n^{2} [/mm] * log n [mm] \in O(n^{2})
[/mm]
Die Frage hier ist einfach ob diese 4 Wahr oder Falsch sind.
z.B. Nr.1: Omega bedeutet ja, das eine Funktion f(x) maximal ein Wachstum hat wie Omega(n) zum Beispiel. Das heisst also für Nr.1: Alle Funktionen die maximal wie n wachsen sind eine Teilmenge wie die Funktionen die maximal wie [mm] n^{2} [/mm] wachsen, habe ich das richtig geschrieben?
Bei dieser Frage würde ich WAHR ankreuzen, weil es ja bei Omega keine untere Grenze gibt, daher ist bei [mm] n^{2} [/mm] eine obere Grenze festgelegt, was auch als obere Schranke für n dient, gell?
Nr.2: würde ich WAHR ankreuzen, da n*log n eine untere Grenze von [mm] n^{2} [/mm] darstellt und es hier nun keine obere Grenze gibt, oder?
Nr.3: wäre FALSCH, da die Schranken der beiden direkt nebeneinander sind, also [mm] Omega(n^{4}) [/mm] ist eine obere Schranke, und bei [mm] O(n^{4}) [/mm] wachsen die Funktionen da wo es bei Omega aufhört, deswegen FALSCH.
Nr.4: hier bin ich schon etwas verwirrt, da es hier kein O oder Omega gibt. [mm] 2n^{2} [/mm] * log n steht hier völlig allein, ohne O oder Omega, was nun Element von [mm] O(n^{2}) [/mm] sein soll, ich würde hier mal FALSCH ankreuzen da [mm] 2n^{2} [/mm] * log n weit unter der Schranke von [mm] O(n^{2}) [/mm] anfängt, deswegen NICHT Element. Oder?
Danke im voraus für die Antworten. 
Vielleicht könnte jemand noch ein paar Tipps für sowas geben, vielleicht hat jemand von euch ein gutes Schema oder so um dies besser zu erkennen.
|
|
| |
|
Hallo Tyan,
Wie ist denn "bei euch" Omega(n) und O(n) definiert?
Bezeichnungen sind halt (leider oder zum Glück) nicht einheitlich.
gruß
mathemaduenn
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:19 Mo 28.03.2005 | | Autor: | Tyvan |
Definition der O-Notation ist:
O(f) = {g | [mm] \exists [/mm] c > 0: [mm] \exists n_{0} [/mm] > 0: [mm] \forall [/mm] n [mm] \ge n_{0}: [/mm] g(n) [mm] \le [/mm] c * f(n)}
Definition der Omega-Notation ist:
Omega(g) = {h | [mm] \exists [/mm] c > 0: [mm] \exists n_{0} [/mm] > 0: [mm] \forall [/mm] n [mm] \ge n_{0}: [/mm] h(n) [mm] \ge [/mm] c * g(n)}
|
|
|
| |
|
Hallo Tyvan,
Ich schreibe mal Deine Definitionen ab:
Definition der O-Notation ist:
O(f) = {g | [mm] \exists [/mm] c > 0: [mm] \exists n_{0} [/mm] > 0: [mm] \forall [/mm] n [mm] \ge n_{0}: [/mm] g(n) [mm] \le [/mm] c * f(n)}
Definition der Omega-Notation ist:
Omega(g) = {h | [mm] \exists [/mm] c > 0: [mm] \exists n_{0} [/mm] > 0: [mm] \forall [/mm] n [mm] \ge n_{0}: [/mm] h(n) [mm] \ge [/mm] c * g(n)}
Du hast also Mengen von Funktionen oder Folgen ( das ist nicht ersichtlich aber auch nicht unbedingt wichtig)
Anfangen möchte ich mit 4.
Hier hast Du also eine Folge gegeben [mm] n^2*log(n)
[/mm]
Ist diese in der Menge [mm] O(n^2)
[/mm]
In die Definition gucken
[mm] \exists [/mm] c > 0: [mm] \exists n_{0} [/mm] > 0: [mm] \forall [/mm] n [mm] \ge n_{0}: n^2*log(n) \le [/mm] c * [mm] n^2
[/mm]
kürzen
[mm] \exists [/mm] c > 0: [mm] \exists n_{0} [/mm] > 0: [mm] \forall [/mm] n [mm] \ge n_{0}: [/mm] log(n) [mm] \le [/mm] c
Also keine Element der Menge. Klar?
Für 1.u.2. kannst Du analog vorgehen
n [mm] \in [/mm] Omega(n) Hier ist die Ungleichung offensichtlich erfüllt. Wenn nun Omega(n) eine Obermenge von [mm] Omega(n^2) [/mm] ist mus n auch in [mm] Omega(n^2) [/mm] enthalten sein.
Gleiches bei 2.
Zu 3. [mm] O(n^4) [/mm] ist eine Menge von Folgen. Als solche kann sie schlecht Element einer Menge sein die als Elemente nur Folgen hat.
Alles klar?
gruß
mathemaduenn
|
|
|
|
