Seite 2 von 2

Verfasst: 1. Jul 2007 23:25
von HolgerF
Du solltest das Proxmap-Verfahren und den damit verwendeten Sortierer mal kurz trennen. Proxmap ist also ausschließlich nur das Einsortieren einer Eingabemenge in eine bestimmte Anzahl an Buckets. Das ist immer ein O(n)-Aufwand, weil du für jedes Element den richtigen Bucket in konstanter Zeit findest und jedes Element auch nur einmal einsortierst. Wenn du hierbei natürlich schon auch die Buckets sortierst, indem du quasi das Einordnen schon mit Insertion Sort machst, dann ist das Einsortieren nicht mehr O(n).

Allerdings macht natürlich insgesamt das Vorsortieren ohne anschließendes exaktes Sortieren ungefähr keinen Sinn, deswegen sympathisiere ich auch ein wenig mit deiner Idee, die mir während der Implementation auch gekommen ist. Da man's sowieso machen muss, könnte man es auch gleich zusammen machen, es würde voraussichtlich vergleichsweise wenig bringen, aber nichtsdestotrotz. Aber was soll's :)

Verfasst: 2. Jul 2007 07:45
von Christoph B
Ich habs auch so gemacht und mal mit nem Kollegen verglichen der die Buckets erst am ende sortiert (genauer gesagt haben wir den unterschied zwischen Collection.sort() und eigener Sortierung verglichen - damit unabhängig von pc leistung) Die buckets also von anfang an sortiert zu halten ist sehr viel langsamer als sie erst zu sortieren wenn sie fertig sind, daher überleg ich auch noch zu revoken um das effizienter zu machen :/

allerdings gibt uns die Aufgabenstellung keine Laufzeitbeschränkung / bestimmten Sortier Algorithmus vor, von daher sollten sogar Slow- oder Bogosort erlaubt sein (könnte höchstens im Testsystem zu Timeouts führen ^^), vorausgesetzt man kann dem Tutor anständig erklären wieso man ausgerechnet den un den algo benutzt hat.

Verfasst: 2. Jul 2007 08:18
von giftnudel
citta hat geschrieben:
giftnudel hat geschrieben:Zur Komplexität: in jedem Schritt O(n) macht unser O(n) Proxmap sort zu O(n^2) => Aufgabenstellung verfehtl! => max 5 Punkte im Testat ... (zumindest bei mir)
Hmm...
Ja, es wäre O(n^2), wenn man denn annimmt, dass man alles in den gleichen Bucket einordnet, also quasi der worst case. Diesen Nachteil hat allerdings auch der Proxmapsort, bei dem man erst hinterher die Buckets mit Insertionsort sortiert.
Da hast du einen Denkfehler drin, denn das passiert nicht nur im Worst Case:

Denn du hast in einem Bucket mindestens mal n/26 bzw n/10 Einträge, da haben wir also ein Problem, wenn wir in jedem "n/26-ten" Schritt alle "n/26" Einträge überprüfen müssen. Also insgesamt untere Schranke n/26*n/26 = n^2/26^2 also O(n^2). Hintereinanderausführen von Proxmap und Heapsort:
O(n + n logn) also O(n logn), was wesentlich besser ist.

Das alles ohne Einschränkung auf ein Bucket mit n/26 Elementen, da wir den beliebig wählen können wenn wir ihn denn dann kennen. Und einen wird es sicher geben.

Verfasst: 2. Jul 2007 12:05
von hcdenton
Was ist, wenn mein Einfuegealgorithmus eine Laufzeit von log(n) pro Element hat?

Verfasst: 2. Jul 2007 12:09
von HolgerF
Wie willst du die denn erreichen? Binary Search für die richtige Einfügeposition? Dann müssen aber immer noch alle Elemente dahinter bewegt werden => wieder O(n).

Verfasst: 2. Jul 2007 12:15
von hcdenton
Wo muss was bewegt werden? Und Einfuegen hat im Tree eine konstante Laufzeit, aehnlich wie bei einer LinkedList... Kommt noch das Suchen (log(n)) und evtl. Rotieren (ebenfalls konstant) hinzu