O-Notation Theta Beweis?
Hallo zusammen,
ich habe eine Verständnisfrage zur Aufgabe a und c (siehe Anhang).
Es ist ja so, dass bei a, im Grunde doch beides gleich schnell wächst, so dass wenn ich beispielsweise als konstante 999 wähle, dass 999 * n^7 / 2n^7 + 1000n^7 zu einer endlichen Zahl führt..
Laut der Definition, darf die Funktion nur höchstens so schnell wachsen wie n hoch 7, und da beide gleich schnell wachsen, trifft dies doch zu, oder?
Bei C habe ich nun aber das gleiche Ergebnis, hier ist es ja so, dass die Funktionnur gleich schnell wachsen darf, wie n quadrat, und auch hier trifft dies zu, da wenn ich beide dividiere, immer ein endliches Ergebnis dabei herauskommt, richtig?
Dementsprechend ist es doch so, dass beispielsweise die Aufgabe a, sowohl stimmen würde, wenn dort das O als auch das Theta (O mit einem Strich in der Mitte) stehen würde, oder?
Freue mich riesig über eine Erklärung!
Weiterhin muss ich solche Aufgaben wie im Anhang zu sehen, beweisen. Wie gehe ich da vor? Muss ich da einfach die Funktion durch g(n) teilen, und bestimmen, ob ein endlicher Wert rauskommt etc, oder es zu 0 führt, bei n gegen unendlich, und dementsprechend einordnen?
LG
1 Antwort
Diese völlig antiquierte "Landau-Symbolik" führt offenbar immer noch ein Randdasein in Reservaten im Riesenreich der Zahlentheorie... (oder wo kommt dieser unselige Spuk in diesem Fall her?). Wer quält euch denn nur mit so etwas? Also wenn's denn unbedingt sein muss:
a) besagt, dass
- eine Trivialität, weil die linke Seite offensichtlich gegen 2 konvergiert.
b) besagt:
- was aus demselben Grund trivial ist.
c) besagt (wahrscheinlich, muss ich sagen, denn ich kenne die Schreibweise nur mit dem Elementzeichen statt des Gleichheitszeichens):
- und auch das ist völlig klar,l weil die linke Seite gegen 1/2 konvergiert.
Völlig ohne Witz, völlig ohne Belang. Wer stellt bloß solche Aufgaben?
Ein Minimum an Interesse kann die Notation allenfalls beanspruchen, wenn die Folge, die durch die Quotientenbildung entsteht, verschiedene Häufungswerte hat, so dass man zwischen dem kleinsten und dem größten unterscheiden muss.
Du hast allerdings nur die Notation angegeben, ohne ihre Definition. Meine Antwort gilt nur unter dem Vorbehalt, dass die mir bekannte Bedeutung auch die in der Aufgabe gemeinte ist. Denn selbst vor abweichenden Erklärungen der Landau-Symbole ist man in der Literatur nicht sicher.
Dabei könnte Zahlentheorie so schön sein!!
Ach was. Es gibt keine "unumgänglichen Notationen", sondern nur gute und schlechte. Und die "Landau-Notationen" sind einfach schlecht, wie man schon am völlig inadäquaten Gebrauch des Gleichheitszeichens in ihr sieht.
Okay, das war mißverständlich ausgedrückt.
Die Notation kann ich natürlich prinzipiell austauschen, das Konzept als solches wird aber schon benötigt.
Also dann, frisch ans Werk!
(Und ja, 'Element von' ist verbreiteter als Gleichheitszeichen)
Landau-Notation ist bei LAufzeitbetrachtungen udn Speicherplatzbetrachtungen unumgänglich.