Wachstum von Funktion zeigen (Landau-o) |
15.01.2020, 17:15 | Studentu | Auf diesen Beitrag antworten » | ||||
Wachstum von Funktion zeigen (Landau-o) 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?)? |
||||||
15.01.2020, 17:21 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
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. |
||||||
16.01.2020, 19:45 | 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? |
||||||
16.01.2020, 21:46 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Da habe ich oben ein Gegenbeispiel genannt.
Unsinn: Über ein Mindestwachstum wird bei überhaupt nichts ausgesagt. 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". |
||||||
16.01.2020, 22:16 | 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. |
||||||
16.01.2020, 22:56 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Muss ich das NOCHMAL wiederholen ... Ich rede davon:
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:
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. |
||||||
Anzeige | ||||||
|
||||||
17.01.2020, 17:59 | 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? |
||||||
19.01.2020, 17:30 | Studentu | Auf diesen Beitrag antworten » | ||||
Gibt es noch jemand, der die Frage beantworten könnte, bitte? |
||||||
21.01.2020, 18:28 | Studentu | Auf diesen Beitrag antworten » | ||||
Ich bin nach wie vor an einer Antwort interessiert, falls jemand eine hat. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|