Algorithmus, um den kleinsten Unterschied im Array zu finden

Wir wollen einen Algorithmus, der bei einem Array mit der Länge von ganzen Zahlen die minimale Differenz zwischen zwei ganzen Zahlen im Array findet. $n$

Ein solcher Algorithmus besteht darin, das Array zu sortieren und benachbarte Zahlenpaare zu überprüfen. Dies dauert einige Zeit . $O(n\log n)$

Gibt es einen schnelleren Weg, z. B. einen -Algorithmus? $O(n)$

algorithms arrays boaten
quelle

ist nicht schneller als

O (n)

$O(n)$

O (n \log n)

$O(n\log n)$

David Merinos

Antworten:

Dies hängt von Ihrem Berechnungsmodell ab. Wenn Sie nur Arithmetik und Vergleiche zulassen (das algebraische Entscheidungsbaummodell), gibt es ein Untergrenze von für dieElementunterscheidbarkeit, das Problem der Entscheidung, ob alle Elemente verschieden sind. Ihr Problem ist natürlich noch schwieriger, daher gilt die gleiche Untergrenze. $\Omega(n\log n)$

(Es gibt einige Kleingedruckte: Die Untergrenze gilt nur, wenn der Grad der zu vergleichenden Polynome begrenzt ist. Wenn Sie nur verschiedene Unterschiede , können Sie loslegen. Die algebraische Entscheidung Mit dem Baummodell können Sie auch allgemeinere Polynome in den Eingaben vergleichen, sofern sie einen begrenzten Grad haben.) $x_i - x_j$

Es gibt andere Modelle, die möglicherweise eine bessere Leistung erzielen. In einigen Modellen können Sie beispielsweise Ganzzahlen in sortieren . Aber ich kann mir vorstellen, dass Sie die Art von Tricks, die in solchen Algorithmen verwendet werden, nicht zulassen wollen. $o(n\log n)$

Yuval Filmus
quelle

Vielen Dank. Was meinst du mit "Vergleich verschiedener Unterschiede

"? Da es

solche Paare gibt, würde das nicht

dauern ?

x_{i} - x_{j}

$x_i-x_j$

Θ (n^{2})

$\Theta(n^2)$

Ω (n^{2})

$\Omega(n^2)$

Boot

Nicht unbedingt. Vergleichsbasierte Algorithmen dürfen nur Elementpaare vergleichen. Hier erlaube ich Ihnen, kompliziertere Abfragen wie

oder sogar

. Wir wissen, dass es eine Lösung gibt, die

-Vergleiche vom Typ

und

x_{1} - x_{2} > x_{3} - x_{4}

$x_1 - x_2 > x_3 - x_4$

x_{1} + 5 x_{8} - 17 x_{3} < - 5

$x_1 + 5x_8 - 17x_3 < -5$

O (n \log n)

$O(n\log n)$

x_{i} > x_{j}

$x_i > x_j$

O (n)

$O(n)$ Vergleiche vom Typ

. Die Frage ist, können Sie es besser machen, und die Antwort lautet Nein, wenn Sie sich nur auf lineare Abfragen (oder allgemeiner auf Abfragen mit begrenztem Grad) beschränken.

x_{i} - x_{j} > x_{k} - x_{ℓ}

$x_i - x_j > x_k - x_\ell$

Yuval Filmus

Ich bin mir nicht sicher, ob ich die praktische Bedeutung dieser Grenze für die Elementunterscheidbarkeit verstehe. Hätten Sie nicht ein erwartetes O (n) mit einer Hash-Tabelle?

JKFF

Eine Hash-Tabelle kann mit diesem Berechnungsmodell nicht implementiert werden. Im Allgemeinen sind Untergrenzen schwer zu beweisen. Das algebraische Entscheidungsbaummodell ist eines, bei dem nicht triviale Untergrenzen nachweisbar sind. Ich kann in keinem anderen Modell eine

nachweisen - tatsächlich sind solche Untergrenzen normalerweise nur für Zufallsfunktionen bekannt. Sie haben Recht, dass es einen Trick-

Algorithmus

gibt, der über dieses Modell hinausgeht, aber mir fällt keiner ein.

ω (n)

$\omega(n)$

o (n \log n)

$o(n\log n)$

Yuval Filmus

-1

Wenn Ganzzahlen im Array eine begrenzte Anzahl von Ziffern haben, können Sie ein Array mit dem Radix-Sortieralgorithmus sortieren , dh O (kN), und dann die benachbarten Zahlenpaare (O (N)) überprüfen. Die resultierende Komplexität ist O ((k + 1) N), linear.

Pavel Davydov
quelle

Beachten Sie die Bedingungen, unter denen die Laufzeit der Radix-Sortierung tatsächlich gut ist.

Raphael

@ Raphael Nun, die ursprüngliche Frage war, ob der lineare Algorithmus existiert, also habe ich darüber nachgedacht. Sie meinen, dass k für kleines N größer als log (N) ist?

Pavel Davydov

k

$k$

N

$N$

Ω (n \log n)

$\Omega(n \log n)$

@Raphael Ja, aber für ein Array von Ganzzahlen, die kleiner als 64 Bit sind (das ist ein ziemlich häufiger Fall), ist es linear. Ich werde meine Antwort bearbeiten. Danke für deine Kommentare.

Pavel Davydov