n log(n) - Barriere für Sortierfunktionen?
-
knivil schrieb:
5. belibige inputdaten bzw container
Kein Problem, wenn Punkt 4 nicht ist. Aber sortieren in n log n setzt random access container voraus.
Dem würde ich widersprechen: Merge sort funktioniert wunderbar mit einfach verketteten Listen und liegt trotzdem noch in O(n log n).
-
Jester schrieb:
Wenn Dir das alles so klar ist, dann frage ich mich, warum Du, obwohl hier sehr klar jeder beschrieben hatte unter welchen Bedingungen nlogn eine untere Schranke ist, ein prolliges "da hab ich mal ne wette gewonnen, es geht nämlich wohl in O(n)" reinwirfst. Wenn Unwissenheit als Grund wegfällt, fallen mir nicht mehr so viele netten Gründe ein.
wie ich schon sagte, ich wollte aufzeigen, dass die barriere nur bei speziellen vorraussetzungen gilt. 'wenn man eine sortierfunktion ist' kann man auch schneller oder langsammer sein.
Wenn Du einfach zusätzlich informieren willst, dann schreib doch Deine zusätzlichen Voraussetzungen dazu und widersprich nicht denen, die auch richtige Sachen gesagt haben. Unter den in obigen Postings genannten Bedingungen ist O(n log n) jedenfalls unbestreitbar optimal.
und diese bedingungen standen beim zittierten satz nicht da, deswegen hab ich das beispiel mit meinem lehrer genannt. alle lesen immer n*log(n) und erzaehlen unreflektiert weiter, dass es nur n*log(n) gibt als barriere fuer alle sortierfunktionen.
mit dem zittierten satz will man auch implizieren, dass es unmoeglich ist "schneller" zu sein als n*log(n) vergleiche und gleichzeitig, dass das das optimum ist. beides ist nicht allgemein gueltig.Es ist wahr wenn
-man nur diesen einen vergleichoperator hat
-nichts ueber die menge weiss
-keine weiteren anforderungen an die zu sortierende menge hatnochmal ganz deutlich: unter deinen bedingungen ist n*log(n) richtig. so "if you were a sort function, you'd never break the nlogn barrier" ist es nicht richtig.
-
rapso schrieb:
so "if you were a sort function, you'd never break the nlogn barrier" ist es nicht richtig.
Und den ersten Teil des Zitates hast du überlesen?
Forever comparing, never evaluating on any external scale.
-
rapso schrieb:
so "if you were a sort function, you'd never break the nlogn barrier" ist es nicht richtig.
stimmt, aber wenn Du das komplette Zitat mitnimmst schon: "forever comparing..."
-
knivil schrieb:
4. es sind keine zusatz allokationen erlaubt
Warum nicht?
warum was nicht? wieso das jemand nicht haben wollen wuerde? da gibt es unmengen von gruenden, z.b. das allokationen sehr viel mehr kosten koennen als das sortieren selbst und man dann lieber einen 'komplexeren' algorithmus haben will, der aber garantiert in-place ist. Oder man ist an einem kritischen bereich der nicht wegen speicher limitierungen fehlschlagen darf. oder einfach weil du feste speicher budgets hast und garnicht allokieren kannst.
5. belibige inputdaten bzw container
Kein Problem, wenn Punkt 4 nicht ist. Aber sortieren in n log n setzt random access container voraus.
jap, wenn du belibig allokieren kannst, kannst du auch listen an alles dranknallen und mit merge sort sortieren.
6. stabil
Meist nicht das Problem.
ja, "meist" reicht vielen irgendein sort aus, aus einer lib dem man einfach vertraut schon das richtige zu tun, da ist es einem oft auch egal, ob worst case bei O(n*n) liegt oder best case bei O(n) ist und wenn man die leute fragt was verwendet wird, sagen sie ohne nachzudenken "quicksort", obwohl das 'meist' nicht der fall ist.
Restriktionen sind ok, solange sie vernuenftig sind. Die hier angefuehrten sind nicht oder nur in Ausnahmefaellen vernuenftig.
ich weiss nicht anhand von was du glaubst die allgemeinfaelle so gut zu kennen, aber dennoch gibt es viele verschiedene faelle, entsprechend viele sortier algorithmen und deren komplexitaet reicht entsprechend weit auseinander und ist nicht mit n*log(n) als mass aller dinge als mutter aller grenzen zu setzen.
-
Tim schrieb:
rapso schrieb:
so "if you were a sort function, you'd never break the nlogn barrier" ist es nicht richtig.
Und den ersten Teil des Zitates hast du überlesen?
Forever comparing, never evaluating on any external scale.
nein, hab ich nicht ueberlesen, das war der grund weshalb mir der zweite satz so auffiel.
vielleicht intepretiere ich das falsch. sorry dann. aber es liest sich fuer mich nicht nach 'unter den bedingungen ist es so', sondern 'so funktioniert sortieren: nur vergleichen, kein weiteres wissen''sortieren kann nicht schneller als.. sein'. also eher nach einem suggestiv satz denn nach einer bedingung.aber wenn ihr das alle anders interpretiert, wird es wohl so gemein sein, das war mir vorher nicht bewust. sorry.
-
Christoph schrieb:
Dem würde ich widersprechen: Merge sort funktioniert wunderbar mit einfach verketteten Listen und liegt trotzdem noch in O(n log n).
Wie erhaelst du die Mitte einer Liste?
edit: Ja, ich hab 's ...
@rapso: Du vergleichst zwei Algorithmen, die einfach unterschiedliche Annahmen an die Daten machen. Das ist witzlos. Fuer eine allgemeine Sortierfunktion (auch von natuerlichen Zahlen, unbeschraenkt) ist n log n die untere Schranke. Und wenn die Anzahl der Vergleiche die Komplexitaet bestimmt, dann gibt es zumindestens fuer Zahlen eine Sortierfunktion ganz ohne Vergleiche.
-
rapso schrieb:
6. stabil
Meist nicht das Problem.
ja, "meist" reicht vielen irgendein sort aus, aus einer lib dem man einfach vertraut schon das richtige zu tun, da ist es einem oft auch egal, ob worst case bei O(n*n) liegt oder best case bei O(n) ist und wenn man die leute fragt was verwendet wird, sagen sie ohne nachzudenken "quicksort", obwohl das 'meist' nicht der fall ist.
Ich würde auch sagen, Stabilität ist sehr wichtig. Jedenfalls wenn die zu sortierenen Objekte noch andere Eigenschaften als das Sortierkriterium haben. Sonst gibt es böse Überraschungen. Reine Zahlenarrays kannst du gerne mit Qicksort sortieren.
-
knivil schrieb:
Christoph schrieb:
Dem würde ich widersprechen: Merge sort funktioniert wunderbar mit einfach verketteten Listen und liegt trotzdem noch in O(n log n).
Wie erhaelst du die Mitte einer Liste?
edit: Ja, ich hab 's ...
Und wie?
-
Du brauchst keine Mitte. Einfach die Liste durchgehen und abwechselnd auf zwei Listen verteilen. Dann haste zwei gleichlange Listen.
-
Zu Vergleichsbasiert, stabil, inplace und n log n. Wie wärs mit Heapsort auf einem Schlüssel, dann gleiche Schlüsselbereiche nochmal mit Heapsort nach zweiten Key sortieren. Könnte funktionieren. Muss nochmal nachdenken.