Not logged in. · Lost password · Register

peck
Member since Jul 2010
16 posts
Subject: 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?
joe
Member since Jul 2010
14 posts
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.
tsch.aei
Member since Jul 2010
57 posts
Quote by joe:
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.
Airhardt
FAU-Mann
Member since Oct 2005
3262 posts
In reply to post #1
Quote by peck:
Aufgabe 1a)

kann mir mal jemand die ersten 2 erklären? Eigentlich hängt da die Laufzeit doch nicht von n ab oder?
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. :-)

Quote by peck:
c)
Meine antwort zu c:

laut O-Kalkül ist OPaks besser, für kleine n ist allerdings OPbitonic schneller.

stimmt das so?
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.
This post was edited on 2010-08-04, 11:59 by Airhardt.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen