Erste Anfänge mit der O-Notation |
03.03.2016, 21:42 | Auf diesen Beitrag antworten » | ||||||||||||||
Shizmo | Erste Anfänge mit der O-Notation Hallo, die Ferien sind vorbei und es geht wieder los mit meinen lästigen Fragen Dieser Thread wird vermutlich etwas länger werden, aber ich stelle die Fragen nach und nach und zwar fange ich mal mit der Definition an: Also laut Vorlesung sieht die so aus: Sei eine Funktion. Es existierten Konstanten , sodass für alle gilt Also: Frage 1: ist eine Konstante. Was genau ist ? Frage 2: Ich suche eine "formal mathematisch exakte Definition", ist die oben geschriebene Definition mathematisch exakt? Oder lt. Wikipedia gäbe es auch noch diese Definition: Was wäre denn die formale mathematische exakte Definition? LG |
||||||||||||||
|
|||||||||||||||
03.03.2016, 22:36 | Auf diesen Beitrag antworten » | ||||||||||||||
Tomato | ist die natürliche Zahl, ab der die Ungleichung gilt. Die beiden Definitiinen sind äquivalent und mathematisch korrekt. |
||||||||||||||
03.03.2016, 23:31 | Auf diesen Beitrag antworten » | ||||||||||||||
Shizmo | RE: Erste Anfänge mit der O-Notation Vielen Dank für deine Antwort. Hmm, warum steht bei uns in den Folien
Also Und auf Wiki:
Also ich mein das größer bzw. größer-gleich... |
||||||||||||||
04.03.2016, 08:58 | Auf diesen Beitrag antworten » | ||||||||||||||
eulerscheZahl | Letztendlich läuft es aufs gleiche hinaus: Bei musst du eben um 1 größer wählen als bei . Da du das aber beliebig wählen darfst, ist das egal. |
||||||||||||||
Anzeige | |||||||||||||||
|
|||||||||||||||
04.03.2016, 21:38 | Auf diesen Beitrag antworten » | ||||||||||||||
Shizmo | Ah okay alles klar vielen Dank. Dann zum nächsten, siehe Anhang. Also rein intuitiv würde ich halt mit den log-Ausdrücken anfangen, dann mit den Konstanten, dann quatratischen, kubischen und zuletzt die exponentiellen Ausdrücke. Aber man sollte das ja auch irgendwie berechnen können oder? Wie geh ich da am besten vor? |
||||||||||||||
05.03.2016, 06:34 | Auf diesen Beitrag antworten » | ||||||||||||||
eulerscheZahl | Die Konstante ist kleiner als der Logarithmus. Nach deiner Definition: Wähle (für Basis 2 im Logarithmus). Damit ist gezeigt . In die andere Richtung geht das nicht. In der O Notation sind Konstanten am kleinsten, dann Logarithmen, Polynome (nach Grad sortiert), dann exponentielle Funktionen. |
||||||||||||||
05.03.2016, 09:49 | Auf diesen Beitrag antworten » | ||||||||||||||
Shizmo | Vielen, vielen Dank. Ich kann dein Beispiel sehr gut nachvollziehen, nur noch generell, kann ich und immer beliebig wählen, sodass es in meine Ungleichung passt? Und das ersetzt einfach immer mein von den Ausdrücken? Also zB: Wähle Also Stimmt das so? Kann ich mein und beliebig wählen, also in dem Fall beide 1? |
||||||||||||||
05.03.2016, 09:56 | Auf diesen Beitrag antworten » | ||||||||||||||
eulerscheZahl | Du kannst c erstmal beliebig wählen. Das n0 musst du dann aber berechnen. Wenn du das c geschickt wählst, kannst du es dir beim n aber leichter machen. Und die Ungleichung muss nicht nur für n0 gelten, sondern auch für jedes n darüber. In deinem Beispiel ist das nicht der Fall (n=43 geht nicht). Deshalb ist auch , wohl aber |
||||||||||||||
05.03.2016, 10:09 | Auf diesen Beitrag antworten » | ||||||||||||||
Shizmo |
Ahh, perfekt, genau das wollte ich wissen. Aber was meinst du genau damit, dass ich n0 berechnen muss? Anderes Beispiel: Wähle (wenn n0=1) Und es dürfte auch für größere n's gelten, zB n0=9 Also Was hältst du davon?? |
||||||||||||||
05.03.2016, 11:11 | Auf diesen Beitrag antworten » | ||||||||||||||
eulerscheZahl | Passt. Mit n0 berechnen meine ich du musst ein n0 finden, das die Ungleichung erfüllt. |
||||||||||||||
05.03.2016, 11:30 | Auf diesen Beitrag antworten » | ||||||||||||||
Shizmo | Okay passt, wenn ich jetzt aber alles so durchrechne und vergleiche, bin ich ewig dabei, wie finde ich das schneller raus? |
||||||||||||||
05.03.2016, 11:41 | Auf diesen Beitrag antworten » | ||||||||||||||
eulerscheZahl | Wenn du das nach Definition zeigen willst, musst du wohl in den sauren Apfel beißen. Letzendlich ist das aber eine Grenzwertberechnung: welche Funktion wächst im Unendlichen schneller. heißt, dass f schneller wächst als g, daher ist . Berechnest du den Grenzwert von g(x)/f(x), ist das Ergebnis 0, was heißt g wächst langsamer als f. Kriegst du eine echt positive Konstante, sind sie in der Notation äquivalent. |
||||||||||||||
05.03.2016, 11:46 | Auf diesen Beitrag antworten » | ||||||||||||||
Shizmo | Ok vielen Dank, werde das gleich mal durchprobieren. Hab mir grad gedacht ich hau alles in einen Plotter und schaus mir da an, ist aber gar nicht so leicht, die alle zu vergleichen Aber nochwas was ich nicht verstehe: (siehe Grafik) Dass x*log(x) schneller steigt als x macht für mich sinn, aber warum steigt x*log(log(x)) weniger schnell als x??? x*log(x) x x*log(log(x)) |
||||||||||||||
05.03.2016, 11:55 | Auf diesen Beitrag antworten » | ||||||||||||||
eulerscheZahl | Alles eine Frage der Betrachtungsweise Schau mal auf die Achsenbeschriftung. |
||||||||||||||
05.03.2016, 12:00 | Auf diesen Beitrag antworten » | ||||||||||||||
Shizmo | Haha Ja soweit habe ich nicht nach vorne geschaut |
||||||||||||||
05.03.2016, 13:46 | Auf diesen Beitrag antworten » | ||||||||||||||
Shizmo | Okay, also meine Sortierung würde dann so ausschauen: Und bei den letzten 2 habe ich eine Konstante () rausbekommen, also eine -Äquivalenz. Ich bin mir nur nicht ganz sicher, ist das gleiche, wie Punk4 bei der Aufgabe auf dem Bild? |
||||||||||||||
05.03.2016, 14:47 | Auf diesen Beitrag antworten » | ||||||||||||||
eulerscheZahl | Wir hatten uns doch schon darauf geeinigt, dass n langsamer wächst als n*log(n). Also muss es weiter nach oben (direkt nach sqrt(n)). Dann schreiben wir die anderen mal ein wenig um: Es gilt: (für n > 0) Und |
||||||||||||||
05.03.2016, 19:50 | Auf diesen Beitrag antworten » | ||||||||||||||
Shizmo |
Natürlich, da hab ich wohl was durcheinander gebracht.
Ahh, auf die Idee einfach mal Umzuformen bin ich nicht gekommen Vielen, vielen Dank. Aber noch eine Frage, aber was anderes, du kennst dich ja sicher auch sehr gut mit LaTeX aus, wenn ich:
Der Codeabschnitt schaut so aus:
|
||||||||||||||
05.03.2016, 20:56 | Auf diesen Beitrag antworten » | ||||||||||||||
eulerscheZahl | Sehr gut ist übertrieben. Aber bei der Bachelorarbeit hat es gute Dienste geleistet. In LaTeX gibt es 2 Modi für Formeln: abgesetzt und inline. Mit $$ schreibst du im inline Modus. Der ist darauf ausgelegt, nicht mehr Platz zu brauchen, als der Fließtext (ausgenommen Dinge wie underbrace). Wenn du mit \begin{align*}...\end{align*} oder \[...\] arbeitest, geht der limes über 2 Zeilen. Du kannst aber auch im inline Modus zweizeilig schreiben:
|
||||||||||||||
06.03.2016, 10:25 | Auf diesen Beitrag antworten » | ||||||||||||||
Shizmo | Perfekt, vielen, vielen Dank für deine Hilfe!!!!!! |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|