[DSAL] Probleme bei der O-Notation

[paco89]

hi,

ich sitz grad an folgender aufgabe....

a) berechnen sie eine möglichst einfache funktion f (n) mit (n/2 + log (n²))³ = f(n) + O (n²).


ich weiß, dass ich jetzt das (n² + log (n²))³ auflösen soll....am ende kommt raus:

n³/8 + (n² log(n²))/(4 + n²log(n²))/2 + nlog²(n²) + (nlog(n²))/2 + log³(n²)

so und jetzt wird gesagt, dass die ersten 3 terme schneller wachsen als O(n²)....und die übrigen 3 würden nicht schneller wachsen als O(n²).

und ganz am ende steht dann (zusammengefasst):
(n³+ 6n²log(n²))/8 + O(n²)


so meine fragen wären jetzt diesbzgl.

a) woher weiß ich, was schneller wächst als O(n²) und was nicht?????? was ist der sinn der ganzen sache???? dass all die terme die langsamer wachsen in O(n²) reingepackt werden versteh ich, aber....das erkennen der langsameren und schnelleren terme fällt mir sehr schwer....gibt es dabei einen trick den man anwenden kann??

[Vion]

Der Trick ist einfach zu überlegen, was mathematisch bei welchem Term passiert. Schneller wachsen heißt ja einfach nur, dass es einen Wert gibt ab dem gilt, dass das Ergebnis von Term a immer größer ist als das Ergebnis von Term b. Jetzt guck dir jeden Term an und überleg was da gilt. Term b ist bei dir also einfach n^2. Was passiert also bei den anderen Termen? Wann sind m passiert:

PS: Ist die Klammersetzung richtig?

[paco89]

ja, die klammern sind alle richtig. es zeigt, dass der bruch für den kompletten term gilt....

[AGo]

Diese Aufgabe stammt aus einer Tutorenübung, und hätte eigentlich in deinem Tutorium (ausführlich) vorgerechnet werden sollen. Merke: Geht zu den Tutorien! Falls ihr in eurem Tutorium etwas nicht versteht. fragt sofort euren Tut.
Der ist genau dafür da (und wird dafür bezahlt)

Die Musterlösung vom Lehrstuhl zu dieser Aufgabe ist etwas knapp. Ich habe mal meine Version eingescannt die ich in meinem Tut vorgerechnet habe.
Das ist mathematisch nicht wirklich sauber aufgeschrieben (war halt nur für meinen "internen" Gebrauch gedacht), aber es zeigt alle nötigen Teilschritte um die Lösung (so hoffe ich) nachvollziehen zu können.

Allgemein zu dem Thema O-Notation bzw wie man diese letzte Abschätzung mit den log(n)s macht siehe auch den anderen Thread

[zed06]

Den letzten Teil der Lösung versteh ich leider nicht. Warum ist "6n * log(n) * log(n) + 8 * log(n) *log(n) * log(n)" =O(n^2) ?

[Max G]

Man kann sich überlegen, dass log(n)*log(n)=O(n) ist. (Grenzwert von log(n)*log(n)/n existiert )

Also:
8*log(n)²*log(n)=O(log(n))*n=O(n*log(n))=O(n²) (er letzte Schritt gilt wegen log(n)=O(n)
6*n*log(n)²=6n*O(n)=O(n²)

Und zwei Funktionen, die O(n²) sind, sind natürlich auch summiert O(n²).
Allgemein suchst du dir die am schnellsten wachsende Funktion von den x Summanden raus, alle anderen Summanden sind dann O(Funktion), dann hast du x*O(Funktion), was wegen x konstant gleich O(Funktion) ist.

[cracki]

"6n * log(n) * log(n) + 8 * log(n) * log(n) * log(n) = O(n^2)"

log(n)^3 / n geht auch noch gegen 0 (also waechst weniger als n), also kann man sagen log(n)^3 ist auch noch in O(n).

nun waere das O(6n) * O(n) + O(8) * O(n), also O(6*n*n) + O(8*n), also O(n^2) + O(n), also O(n^2)

so passt das gut. das sind aber alles abschaetzungen, also der eigentliche ausdruck koennte noch enger begrenzt werden, aber dann wird der O(,,,) ausdruck nur komplizierter.