Vergleichsbasierte Datenstruktur zum Auffinden von Artikeln

Gibt es eine Datenstruktur, die ein ungeordnetes Array von Elementen annimmt , eine Vorverarbeitung in und Abfragen beantwortet: Befindet sich ein Element in der Liste, jede Abfrage in der schlechtesten Zeit ? $n$ $O(n)$ $x$ $O(\log n)$

Ich denke wirklich, dass es keinen gibt. Ein Beweis dafür, dass es keinen gibt, ist auch willkommen.

ds.data-structures sorting Chi-Lan
quelle

(1) Ich weiß nicht, warum Sie "Natürlich berücksichtige ich die erwartete Zeit" sagen können, weil Sie in Ihrer Frage überhaupt nicht "erwartet" angeben. Bitte versuchen Sie, Ihre Frage genauer zu formulieren, bevor Sie "natürlich" sagen. (2) Definieren Sie "nicht hashbar".

Tsuyoshi Ito

(1) Ich verstehe. Danke für die Erklärung. Wenn jemand gefragt wird, ob Ihnen die Laufzeit wichtig ist, lautet die Antwort in der Tat „natürlich“. :) (2) Ich denke, dass „die einzig zulässige Aktion darin besteht, zwei Werte in der Liste zu vergleichen“, viel präziser ist Können Sie die Frage so bearbeiten, dass die Benutzer die Kommentare nicht lesen müssen, um zu verstehen, was "nicht hashbar" bedeutet?

Tsuyoshi Ito

Übrigens, wenn Sie es nicht beweisen können, warum wissen Sie, dass es unmöglich ist? Wenn es sich um eine Übung in einem Lehrbuch oder einer Klasse handelt, fragen Sie auf einer falschen Website.

Tsuyoshi Ito

Ist dies Ihre Frage: Gibt es eine Datenstruktur, die ein ungeordnetes Array von n Elementen annimmt, eine Vorverarbeitung in O (n) durchführt und Abfragen beantwortet: Befindet sich ein Element x in der Liste, jede Abfrage in der schlechtesten Zeit O (log n)?

SDCVVC

@Filip: Ist das leicht zu sehen? Wenn es wahr ist, bin ich damit einverstanden, dass es die Frage löst.

Tsuyoshi Ito

Antworten:

Hier ist ein Beweis, dass es unmöglich ist. Angenommen, Sie könnten eine solche Datenstruktur erstellen. Baue es. Wählen Sie dann zufällige Elemente aus der Liste aus, fügen Sie jedem , wobei kleiner als die Differenz zwischen zwei Elementen in der Liste ist, und führen Sie die Abfragen durch, um zu prüfen, ob eines der resultierenden Elemente vorhanden ist ist in der Liste. Sie haben bisher Abfragen durchgeführt. $n/\log n$ $\epsilon$ $\epsilon$ $O(n)$

Ich möchte behaupten, dass die von Ihnen durchgeführten Vergleiche ausreichen, um festzustellen, ob ein Element in der ursprünglichen Liste kleiner oder größer als ein neues Element . Angenommen, Sie könnten es nicht sagen. Da es sich dann um ein vergleichsbasiertes Modell handelt, würden Sie nicht wissen, ob gleich oder nicht. Dies ist ein Widerspruch zu der Annahme, dass Ihre Datenstruktur funktioniert. $a$ $b$ $a$ $b$

Da die von Ihnen ausgewählten Elemente zufällig waren, haben Ihre Vergleiche mit hoher Wahrscheinlichkeit genügend Informationen geliefert, um die ursprüngliche Liste in Listen der Größe . Indem Sie jede dieser Listen sortieren, erhalten Sie einen zufälligen -Zeit-Sortieralgorithmus, der ausschließlich auf Vergleichen basiert. Dies ist ein Widerspruch. $n/\log n$ $n/\log n$ $O(\log n)$ $O(n \log \log n)$

Peter Shor
quelle

Ein paar Hinweise zum besseren Verständnis des Beweises (vorausgesetzt, ich verstehe ihn natürlich selbst richtig): Die Elemente sollten von den Elementen ausgefüllt werden, nachdem ihnen hinzugefügt wurde. Das Vergleichsmodell garantiert, dass Sie wissen, welcher der Fälle und gilt. Die Listen sind in aufsteigender Reihenfolge: Jedes Element in einer höheren Liste ist höher als jedes Element in einer niedrigeren Liste. Nach den ursprünglichen Abfragen haben Sie genügend Informationen , um die Listen um die Elemente zu erstellen, die Sie zufällig ausgewählt haben.

b

$b$

ϵ

$\epsilon$

a \leq b

$a \leq b$

a \geq b

$a \geq b$

n / \log n

$n / \log n$

Alex ten Brink

(Fortsetzung) Beachten Sie, dass Sie nicht einmal explizit in der Lage sein müssen, die Liste in der angegebenen Zeit zu erstellen, damit der Proof gespeichert werden kann.

Alex ten Brink

Ich verstehe diesen Beweis nicht ganz. Der letzte Widerspruch ist "Algorithmus, der nur auf Vergleichen basiert", aber in den ersten Schritten unseres Algorithmus haben wir jedem Element hinzugefügt (ferner "wobei kleiner ist als die Differenz zwischen zwei Elementen auf der Liste"). Warum ist es immer noch gerechtfertigt, dass unser Algorithmus nur dann auf einem Vergleich basiert, wenn wir davon ausgehen, dass unsere Artikel eine nicht diskrete Gesamtreihenfolge aufweisen?

ϵ

$\epsilon$

ϵ

$\epsilon$

Artem Kaznatcheev

@Artem: Ihr ursprünglicher Eingang besteht aus Elementen . Dann konstruieren Sie eine neue Menge ; Sie repräsentieren ein ursprüngliches als und ein modifiziertes als . Jetzt verwenden Sie den Black-Box-Algorithmus. der Algorithmus vergleicht Elemente von miteinander; Um solche Fragen zu beantworten, müssen Sie nur eine konstante Anzahl von Elementen von miteinander vergleichen. Daher sollte im Vergleichsmodell alles machbar sein, mit einem konstanten Overhead.

x \in X

$x \in X$

X^{'} = X \times {0, 1}

$X' = X \times \{0,1\}$

x \in X

$x \in X$

(x, 0) \in X^{'}

$(x,0) \in X'$

x + ϵ

$x + \epsilon$

(x, 1) \in X^{'}

$(x,1) \in X'$

X^{'}

$X'$

X

$X$

Jukka Suomela

@Aryabhata: Das tut es. Was ist der

-Algorithmus?

O (\log^{2} n)

$O(\log^2 n)$

Peter Shor

Ich glaube, hier ist ein anderer Beweis, der die Unmöglichkeit einer -Abfragezeitstruktur mit -Vorbearbeitung beweist . $\mathcal{O}(\log ^k n)$ $\mathcal{O}(n)$

Angenommen, Sie führen in der Vorverarbeitung Vergleiche durch, die zu einer Teilreihenfolge führen. $\mathcal{O}(n)$

Betrachten Sie nun die Größe des größten Antichains darin. Da diese Elemente nicht vergleichbar sind, für uns ein haben Abfrage - Algorithmus, müssen wir haben , dass . $A$ $\mathcal{O}(\log ^k n)$ $A = \mathcal{O}(\log ^k n)$

Nach dem Satz von Dilworth gibt es nun eine Aufteilung der Größe in Ketten. $A$

Jetzt können wir den Algorithmus ergänzen, um die Ketten in der Partition zu bestimmen. Wir können feststellen, ob zwei Elemente vergleichbar sind, indem wir einen gerichteten Vergleichsdiagramm erstellen und eine Erreichbarkeitsanalyse durchführen. Dies kann ohne zusätzliche Vergleiche durchgeführt werden. Nun zwingen Sie einfach jede mögliche Partition der Größe um festzustellen, ob es sich um eine Partition von Ketten handelt. $A$

Sobald wir die Ketten haben, können wir sie zusammenführen, um einen -Vergleichsalgorithmus zum Sortieren der gesamten Liste zu erhalten. $\mathcal{O}(n \log \log n)$

Aryabhata
quelle

Das ist eine schöne Idee. Und wenn Sie zeigen könnten, dass die Kettenpartition dem Algorithmus bekannt sein muss, könnten Sie mit mergesort zeigen, dass nur zusätzliche O (n log log n) -Vergleiche erforderlich sind, um die gesamte Eingabe zu sortieren, anstatt Jensen zu verwenden. Es gibt jedoch ein Problem: Warum muss der Vorverarbeitungsalgorithmus eine Kettenpartition erstellen? Ja, es muss eine Kettenpartition geben, aber das ist etwas ganz anderes, als dem Algorithmus bekannt zu sein.

David Eppstein

O (n \log \log n)

$O(n\log\log n)$

Ω (n \log n)

$\Omega(n\log n)$

Ω (n)

$\Omega(n)$

@Yuval: Vielleicht sollten Sie diese Beobachtung als eine tatsächliche Antwort aufschreiben, da ich der Meinung bin, dass Sie einen moderaten Arbeitsaufwand leisten müssen, um das obige Ergebnis aus den Beweisen in den Antworten zu erhalten.

Peter Shor

Ω (n \log n)

$\Omega(n \log n)$

Ω (n^{1 - ϵ})

$\Omega(n^{1-\epsilon})$

ϵ

$\epsilon$

o (n \log n)

$o(n \log n)$

O (n / \log n)

$O(n / \log n)$

\log n

$\log n$

n / \log n

$n/\log n$

θ (n \log \log n)

$\theta(n \log\log n)$

$k<n$ $Θ(n \log k)$ $n$ $c>0$ $c \, n \log k$ $≤c \, n \log k/k$ $k' = k / \log k ≤ n/\log n$ $O(n \log k') = O(n \log k)$ Zeit, die Abfragekosten ermöglicht. $O(n/k')$

Insbesondere bei Verwendung der -Vorbearbeitung können keine -Anfragekosten anfallen. Außerdem entspricht die Vorverarbeitung von in für jedes und damit Abfragekosten. $O(n)$ $o(n)$ $o(n \log n)$ $k$ $O(n^ε)$ $ε>0$ $Ω(n^{1−ε})$

Dmytro Taranovsky
quelle