Wachstum von Funktion zeigen (Landau-o)

Neue Frage »

Studentu Auf diesen Beitrag antworten »
Wachstum von Funktion zeigen (Landau-o)
Liebe Boardcommunity,
mich würde eure Meinung zu meiner folgenden Überlegung interessieren:

Zeigen möchte ich, dass , wenn r konstant ist und l eine Funktion in ist, wobei d eine vorgegebene Konstante (eine natürliche Zahl) ist.

Meine Idee dazu ist, dass das ja bedeutet, zu zeigen, dass
, was gekürzt bedeutet, , was wiederum offensichtlich ist, da l schneller wächst als das konstante r.
Stimmt das so oder hab ich was übersehen? Und spielt die Konstante d überhaupt eine Rolle oder kann man sie auch einfach weglassen (ich denke Letzteres?)?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Studentu
und l eine Funktion in ist

Wenn positiv ist, wird das z.B. durch die konstante Funktion erfüllt.

Für eine Konstante ist aber mitnichten , sondern allenfalls in .


EDIT: Aber auch klappt i.a. nicht. Meinst du am Ende ? Allem Anschein nach solltest du SORGFÄLTIG darüber nachdenken, welche Landau-Symbole an welcher Stelle du WIRKLICH meinst.
 
 
Studentu Auf diesen Beitrag antworten »

Hallo Hal9000, ich meine das kleine o und meine Frage bezieht sich auf S. 148 im Buch "Finite Automata, Formal Logic, and Circuit Complexity" von Straubing.
Da wird in einem Beweis nämlich verwendet, (wobei d konstant ist, und l = 2r).
Dann schreibt er noch "wenn r konstant ist, dann ist nicht in , aber dann kann l als eine Funktion gewählt werden, die in ist und die "increases without bound"."

Genaugenommen ist mir auch die erste Zeile schon nicht klar. Kannst du mir erklären, warum das gilt?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Studentu
Hallo Hal9000, ich meine das kleine o

Da habe ich oben ein Gegenbeispiel genannt. unglücklich

Zitat:
Original von Studentu
da l schneller wächst als das konstante r.

Unsinn: Über ein Mindestwachstum wird bei überhaupt nichts ausgesagt. unglücklich

Daher ja auch mein Hinweis, dass du dir über das richtige Landau-Symbol Gedanken machen sollst. Aber anscheinend drehen wir uns im Kreis, daher will ich nicht länger "missionieren". Wink
Studentu Auf diesen Beitrag antworten »

Hallo Hal9000,
dann scheine ich das Symbol falsch aufgefasst zu haben. Ich habe von "Klein-O" gesprochen, weil das eben in dem Text das kleine o verwendet wird. Und ich dachte, es wäre im Kontext auch dieses gemeint.
Für welches Landau-Symbol würde es denn mehr Sinn machen bzw. wie würdest du es auffassen?

Und wie kommst du auf ein Mindestwachstum? So wie ich es verstanden habe, geht es darum, zu zeigen, dass es eben weniger schnell als wächst. Das "increases without bound" habe ich auf Englisch aus dem Text übernommen, weil ich mir eben nicht sicher war, wie es gemeint ist.
HAL 9000 Auf diesen Beitrag antworten »

Muss ich das NOCHMAL wiederholen ... Ich rede davon:

Zitat:
Original von Studentu
und l eine Funktion in ist, wobei d eine vorgegebene Konstante (eine natürliche Zahl) ist.

[...]

was wiederum offensichtlich ist, da l schneller wächst als das konstante r.

Was Unsinn ist, wie das Beispiel zeigt, und für dieses Beispiel gilt zweifelsohne , weil (siehe Definition von ) ja



gilt. Damit bricht deine Argumentation oben vollkommen zusammen.


EDIT: Vermutlich ist das das Problem:

Zitat:
Original von Studentu
und die "increases without bound"."

Das ist also als zusätzliche (!) Bedingung zu verstehen! D.h., es wird nicht nur gefordert, sondern zudem noch . Dann würde das ganze endlich Sinn machen.
Studentu Auf diesen Beitrag antworten »

Okay, jetzt verstehe ich genau, was du gemeint hast! Ja, dann ist es eine zusätzliche Bedingung an l. Wundert mich nur, dass er die (im ersten Fall, wo l=2r ist) nicht auch an r gestellt hat...
Wie würde man "increases without bound" dann korrekt ins Deutsche übersetzen, damit es die gemeinte Bedeutung behält? Und bedeutet "increases without bound" immer, dass es in liegt oder was genau?
Studentu Auf diesen Beitrag antworten »

Gibt es noch jemand, der die Frage beantworten könnte, bitte?
Studentu Auf diesen Beitrag antworten »

Ich bin nach wie vor an einer Antwort interessiert, falls jemand eine hat.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »