Landau Notation < gewöhnliche < Differentialgl. < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:25 Mi 17.01.2007 | | Autor: | BenRen |
Hallo,
ich habe hier einige Aufgaben zu "lösen" - es geht darum, den Wahrheitsgehalt von Aussagen zu bestimmen und zu begründen, warum man "wahr" oder "falsch" gewählt hat.
Leider habe ich noch Probleme, die Landau Notation (O) zu verstehen. Ich gebe hier einmal die erste Aufgabe als Beispiel an:
Aus n [mm] \ge [/mm] m folgt [mm] x^{n} [/mm] = O( [mm] x^{m} [/mm] ) für x [mm] \to [/mm] 0
(eine zweite Aufgabe ist diesselbe, nur das am Ende "für x [mm] \to \infty" [/mm] steht.
Meine Überlegung ist nun folgende:
Die O-Notation gibt in der Mathematik ja an, wie schnell eine Funktion wächst. Nach meinem Wissen heißt [mm] "x^{n} [/mm] = O( [mm] x^{m} [/mm] )" also, dass [mm] x^{n} [/mm] höchstens so schnell wie [mm] x^{m} [/mm] wächst.
Plotte ich mir die beiden Funktionen, so sehe ich klar, dass [mm] x^{n} [/mm] schneller wächst als [mm] x^{m}, [/mm] wenn ich ein n > m wähle. Nun könnte ich ja salopp sagen, nein, die Aussage stimmt nicht, also [mm] x^{n} \not\in [/mm] O( [mm] x^{m} [/mm] ). Aber diese Überlegung ist falsch oder zu simpel - was genau ich nicht verstehe, ist das "für x [mm] \to [/mm] 0" am Ende. Wie soll ich das verstehen, wenn x gegen 0 geht, dann werden die Funktionswerte doch auch 0, also würde für x = 0 ja [mm] x^{n} \in [/mm] O( [mm] x^{m} [/mm] ) gelten?
Ihr seht, meine Verständnis für die Aufgabe oben ist nicht gerade einwandfrei. Ich würde mich sehr freuen, wenn ihr mir die gestellte Aufgabe einmal mit Worten erklären könntet, ohne nun anzugeben, ob der Wahrheitsgehalt wahr oder falsch ist (das würde ich dann gerne selbst schlussfolgern :).
Vielen Dank!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:27 Fr 19.01.2007 | | Autor: | BenRen |
Weiß denn keiner einen Rat? Auch wenn die Frage oben schon überfällig ist, würde es mich dennoch sehr interessieren, um zukünftige Aufgaben in demselben Bereich besser verstehen zu können.
Vielen Dank!
|
|
|
| |
|
Ok,
machen wir uns doch mal klar, was [mm]x^n \in O(x^m)[/mm] heisst.
Das heisst, [mm] x^n [/mm] wächst höchstens so schnell wie [mm] x^m.
[/mm]
Gucken wir uns erstmal den Grenzwert (der wichtig ist bei der Landau-Notation!) an. Erstmal für [mm]x\to\infty[/mm] Wie du ja selbst schon erkannt hast, stimmt das einfach nicht, weil für grosse x,[mm]n\ge m[/mm] wächst [mm] x^n [/mm] nunmal schneller als [mm] x^m. [/mm]
Im zweiten Fall guck dir mal die Graphen an, wenn du eben nicht von 0 nach rechts auf der x-Achse wanderst, sondern von irgendwo rechts auf die Null zu. (Also [mm]x\to 0[/mm])
Was fällt dir auf?
Gruß,
Gono.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 16:34 Fr 19.01.2007 | | Autor: | BenRen |
Hallo,
vielen Dank für Deine Antwort.
> Im zweiten Fall guck dir mal die Graphen an, wenn du eben
> nicht von 0 nach rechts auf der x-Achse wanderst, sondern
> von irgendwo rechts auf die Null zu. (Also [mm]x\to 0[/mm])
> Was
> fällt dir auf?
mir fällt auf, dass der Unterschied des Wachstums der Funktionen immer geringer wird. Ich vermute mal, dass bei 0 der Wachstum gleich groß ist? Das bedeutet, [mm] x^{n} [/mm] wächst dann genauso schnell wie [mm] x^{m}, [/mm] denn wenn "x gegen 0" ist der Grenzwert ja 0.
Wenn die Folgerung stimmt, ist
"Aus n [mm] \ge [/mm] m folgt [mm] x^{n} [/mm] = O( [mm] x^{m} [/mm] ) für x [mm] \to [/mm] 0"
ja falsch, denn [mm] x^{n} [/mm] = O( [mm] x^{m} [/mm] ) heißt "wächst höchstens so schnell" und nicht "genau so schnell".
Ist das so richtig verstanden?
Falls ja, dann könnte ich ja bei fast allen Aussagen, wo x gegen 0 geht sagen, dass es falsch ist (wenn es um das große O, also "wächst höchstens so schnell wie" geht)?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 So 21.01.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 10:28 Mo 22.01.2007 | | Autor: | BenRen |
> Wie angekündigt gehen wir nun davon aus, dass Du an einer Antwort nicht mehr interessiert bist.
> Die Frage taucht nun nicht mehr in der Liste der offenen Fragen, sondern nur noch in der Liste der
> Fragen für Interessierte auf. Falls Du weiterhin an einer Antwort interessiert bist, stelle einfach eine
> weitere Frage in dieser Diskussion.
Das mach ich doch gerne, denn ich bin immmernoch an einer Antwort interessiert. Jemand hatte mir geantwortet, was mir nur ein klein wenig weiter geholfen hat, und daraufhin habe ich meine eigene Schlussfolgerung forumliert, weiß nur leider nicht, ob diese richtig ist (siehe meinen letzten Post weiter oben).
Über weitere Hilfe würde ich mich sehr freuen!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:20 Fr 26.01.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
