Praktikum 8 getBucket()

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag 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 :)

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag 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.

Benutzeravatar
giftnudel
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 112
Registriert: 3. Mai 2005 11:26

Beitrag 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.

hcdenton
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 21. Dez 2006 17:15

Beitrag von hcdenton »

Was ist, wenn mein Einfuegealgorithmus eine Laufzeit von log(n) pro Element hat?
Bild

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag 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).

hcdenton
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 21. Dez 2006 17:15

Beitrag 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
Bild

Antworten

Zurück zu „Archiv“