O-Notation in der Mathematik?
Hallo, ich hab die O-Notation schon so mehr oder weniger verstanden, also dass es um den Zeit/Platzverbrauch von Algorithmen geht und bei O(n^3) der Zeit/Platzverbrauch immer hoch drei dem Eingegebenen entspricht.
Was ich aber nicht verstehe, wie man das bei mathematischen Ausdrücken zeigen soll. Z.B.:
Was ich mir vorstellen könnte wäre, dass n die Eingabe entspricht und der Funktionswert der dann rauskommt gleich der Eingabe hoch vier entsprechen muss (ist hier ja aber nicht der Fall).
1 Antwort
also dass es um den Zeit/Platzverbrauch von Algorithmen geht und bei O(n^3) der Zeit/Platzverbrauch immer hoch drei dem Eingegebenen entspricht.
Nein, wenn die Laufzeit in O(n^3) ist, bedeutet es, dass die Laufzeit höchstens genauso schnell wie n^3 wächst, wenn n gegen unendlich geht. Es bedeutet nicht, dass die Laufzeit exakt n^3 ist.
Mit der O Notation sagst du nur aus, wie schnell etwas wächst, wenn n gegen unendlich geht.
Schau dir nochmal an, wie die Landau notation definiert ist.
Zum Beispiel hier:
https://de.m.wikipedia.org/wiki/Landau-Symbole
f ist in O(g) wenn es ein C>0 und ein N>0 gibt, sodass f(n)<=C*g(n) für alle n größer als n gilt.
Du musst hier also zeigen, dass es ein C>0 und ein N>0 gibt, sodass 5n^4-3n^2+5n <= Cn^4 für alle n>N gilt.
Nicht ganz, die Aussage wäre wahr, wenn es ab einem Bestimmten N gilt, es muss also nicht für alle n gelten.
Du kannst hier aber eine Abschätzung finden, die schon ab N=1 gilt.
Würde also heißen in meinem Fall wäre die Aufgabe wahr wenn die Funktion kleiner gleich ist als n^4 multipliziert mit einem beliebigen Faktor?