Deterministischer linearer Zeitalgorithmus zur Überprüfung, ob ein Array eine sortierte Version des anderen ist

Betrachten Sie das folgende Problem:

Eingabe: zwei Arrays $A$ und $B$ der Länge $n$ , wobei $B$ in sortierter Reihenfolge ist.

Frage: Sie $A$ und $B$ enthalten die gleichen Elemente (mit ihrer Vielfalt)?

Was ist der schnellste deterministische Algorithmus für dieses Problem?
Kann es schneller gelöst werden als sie zu sortieren? Kann dieses Problem in deterministischer linearer Zeit gelöst werden?

Sie haben Ihr Berechnungsmodell nicht angegeben, daher nehme ich das Vergleichsmodell an.

Betrachten Sie den Sonderfall, in dem das Array aus der Liste { 1 , 2 } × { 3 , 4 } × ⋯ × { 2 n - 1 , 2 n } genommen wird . In Worten ist das i- te Element entweder 2 i - 1 oder 2 i .$B$

$$\{1,2\} \times \{3,4\} \times \cdots \times \{2n-1,2n\}.$$ $i$$2i-1$$2i$

Ich behaupte, wenn der Algorithmus zu dem Schluss kommt, dass und B dieselben Elemente enthalten, hat der Algorithmus jedes Element in B mit seinem Gegenstück in A verglichen . Tatsächlich wird angenommen , dass der Algorithmus schließt daraus , dass A und B die gleichen Elemente enthalten, aber nie vergleicht das erste Element B zu seinem Gegenstück in A . Wenn wir das erste Element umschalten, würde der Algorithmus genauso vorgehen, auch wenn die Antwort unterschiedlich ist. Dies zeigt, dass der Algorithmus das erste Element (und jedes andere Element) mit seinem Gegenstück in A vergleichen muss .$A$$B$$B$$A$$A$$B$$B$$A$$A$

Dies bedeutet, dass, wenn und B dieselben Elemente enthalten, der Algorithmus nach Überprüfung die sortierte Reihenfolge von A kennt . Daher muss es mindestens n haben ! verschiedene Blätter, und so dauert es Zeit Ω ( n log n ) .$A$$B$$A$$n!$$\Omega(n\log n)$

Diese Antwort betrachtet ein anderes Berechnungsmodell: das Stückkosten-RAM-Modell. In diesem Modell haben Maschinenwörter die Größe , und Operationen an ihnen dauern O ( 1 ) . Der Einfachheit halber nehmen wir auch an, dass jedes Array-Element in ein Maschinenwort passt (und daher höchstens n 0 ( 1 ) beträgt ).$O(\log n)$$O(1)$$n^{O(1)}$

Wir werden einen linearen, zeitlich zufälligen Algorithmus mit einseitigem Fehler konstruieren (der Algorithmus könnte erklären, dass die beiden Arrays dieselben Elemente enthalten, auch wenn dies nicht der Fall ist), um das schwierigere Problem zu lösen, ob zwei Arrays und b 1 , … , b n enthalten die gleichen Elemente. (Wir brauchen keine Sortierung.) Unser Algorithmus wird mit einer Wahrscheinlichkeit von höchstens 1 / n einen Fehler machen .$a_1,\ldots,a_n$$b_1,\ldots,b_n$$1/n$

Die Idee ist , dass die folgende Identität gilt iff die Anordnungen dieselben Elemente enthalten: Das genaue Berechnen dieser Polynome wird zu viel Zeit in Anspruch nehmen. Stattdessen wählen wir eine zufällige Primzahl p und eine zufällige x 0 und testen, ob n ∏ i = 1 ( x 0 - a i ) ≡ n

$$\prod_{i=1}^n (x-a_i) = \prod_{i=1}^n (x-b_i).$$ $p$$x_0$ Wenn die Arrays gleich sind, besteht der Test immer. Konzentrieren wir uns also auf die Fälle, in denen die Arrays unterschiedlich sind. Insbesondere einige Koeffizient Π n i = 1 ( x - a i ) - Π n i = 1 ( x - b i ) nicht Null. Da a i , b i die Größe n ) = n O ( n ) hat , hat es höchstens O ( $$\prod_{i=1}^n (x_0-a_i) \equiv \prod_{i=1}^n (x_0-b_i) \pmod{p}.$$ $\prod_{i=1}^n (x-a_i) - \prod_{i=1}^n (x-b_i)$$a_i,b_i$ , hat dieser Koeffizient die Größe 2 n n O $n^{O(1)}$$2^n n^{O(n)} = n^{O(n)}$ Primfaktoren der Größe Ω ( n ) . Dies bedeutet, dass, wenn wir eine Menge von mindestens n 2 Primzahlen p mit einer Größe von mindestens n 2 (etwa)wählen, für eine zufällige Primzahl p dieser Menge mit einer Wahrscheinlichkeit von mindestens 1 - 1 / n gilt, dass $O(n)$$\Omega(n)$$n^2$$p$$n^2$$p$$1-1/n$ Ein zufälliges x 0 Modulo p wird dies mit einer Wahrscheinlichkeit von 1 - n / p ≥ 1 - 1 / n bezeugen(da ein Polynom vom Grad höchstens n höchstens n Wurzeln hat). $$\prod_{i=1}^n (x-a_i) - \prod_{i=1}^n (x-b_i) \not\equiv 0 \pmod{p}.$$ $x_0$$p$$1-n/p \geq 1-1/n$$n$$n$

Wenn wir also ein zufälliges einer Größe von ungefähr n 2 aus einer Menge von mindestens n 2 verschiedenen Primzahlen und ein zufälliges x 0- Modulo p auswählen , schlägt unser Test fehl, wenn die Arrays nicht dieselben Elemente enthalten Wahrscheinlichkeit 1 - O ( 1 / n ) . Das Ausführen des Tests benötigt die Zeit O ( n ), da p in eine konstante Anzahl von Maschinenwörtern passt.$p$$n^2$$n^2$$x_0$$p$$1-O(1/n)$$O(n)$$p$

Mit Polynom Primtests Zeit und da die Dichte der Primzahlen der Größe ungefähr ist Ω ( 1 / log n ) , können wir eine zufällige Primzahl wählen p in der Zeit ( log n ) O ( 1 ) . Die Wahl eines zufälligen x 0 modulo p kann auf verschiedene Arten implementiert werden und wird erleichtert, da wir in unserem Fall kein völlig gleichmäßiges zufälliges x 0 benötigen .$n^2$$\Omega(1/\log n)$$p$$(\log n)^{O(1)}$$x_0$$p$$x_0$

Zusammenfassend läuft unser Algorithmus in der Zeit , gibt immer JA aus, wenn die Arrays die gleichen Elemente enthalten, und gibt NEIN mit der Wahrscheinlichkeit 1 - O ( 1 / n ) aus, wenn die Arrays nicht die gleichen Elemente enthalten. Wir können die Fehlerwahrscheinlichkeit auf 1 - O verbessern ( $O(n)$$1-O(1/n)$für jede Konstante C / n C ).$1-O(1/n^C)$$C$

Ich werde einen anderen Algorithmus vorschlagen (oder zumindest ein Schema eines solchen Algorithmus)

$[min,max]$

1. $O(n)$minmax

2. Subtrahiere die minvon allen Werten von beiden Arrays (hier wird die Tatsache, dass ein Array bereits in sortierter Reihenfolge ist, nicht berücksichtigt, vermutlich kann dies verbessert werden)

3. $1$$c > 1$

4. max-min$O((max-min)n)$

man beachte, dass das obige Algorithmusschema in vielen praktischen Situationen (deterministisch) ziemlich schnell sein kann.

Das obige Algorithmusschema ist eine Variation eines linearen Zeitsortieralgorithmus, der "sich bewegende Massen " verwendet. Die physikalische Intuition hinter dem Sortieralgorithmus " Moving Masses " lautet:

Nehmen Sie an, dass der Wert jedes Elements tatsächlich dessen Massengröße darstellt, und stellen Sie sich vor, Sie ordnen alle Elemente in einer Linie an und wenden dieselbe Beschleunigungskraft an.

Dann bewegt sich jeder Gegenstand in Bezug auf seine Masse um eine Distanz, massiver weniger Distanz und umgekehrt. Zum Abrufen der sortierten Artikel sammeln Sie die Artikel einfach in umgekehrter Reihenfolge nach zurückgelegter Entfernung.

Dieser Algorithmus ist linear und deterministisch , es gibt jedoch eine Einschränkung dahingehend, dass der Betrag der anfänglichen Beschleunigungskraft und der zurückzulegenden Strecke (oder die Wartezeit) mit der Verteilung der Werte (dh den " Massen ") zusammenhängt$max-min$Faktor oben). Man kann auch versuchen, den Raum zu diskretisieren, in dem die Elemente in ein Gitter wandern, und einen konstanten Faktor für die Algorithmusgeschwindigkeit erhalten (und eine schnelle Sortierroutine verwenden, um verschiedene Elemente in derselben Zelle zu sortieren ).

In dieser Hinsicht ähnelt der obige Algorithmus numerisch basierten Sortieralgorithmen (z. B. Radix-Sortierung , Zähl-Sortierung ).

Man könnte meinen, dass dieser Algorithmus nicht viel bedeutet, aber er zeigt mindestens eines. Das " fundamentale " Sortieren beliebiger Zahlen auf physikalischer Ebene ist eine linear-zeitliche Operation in Bezug auf die Anzahl der Elemente.