Seite 1 von 2

Offtopic ?? Sortieren in O(log n)

Verfasst: 23. Apr 2008 01:56
von oren78
Bitte verzeiht falls ich hier fehl am platz bin, was dieses posting angeht, aber ich wüsste nicht wo man das genau
zuordnen sollte...

meine frage lautet wie folgt: Wer kann mir beweisen das es definitiv KEIN sortieralgorithmus gibt der in O(log (n)) liegt
vollkommen egal ob average, best oder worstcase :-) ??? und bitte keine scherzantworten wie: "einfach Boggosort ausprobieren" :-)
ich weiß ebenfalls das für vergleichsbasierte algo's die untere schranke bei O(nlog(n)) liegt, daher kann man diese algorithmenklasse
auch schon mal vergessen...

ich habe etliche modifizierungen von quicksort gesehen wie etwa das berühmte introsort, jedoch liegt auch hier im average/
bestcase ein O(nlog(n)) vor :-(

ich habe gehört das es von Radixsort verschiedene modifizierungen existieren sollen, die schon mal immerhin in O(n*0,5) sortieren können,
leider konnte ich hierzu auch keine sehr brauchbaren infos finden...stimmt das den überhaupt tatsächlich??

es ist schon frustrierend, ich streife schon seit langen im netz auf der suche nach ansätze das dies DOCH irgendwie möglich ist...
ich habe auch ein speziellen algorithmus gefunden: http://www.springerlink.com/content/501 ... lltext.pdf,
aber er schleppt vor dem O(log (n)) eine äußert gigantische konstante sodass dieser algo. absolut unbrauchbar ist (zumindest in der praxis...)

effiziente sortieralgorithmen intressieren mich seit eh und je und ich wollte (in knapp zwei semester) meine bachelorarbeit
darüber schreiben...deswegen die fragerei :-)

bin sehr dankbar für jede antwort, die sich mit dem thema beschäftigt ;-)

Re: Offtopic ?? Sortieren in O(log n)

Verfasst: 23. Apr 2008 07:10
von taufrisch
oren78 hat geschrieben:ich habe auch ein speziellen algorithmus gefunden: http://www.springerlink.com/content/501 ... lltext.pdf, ...
M. Ajtai, J. Komlós & E. Szemerédi hat geschrieben:We give a sorting network with cn log n comparisons. The algorithm can be performed in c log n parallel steps as well, ...
:mrgreen:

Viel Spaß bei der Bachelorarbeit. :wink:

Re: Offtopic ?? Sortieren in O(log n)

Verfasst: 23. Apr 2008 07:24
von mehlvogel

Re: Offtopic ?? Sortieren in O(log n)

Verfasst: 23. Apr 2008 08:21
von SmilingJ
naja.. sollte eigentlich recht einfach über argumentation sein:

um was zu sortieren solltest du wenigstens jedes element einmal anfassen, was O(n) wäre. O(log n) ist definitif kleiner O(n) und sollte schon allein aus dem im letzten satz genannten grund nicht funktionieren.

(edit)

btw.
die schon mal immerhin in O(n*0,5) sortieren
konstante faktoren werden afaik rausgezogen, wobei du dann bei O(n) wärest ...

Re: Offtopic ?? Sortieren in O(log n)

Verfasst: 23. Apr 2008 08:51
von Tillmann
oren78 hat geschrieben:Wer kann mir beweisen das es definitiv KEIN sortieralgorithmus gibt der in O(log (n)) liegt
Ich würde so argumentieren: Ein Sortieralgorithmus muß die gesamte Eingabe verarbeiten und benötigt dafür mindestens einen Schritt pro Eingabewert, insgesamt also mindestens n Schritte. Daher kann kein Sortieralgorithmus besser als O(n) sein.

Im Falle des sorting networks ist es vielleicht sinnvoller, die Größe des Netzwerks zu betrachten statt der Anzahl der aufeinanderfolgenden Schritte.

Re: Offtopic ?? Sortieren in O(log n)

Verfasst: 23. Apr 2008 09:22
von bender
http://www-i1.informatik.rwth-aachen.de ... algo12.php

das dürfte das sein, was O(log n) braucht.

Auch in dem Buch Algorithmen - Eine Einführung (2. Auflage) ist diese Sortierung auf Seite 716 aufgeführt.

Programmieren dürfte nicht gehen. Denn dies ist ja eine reine Schlatung, wo die Komperatoren jede Leitung gleichzeitig überprüfen.

Damit habt ihr schon recht, dass man jedes Element einmal anfassen muss. Hier geschieht es nur Parallel, und man braucht nur log n schritte um die Eingabe zu sortieren.

Re: Offtopic ?? Sortieren in O(log n)

Verfasst: 23. Apr 2008 20:41
von Tobias
bender hat geschrieben:http://www-i1.informatik.rwth-aachen.de ... algo12.php

das dürfte das sein, was O(log n) braucht.
O((log n)^2)
bender hat geschrieben: Programmieren dürfte nicht gehen. Denn dies ist ja eine reine Schlatung, wo die Komperatoren jede Leitung gleichzeitig überprüfen.
Das würde ich so nicht sagen. Wir haben
  • massivparallele Rechenmodelle (z.B. GCA),
  • parallele Rechnerarchitekturen, Koprozessoren und Befehlssätze (z.B. CUDA, MMX, SSE, Core2 Duo/Quad, FPGAs) und
  • datenparallele Programmiersprachen (z.B. ZPL, OpenMP).
Sicherlich schwankt der tatsächlich erreichte Grad der Parallelisierung abhängig von der Hardware, aber ansonsten ist bitonisches Sortieren durchaus in Software implementierbar.
(IMHO steht ein Paradigmenwechsel vor der Tür: Weil sich auch die Taktraten nicht beliebig steigern lassen, wird Parallelisierung immer wichtiger – auch in heimischen PCs.)
bender hat geschrieben:Damit habt ihr schon recht, dass man jedes Element einmal anfassen muss. Hier geschieht es nur Parallel, und man braucht nur log n schritte um die Eingabe zu sortieren.
Das ist der Vorteil parallelen Algorithmen: Die Speicherplätze für die Elemente braucht man so oder so; wenn die Berechnung auf viele Speicherplätze verteilt werden kann, sinkt der zeitliche Aufwand.
Ein anderes Beispiel dafür ist der Floyd-Warshall-Algorithmus: Sequentiell kann man den in O(n^3) Operationen erledigen; auf einem GCA mit O(n^2) Speicherplätzen reichen O(n) Iterationen. Insgesamt bleibt's aber bei O(n^3) Operationen.

Re: Offtopic ?? Sortieren in O(log n)

Verfasst: 23. Apr 2008 22:47
von oren78
liebe leute,

vielen dank für die teilweise sehr informativen links...ich seh schon, ich hab mir da was vorgenommen :-)
naja..zum glück ist's bis zur bachelorarbeit noch 'ne weile...bis dahin kann man noch viele infos sammeln
die unter umständen dazu beitragen dieses msyterium aufzudecken...

also nochmals danke....und liebe grüße :-)

Re: Offtopic ?? Sortieren in O(log n)

Verfasst: 25. Apr 2008 11:34
von Prof. Karsten Weihe
oren78 hat geschrieben: meine frage lautet wie folgt: Wer kann mir beweisen das es definitiv KEIN sortieralgorithmus gibt der in O(log (n)) liegt
Das ist einfach. Informell gesprochen: Sie müssen ja jedes zu sortierende Element mindestens einmal anfassen, um es richtig einzuordnen. Das allein ist schon Omega(n).

Oder meinten Sie: "nicht in O(n)"?

Gruß,

KW

Re: Offtopic ?? Sortieren in O(log n)

Verfasst: 25. Apr 2008 12:13
von oren78
Ohhhh....sogar der Dekan antwortet mir höchst persönlich :-)
Prof. Karsten Weihe hat geschrieben:Oder meinten Sie: "nicht in O(n)"?
nee, also ich meinte schon wirklich O(log (n)) den Algorithmen die schon in O(n) sortieren gibt es ja mittlerweile
wie sand am meer...(Proxmap, Radix, etc...)

Das O(n), bzw. Omega(n) jedoch nicht die untere Schranke ist, sieht man eigentlich schon an den Sortier Netzwerke Algorithmen,
die in best / average case auf O(log (n)) kommen (jedoch mit der gigantischen Konstante davor), deswegen intressiert mich dieses
Thema gerade so sehr ;-)


liebe Grüsse und ein schönes Wochenende euch allen :-)

Re: Offtopic ?? Sortieren in O(log n)

Verfasst: 25. Apr 2008 12:27
von Prof. Karsten Weihe
oren78 hat geschrieben:Ohhhh....sogar der Dekan antwortet mir höchst persönlich :-)
Nein, der moderator dieses Subforums. :wink:

oren78 hat geschrieben: Das O(n), bzw. Omega(n) jedoch nicht die untere Schranke ist, sieht man eigentlich schon an den Sortier Netzwerke Algorithmen
Aha, jetzt kommen wir der Sache schon näher: Sie betrachten also gar nicht unbedingt das Standardmaschinenmodell wie z.B. beim Thema Sortieren in GdI II, sondern erlauben auch parallele Modelle wie bspw. Sortiernetzwerke.

Vielleicht sollten Sie etwas genauer eingrenzen, welche Maschinenmodelle Sie betrachten wollen. Rein aus dem Bauch heraus würde ich z.B. vermuten, dass es für Ihre Frage einen Unterschied macht, ob Sie Quantencomputer mitbetrachten oder nicht.

Gruß,

KW

Re: Offtopic ?? Sortieren in O(log n)

Verfasst: 25. Apr 2008 13:35
von oren78
Prof. Karsten Weihe hat geschrieben:Vielleicht sollten Sie etwas genauer eingrenzen, welche Maschinenmodelle Sie betrachten wollen. Rein aus dem Bauch heraus würde ich z.B. vermuten, dass es für Ihre Frage einen Unterschied macht, ob Sie Quantencomputer mitbetrachten oder nicht.
Naja "Quantencomputer" ist doch etwas zu hoch gepokert ;-)

Also wie ich das bis dato verstanden habe, sind Sortiernetzwerk-Algo's nur auf Parallelrechner anwendbar, also Maschinen
die Hardwarekomponenten ausnutzen um effizient sortieren zu können, was ja schon die erste Einschränkung ist, ich habe
gedacht das eine herkömmliche Maschine, die alleine nur auf Softwarebasis dazu in der Lage wäre in O(log(n)) zu sortieren
zu können, aber dafür gibt es eben offensichtlich noch nichts :-(

Ich hatte vor einiger Zeit gehört das es unter Umständen möglich wäre eine spezielle Datenstruktur
zu entwickeln mit der es möglich wäre Elemente eben nicht "einzeln" anzufassen sondern häppchenweise
zu behandeln um darauf dann (z.B.) einen Sortier-Algo anzuwenden, wobei ich mich allerdings selbst frage wie das
wirklich möglich sein soll

Aber, naja, jedenfalls wäre das schon mal ein minimaler Ansatz...

Re: Offtopic ?? Sortieren in O(log n)

Verfasst: 25. Apr 2008 13:37
von mantra
Die Hoffnung stirbt zuletzt.

Re: Offtopic ?? Sortieren in O(log n)

Verfasst: 25. Apr 2008 13:51
von Prof. Karsten Weihe
oren78 hat geschrieben: Also wie ich das bis dato verstanden habe, sind Sortiernetzwerk-Algo's nur auf Parallelrechner anwendbar
es ist sogar noch etwas anders: Sortiernetzwerke sind theoretische Maschinenmeodelle, bei denen man davon ausgeht, dass man (a) unendlich viele Prozessoren zur verfügung hat (von denen man dann O(logn ) braucht) und (b) dürfen die Zahlen beliebig lang werden ohne die Größe eines Maschinenwortes zu sprengen.

Eine Aussage, dass man in Sortiernetzwerken mit O(log n) auskommt, ist daher erst einmal eine rein theoretische Aussage. Sie ist aber praktisch korrekt, solange die tatsächliche (natürlich endliche) Anzahl der Prozessoren und Größe eines Maschinenwortes nicht überschritten werden.

oren78 hat geschrieben: die Hardwarekomponenten ausnutzen um effizient sortieren zu können, was ja schon die erste Einschränkung ist, ich habe
gedacht das eine herkömmliche Maschine, die alleine nur auf Softwarebasis dazu in der Lage wäre in O(log(n)) zu sortieren
zu können, aber dafür gibt es eben offensichtlich noch nichts :-(
Sie brauchen irgendeine Art von Parallelverarbeitung, um mein Argument auszuhebeln, dass das Anfassen jedes einzelnen Elements schon Omega(n) Zeit kostet. Und das müsste schon so eine potentiell unendliche Maschine sein, denn sowie Sie eine feste Zahl K von Prozessoren haben, wird der Aufwand nur von Omega(n) auf Omega(n/k)=Omega(n) reduziert, es ändert sich also in der Praxis nichts.

Gruß,

KW

Re: Offtopic ?? Sortieren in O(log n)

Verfasst: 25. Apr 2008 13:52
von Arki
Na da haben wir doch einen Anwärter für den Turing Award... :)

Ich wünsch dir viel Erfolg!