Ist eine ganzzahlige Sortierung in O (n) im transdichotomen Modell möglich?

Meines Wissens gibt es keinen Worst-Case-Algorithmus, der das folgende Problem löst: $O(n)$

Finden Sie bei einer Folge der Länge die aus endlichen ganzen Zahlen besteht, die Permutation, bei der jedes Element kleiner oder gleich seinem Nachfolger ist. $n$

Aber gibt es einen Beweis dafür, dass es im transdichotomen Rechenmodell nicht existiert ?

Beachten Sie, dass ich den Bereich der Ganzzahlen nicht einschränke. Ich beschränke die Lösungen auch nicht auf Vergleichssorten.

complexity-theory sorting computation-models lower-bounds orlp
quelle

Soweit ich weiß, könnte es einen -Zeitalgorithmus für SAT geben! Die Antwort lautet also nein.

O (n)

$O(n)$

Lembik

AFAIK, das ist immer noch ein offenes Problem.

Juho

Ich weiß nicht, ob es eine aussagekräftige Antwort geben kann, bis Sie angeben, welches Berechnungsmodell Sie verwenden, da Sie Ihren Computer nicht auf Vergleiche und Swaps beschränken. Mit nur RAM- und Zwei-Zahlen-Vergleichen ergibt ein Argument aus der Entropie eine Zeitbindung von , selbst für transdichotome Computer. Wenn das Sortieren anstelle von Swaps und Vergleichen eine elementare Operation ist, kann es trivialerweise in . Wenn das Einfügen einer Ganzzahl an der richtigen Stelle eine elementare Operation ist, . Hatten Sie ein bestimmtes, über den Vergleich hinausgehendes Swap-Modell im Sinn?

Ω (n \cdot l o g (n))

$\Omega(n\cdot log(n))$

Θ (1)

$\Theta(1)$

Θ (n)

$\Theta(n)$

Lieuwe Vinkhuijzen

@LieuweVinkhuijzen Meine Frage spezifiziert das transdichotome Rechenmodell. Im Klartext: Ein Berechnungsmodell, bei dem die Wortgröße der Maschine groß genug ist, um eine beliebige Ganzzahl des Problems aufzunehmen. Der Vergleich zweier beliebiger Ganzzahlen ist also O (1), aber auch das Addieren, Multiplizieren usw. In diesem Berechnungsmodell wurde die entropische Grenze bereits überschritten, siehe Han, Yijie (2004), "Deterministische Sortierung in O (n log log n) Zeit und linearem Raum" .

Orlp

@orlp Ich verstehe; Wenn Sie die Struktur der ganzen Zahlen nutzen, können Sie die entropische Grenze überschreiten. Ich wusste nichts über das Sortieren von ganzen Zahlen. Ich werde mich sicher über dieses Thema informieren!

Lieuwe Vinkhuijzen

Antworten:

Ganzzahlen können in -Zeit mit zusätzlichem Leerzeichen stabil sortiert werden. $O(n)$ $O(1)$ Genauer gesagt, wenn Sie ganze Zahlen im Bereich , kann die in O (n) Zeit sortiert werden. $n$ $[1, n^c]$

Dies wurde erst vor ein paar Jahren von einem Team gezeigt, zu dem auch der verstorbene Mihai Pătrașcu gehörte (was niemanden überraschen sollte, der mit seiner Arbeit vertraut ist). Es ist ein bemerkenswertes Ergebnis, von dem ich überrascht bin, dass mehr Menschen nichts wissen, weil es bedeutet, dass das Problem des Sortierens von ganzen Zahlen (theoretisch) gelöst ist.

Es gibt einen praktischen Algorithmus (siehe oben), wenn Sie Schlüssel ändern dürfen. Grundsätzlich können Sie sortierte Ganzzahlen stärker komprimieren als unsortierte Ganzzahlen, und der zusätzliche Speicherplatz, den Sie gewinnen, entspricht genau dem zusätzlichen Speicher, der für die Radix-Sortierung benötigt wird. Sie geben auch einen unpraktischen Algorithmus an, der schreibgeschützte Schlüssel unterstützt.

Pseudonym
quelle

Nach dem, was ich aus der Zusammenfassung verstehen kann, ist dies nicht allgemein - es können nur Wörter bis zu einer Größe von in sortiert werden . In meiner Frage werden ausdrücklich unbegrenzte ganze Zahlen erwähnt.

\log n

$\log n$

O (n)

$O(n)$

Orlp

@orlp Der dritte Algorithmus in diesem Artikel befasst sich mit Ganzzahlen mit unbegrenzter Länge.

Pseudonym

Vielleicht verstehe ich es falsch, aber ich kann nur eine Beschreibung einer Methode sehen, mit der die Speichernutzung unbegrenzter ganzzahliger Sortieralgorithmen reduziert werden kann. Zitat aus der Zusammenfassung (Hervorhebung von mir): "Eine weitere interessante Frage ist der Fall von willkürlichem . Hier präsentieren wir eine Black-Box-Transformation von einem beliebigen RAM-Sortieralgorithmus zu einem Sortieralgorithmus, der nur O (1) zusätzlichen Speicherplatz verwendet und denselben hat Laufzeit . " $c$

Orlp

Verzeihen Sie mir, aber im aktuellen Zustand beantwortet diese Antwort die Frage überhaupt nicht . Ich habe ausdrücklich erwähnt, dass die ganzen Zahlen nicht begrenzt sind . Diese Antwort löst ein ganz anderes Problem.

Orlp

Der letzte Punkt ist jetzt nicht mehr in einer kleinen Schrift :)

orlp

-1

Für Ganzzahlen können Sie die Radix-Sortierung verwenden . Es erstellt Buckets und sortiert dann eine Liste von Zahlen in wobei eine Obergrenze für die Größe in Bits einer beliebigen Ganzzahl und die Anzahl der zu sortierenden Elemente ist. $O(bn)$ $b$ $n$

Wenn es keine Obergrenze für die Größe Ihrer Ganzzahlen gibt, gibt es meines Erachtens keinen bekannten linearen Zeitsortieralgorithmus.

RFC 2549
quelle

Herzlich willkommen! Was Sie sagen, ist völlig wahr, aber ich glaube nicht, dass es die Frage beantwortet. In der Frage wird speziell nach einem Beweis gefragt, dass der erforderliche Algorithmus in einem bestimmten Berechnungsmodell nicht vorhanden ist. Die bloße Aussage, dass kein solcher Algorithmus bekannt ist, beweist nicht, dass keiner existiert.

David Richerby

Da b eine Konstante in unserem Problem ist, betrachte ich diesen Algorithmus als in o (n)

RFC 2549

b

$b$

n

$n$

O (n)

$O(n)$

o (n)

$o(n)$

Ja, definitiv ein Tippfehler;) In seiner Frage wird eine Zahl, die in ein Wort der Länge b passt, zu einer Konstanten.

RFC 2549

Das macht die Wortlänge nicht zu einer Konstanten. (Sonst gäbe es keinen Grund, ausdrücklich davon ausgehen „ dass Operationen auf einzelne Wörter nehmen konstante Zeit pro Betrieb“.