wake-up-neo.net

Ist dort ein O(n) ganzzahliger Sortieralgorithmus?

Letzte Woche bin ich über dieses Papier gestolpert, wo die Autoren auf der zweiten Seite erwähnen:

Beachten Sie, dass dies eine lineare Laufzeit für ganzzahlige Flankengewichte ergibt.

Gleiches auf der dritten Seite:

Dies ergibt eine lineare Laufzeit für ganzzahlige Flankengewichte und O (m log n) für die vergleichsbasierte Sortierung.

Und auf der 8. Seite:

Insbesondere die Verwendung der schnellen Ganzzahlsortierung würde die GPA wahrscheinlich erheblich beschleunigen. 

Bedeutet das, dass es unter bestimmten Umständen für ganzzahlige Werte einen Sortieralgorithmus O(n) gibt? Oder ist das eine Spezialität der Graphentheorie?

PS:
Es könnte sein, dass die Referenz [3] hilfreich sein könnte, weil auf der ersten Seite gesagt wird:

Weitere Verbesserungen wurden für [..] Graphenklassen erzielt, z. B. ganze Kantengewichte [3], [...]

aber ich hatte keinen Zugang zu den wissenschaftlichen Zeitschriften.

38
Karussell

Ja, Radix Sortierung und Zählung Sortierung sind O(N). Es handelt sich NICHT um vergleichsbasierte Sortierungen, für die nachweislich die Ω(N log N)-Untergrenze gilt.

Um genau zu sein, ist radix sort O(kN), wobei k die Anzahl der Ziffern in den zu sortierenden Werten ist. Die Zählsortierung lautet O(N + k), wobei k der Bereich der zu sortierenden Zahlen ist.

Es gibt bestimmte Anwendungen, bei denen k so klein ist, dass sowohl die Radix-Sortierung als auch die Zählsortierung in der Praxis eine lineare Leistung zeigen.

53

Vergleichssorten müssen im Durchschnitt mindestens Ω (n log n) sein.

counting sort und radix sort linear mit der Eingangsgröße skalieren - da es sich nicht um Vergleichssortierungen handelt, nutzen sie die feste Struktur der Eingänge.

11
ephemient

Zählsortierung: http://en.wikipedia.org/wiki/Counting_sort Wenn Ihre Ganzzahlen relativ klein sind . Radix-Sortierung, wenn Sie größere Zahlen haben (dies ist im Allgemeinen eine Generalisierung der Zählsortierung oder eine Optimierung für größere Zahlen, wenn Sie so wollen): http://en.wikipedia.org/wiki/Radix_sort

Es gibt auch eine Bucket-Sortierung: http://en.wikipedia.org/wiki/Bucket_sort

4
IVlad

Obwohl dies nicht sehr praktisch ist (hauptsächlich wegen des großen Speicheraufwands), dachte ich, ich würde Abacus (Bead) Sort als einen anderen interessanten linearen Zeitsortieralgorithmus erwähnen.

2
Dolphin

Diese hardwarebasierten Sortieralgorithmen:

Ein vergleichsfreier Sortieralgorithmus
Sortieren von Binärzahlen in Hardware - Ein neuartiger Algorithmus und seine Implementierung

Laser Domino Sorting Algorithm - ein Gedankenexperiment von mir basierend auf Counting Sort mit der Absicht, O(n) Zeitkomplexität über Counting Sorts O(n + k) zu erreichen.

1
abcoep

Ein wenig mehr Detail hinzufügen - Praktisch der beste Sortieralgorithmus bis zum Datum ist nicht O(n), sondern 0 (n\sqrt {\ log\log n}).

Weitere Informationen zu diesem Algo finden Sie in der Arbeit: http://dl.acm.org/citation.cfm?id=652131

0
akuriako