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.
O-Kalkül 27.03.2006
Aufgabe 1a)
kann mir mal jemand die ersten 2 erklären? Eigentlich hängt da die Laufzeit doch nicht von n ab oder?
bei der dritten hab ich O(n) ist das richtig?
c)
Meine antwort zu c:
laut O-Kalkül ist OPaks besser, für kleine n ist allerdings OPbitonic schneller.
stimmt das so?
1a) 2(n − 1)(n + 1)/n + log(n) = 2(n² - 1)/n + log(n) = 2n - 2/n + log(n) => O(n)
log(n²) = 2log(n) => O(log(n))
Summe von i = 1 bis n = 1 + 2 + 3 + … + n = 1/2 n (n+1) = 1/2 (n² + n) => O(n²)
c)
Da würde ich auch gerne wissen was da stimmt. Meine Überlegung war:
O-Kalkül von opAKS = O(n log(n))
O-Kalkül von opBitonic = O(n (log(n))²)
Ich würde dann auch opBitonics bevorziehen, weil (log(n))² kleiner als log(n) ist.
Das stimmt aber nur für ganz kleine n (0<n<1).
Ich würde auch opBitonic nehmen, einfach weil die 1000 vor dem n bei opAKS bis zu einem gewissen n größere Auswirkungen hat als der quadratische Logarithmus, der ja doch ziemlich gemächlich steigt.
Ich glaube, da gibt es ein fundamentales Missverständnis. Kann es sein, dass du denkst, dass man die Komplexität einer Implementierung angeben soll, die jeweils die gegebene mathematische Formel auswertet?
Bei dieser Aufgabe geht es nur darum, für die gegebenen Formeln die Komplexitätsklasse anzugeben - also einfach nur stur umformen wie von joe gezeigt und dann durch scharfes Hinschauen zum Ergebnis kommen. 
Laut O-Kalkül ist für große n ganz klar AKS Sort besser, weil O(log n) < O((log n)²). Der riesige konstante Vorfaktor macht es aber für die Praxis untauglich.
Wenn ich mich nicht verrechnet habe, liegt der Break-Even-Point [1] bei n = 2^2000. Und das ist eine gigantisch riesig megamäßige Zahl, die um Lichtjahre jenseits jeder Eingabegröße liegt, mit der man den Algorithmus jemals füttern wird.
Folglich ist Bitonic Merge Sort in der Praxis bei allen Eingaben effizienter.
[1] Das ist der Punkt, ab dem AKS Sort besser ist als Bitonic Merge Sort. Berechnung: Einfach die beiden Terme gleichsetzen und nach n auflösen.