Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Folie 13 Seite 30
f, g Funktionen
O(f)·O(g) = O(f·g)
O(f·g) = f·O(g)
O(O(f)) = O(f) aber natürlich nicht: O(f) = f
Müsste es nicht heißen:
O(f·g) = O(f)·O(g)
weil: O(f) ist nicht f ?
Macht denn das im Endeffekt überhaupt einen Unterschied?
Ob ich jetzt:
nO(n)
oder
O(nn)
nehme, es kommt doch immer O(n^2) raus
Es geht um 2 Funktionen, die können n, n^2 etc sein.
Demnach kann es je nachdem ob f oder g n oder n^2 sind zB O(n) oder O(n^2) heißen, was doch nicht sein kann, oder?
Da bin ich auch schon drüber gestolpert, kann mir aber bisher auch nicht so recht einen Reim drauf machen, was das bedeuten soll.
Das O(f) ≠ f ist gilt nur bei der Regel: O(O(f)) = O(f). Meiner Ansicht nach ist das so weil man ja das “=” immer als ein “element von” lesen muss und somit kann man nicht so einfach die Rechenregeln die man von mathematischen Gleichungen her kennt auf solche “Gleichungen” anwenden. Sprich das obige bedeutet eigentlich: O(O(f)) ist element der Menge O(f) und würde man jetzt folgern das O(f) = f ist so würde ja dastehen O(f) ist element von f. Aber f ist keine Menge und die Rückrichtung ist ja bei diesem “=” nicht erlaubt. Also nicht zu sehr verwirren lassen.
@peda:
Das kann natürlich sein, aber es ist schon ein Witz, dass erst darauf hingewiesen wird, dass man auf gar keinen Fall “=” schreiben soll, weil es zu Fehlern in der Interpretation führen kann und dann so was …
Demnach ist O(f*g) = O(f)O(g) = fO(g) ABER O(f) ∈ f ist FALSCH.
Ich gehe im Moment nach wie vor von einem Tippfehler aus.