O-Notation passenden b suchen |
27.12.2015, 18:31 | Adramelec | Auf diesen Beitrag antworten » | ||||
O-Notation passenden b suchen in einer O-Notation Aufgabe würde ich gern um eine Überprüfung bitten, ob ich das richtig gemacht habe: (wobei ich mir bei diesem Log(n) etwas unsicher bin ob man das wirklich so machen kann oder ob ich da nicht "zu groß" geworden bin .. :/ ) [attach]40217[/attach] Danke! |
||||||
30.12.2015, 20:04 | Adramelec | Auf diesen Beitrag antworten » | ||||
push |
||||||
30.12.2015, 20:24 | echnaton | Auf diesen Beitrag antworten » | ||||
Aus welcher Menge soll sein? Es ist für alle und . Die Abschätzung ist korrekt und sowieso. |
||||||
30.12.2015, 20:51 | Adramelec | Auf diesen Beitrag antworten » | ||||
Ahja, die Menge für b sind die natürlichen Zahlen |
||||||
30.12.2015, 21:08 | echnaton | Auf diesen Beitrag antworten » | ||||
Ok, hast du dann mit meinem Hinweis die Lösung? Viel kleiner kann eh nicht werden. |
||||||
30.12.2015, 21:27 | Adramelec | Auf diesen Beitrag antworten » | ||||
Dann ist b wohl 1. Aber verstehen tue ich es nicht ganz Ist es weil log(n) = O(log(n)). Auch (log(n))^2 = O(log(n)) und somit wäre das Ergebnis eigentlich O(log(n)) - aber da b aus den natürlichen Zahlen kommen muss, nehme ich das höchst größere und das ist 1? Danke! |
||||||
Anzeige | ||||||
|
||||||
30.12.2015, 21:59 | echnaton | Auf diesen Beitrag antworten » | ||||
Es stimmt, 1 ist das minimalste natürliche , aber deine Begründung ist falsch. Für alle reelle gilt . Die Begründung für den zweiten Summanden hast du selbst gegeben. Für den ersten schau dir nochmal meinen ersten Beitrag an.
|
||||||
30.12.2015, 22:08 | Adramelec | Auf diesen Beitrag antworten » | ||||
Hi, ich bin mir nicht sicher ob ich dich richtig verstehe, aber bedeutet, das egal wie hoch die Potenz von log(n) ist, die O-Notation ist immer O(1) Also als Beispiel: ? |
||||||
30.12.2015, 22:21 | echnaton | Auf diesen Beitrag antworten » | ||||
Nein, habe ich in diesem Zusammenhang nie behauptet.
Das stimmt, oder auch oder . Allgemein halt für alle und . |
||||||
30.12.2015, 22:25 | Adramelec | Auf diesen Beitrag antworten » | ||||
Danke. Und ja das O(1) war ein Tippfehler, ich wollte O(n) schreiben.. ;-) Danke nochmal! |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|