Finden Sie gemeinsame min in logarithmischer Zeit

Ich suche nach einer Datenstruktur zum Speichern einer Menge, so dass bei zwei Instanzen der Größe denen bekannt ist, dass sie einen nicht leeren Schnittpunkt haben, das minimale Element des Schnittpunkts in der Zeit kann. Ist dies entweder im schlimmsten Fall oder bei amortisierter Komplexität möglich? Weitere Anforderungen an die Datenstruktur: -Löschung, -Initialisierung. $O(n)$ $O(\log n)$ $O(\log n)$ $O(n \log n)$

Hier ist eine beispielhafte Anwendung einer solchen Datenstruktur, um die Anforderungen zu klären. Die Eingabe besteht aus n Teilmengen von alle die Nummer n enthalten. Die Ausgabe ist eine n x n-Matrix, deren Eintrag das minimale Element im Schnittpunkt der Mengen i und j ist. Mit einem grundlegenden Ansatz kann man dieses Problem in -Zeit lösen . Mit einer Datenstruktur, die die obigen Bedingungen erfüllt, könnte man sie in Zeit lösen . $\{1, ..., n\}$ $i, j$ $O(n^3)$ $O(n^2 \log n)$

data-structures heaps Vorniere
quelle

Die Situation, die mich am meisten interessiert, ist, wenn die Sets einen spärlichen unteren Schwanz haben und die Dichte stetig zunimmt. Zum Beispiel gibt es einen offensichtlichen O (d log n) -Algorithmus für Sätze mit einer Dichte, die unten durch 1 / d begrenzt ist. Dabei verwenden Sie min Heaps und beginnen mit dem Minimum eines Satzes. Dann ping pong hin und her und greifen immer nach dem nächstgrößeren Element auf dem Haufen, bis Sie sich stabilisieren.

Pre-Niere

Was bedeutet es für ein Set, einen spärlichen unteren Schwanz zu haben oder für eine stetig zunehmende Dichte?

Stellen Sie sich zum Beispiel eine zufällige Menge vor, in der das Element i mit der Wahrscheinlichkeit 1 / (ni) für i <n und n mit der Wahrscheinlichkeit 1 enthalten ist.

Vor der Niere

Wenn Sie die Frage bearbeiten können, um ein bestimmtes Problem anzugeben. Verteilung, die dies möglicherweise einfacher zu lösen macht. Wenn zum Beispiel jede Menge zufällig ausgewählt wird (wobei Element i mit der Wahrscheinlichkeit p enthalten ist, unabhängig von i), dann gibt es meiner Meinung nach einen natürlichen Algorithmus, dessen erwartete Laufzeit so etwas wie : zuerst aufzählen alle Paare von Mengen , die beide 1 enthalten; dann alle Paare, die 1 enthalten (aber noch nicht gefunden wurden); und so weiter. Es gibt eine einfache Stoppbedingung, und wenn die Sätze zufällig sind, müssen Sie vor dem Stoppen nicht sehr weit fortfahren.

O (n^{2} \log n)

$O(n^2 \log n)$

S_{i}, S_{j}

$S_i,S_j$

Als weiteres Beispiel gibt es für die spezifische Verteilung in Ihrem Kommentar einen einfachen -Zeitalgorithmus, da die erwartete Größe jedes Satzes .

O (n^{2} \log n)

$O(n^2 \log n)$

O (\log n)

$O(\log n)$

Antworten:

Das kannst du nicht. Es gibt keine solche Datenstruktur. Angenommen, Sie haben eine separate Instanz pro Satz und jede Instanz wird separat initialisiert (wobei nur Informationen zu dem Satz verwendet werden, den sie darstellt, und keine Informationen zu den anderen Sätzen), sind diese Laufzeiten nicht erreichbar.

Insbesondere wenn Sie zwei Sätze haben, dauert das Finden des minimalen gemeinsamen Elements Zeit. In der Tat erfordert das Testen der Disjunktheit -Zeit, wie hier erläutert . Stellen Sie sich nun vor, Sie beginnen mit zwei Mengen über dem Universum . Sei und . Jetzt haben garantiert ein gemeinsames Element. Wenn Sie also eine gute Datenstruktur für Ihr Problem hatten, speichern Sie in einer Instanz der Datenstruktur und in einer anderen. Wenn wir dann eine Möglichkeit hätten, das minimale Element von in zu finden $\Omega(n)$ $\Omega(n)$ $S_1,S_2$ $\{1,2,\dots,n-1\}$ $T_1=S_1 \cup \{n\}$ $T_2 = S_2 \cup \{n\}$ $T_1,T_2$ $T_1$ $T_2$ $T_1 \cap T_2$ $o(n)$ Zeit, dies würde uns eine Möglichkeit geben, die Disjunktheit von in Zeit zu testen (testen Sie einfach, ob das minimale Element kleiner als ) - aber wir wissen bereits, dass letzteres nicht möglich ist. Daraus folgt, dass Ersteres auch nicht möglich ist, dh, dass eine Datenstruktur für Ihr Problem Zeit benötigt, um das minimale gemeinsame Element von zwei Mengen zu finden. $S_1,S_2$ $o(n)$ $n$ $\Omega(n)$

Dies bedeutet nicht, dass Ihre Anwendung nicht effizient gelöst werden kann. Es könnte immer noch eine Möglichkeit geben, Ihre Anwendung in Zeit zu lösen . Dieses Ergebnis schließt das nicht aus. $O(n^2 \log n)$

DW
quelle

Ich würde mich sehr freuen, wenn Sie Ihre Antwort etwas eigenständiger gestalten könnten, da sie Ihre Antwort in einem anderen Beitrag zitiert, der wiederum ein Ergebnis zitiert, auf das Sie nicht Bezug genommen haben.

Vor-Niere

Lassen Sie mich genau darauf hinweisen, welcher Schritt meiner Meinung nach weiter ausgearbeitet werden muss. Der entscheidende Schritt in Ihrer Argumentation ist die Behauptung, dass die Lösung des Problems der Disjunktheitsentscheidung für Sätze, die auf welche Weise auch immer gespeichert sind, aber nicht auf den Speicher des anderen zugreifen können, Omega (n) Zeit benötigt. Sie behaupten, dass ein schnellerer Algorithmus den grundlegenden Ergebnissen der Kommunikationskomplexität widersprechen würde. Dieses Modell des Kommunikationskanals scheint jedoch allgemeiner zu sein als die grundlegenden Kommunikationsmodelle, die ich in der Literatur gefunden habe, für die die Omega (n) -Bindung bekannt ist. Deshalb bitte ich um ein bestimmtes Zitat.

Pre-Niere

@ Pre-Niere, ich verstehe nicht, wie es allgemeiner erscheint. Wie auch immer, es scheint, dass Ihr Einwand in erster Linie gegen meine andere Antwort gerichtet ist , also lassen Sie uns dort bitte eine Diskussion führen. Ich habe meine Antwort dort bearbeitet, um die Reduzierung im Detail zu artikulieren. Wenn Sie spezielle Bedenken hinsichtlich des Berechnungsmodells haben, kommentieren Sie dort bitte genau, welchen Unterschied im Berechnungsmodell Sie sehen. Ich sehe keinen, aber das heißt nicht, dass Sie sich irren - ich bin kein Experte auf diesem Gebiet, und ich könnte mich immer irren.

Faire Punkte und danke für das Update. Werde mal schauen.

Vor-Niere

-1

Hier ist eine Idee, um das Problem zu lösen, wenn 2 Sätze gegeben sind:

Sie können "Sets" an einem rot-schwarzen Baum halten. Zusätzlich ordnen wir für jeden Knoten im Baum ein Bit zu, um zu bestimmen, ob sein Teilbaum in beiden Mengen ein Element enthält. Zur Darstellung wird es als Einfügebit bezeichnet . Ich gehe davon aus, dass der rot-schwarze Baum die Elemente von links nach rechts sortiert.

Beim Einfügen eines Elements in den Baum prüft der Algorithmus, ob das Element im Baum vorhanden ist (dh in dem anderen die Menge). Wenn nicht, fügen wir das Element wie gewohnt ein. Wenn nicht, schaltet der Algorithmus das Einfügebit der entsprechenden Knoten ein, indem er von der Wurzel zu dem Blatt wandert, das das Element enthält. Im schlimmsten Fall dauert es . $O(\log n)$

Beim Löschen eines Elements prüft der Algorithmus, ob das Element im Baum vorhanden ist und ob das Einfügebit aktiviert ist. Wenn das Element nicht im Baum vorhanden ist, geben wir einen Fehler zurück. Wenn das Element vorhanden ist und das Einfügebit deaktiviert ist, löschen wir das Element wie im Rot-Schwarz-Baum-Algorithmus. Andernfalls schaltet der Algorithmus das Einfügebit der entsprechenden Knoten aus, indem er von der Wurzel zu dem Blatt wandert, das das Element enthält. Das Löschen dauert . $O(\log n)$

Schließlich beginnt der Algorithmus zum Finden eines minimalen Elements, das von beiden Sätzen gemeinsam genutzt wird, mit der Wurzel. Wenn das Einfügebit der Wurzel ausgeschaltet ist, werden die Mengen getrennt, und der Algorithmus gibt einen Fehler zurück. Andernfalls wandert der Algorithmus rekursiv zum linken Kind, wenn sein Einfügebit aktiviert ist, und andernfalls zum rechten Kind. Der Algorithmus stoppt beim Element mit dem Minimalwert. Der Algorithmus läuft bei . $O(\log n)$

Ich versuche zu überlegen, wie man das für eine größere Anzahl von Sätzen verallgemeinert ...

user3563894
quelle

Dies erfüllt nicht die angegebenen Kriterien, da davon ausgegangen wird, dass die beiden Instanzen während der Initialisierung einander bekannt sind. Wenn Sie viele Instanzen hätten und paarweise minimale Schnittpunkte finden müssten, würde dies das Timing nicht erfüllen, da Sie die Datenstruktur neu erstellen müssten für jedes Satzpaar.

Pre-Niere

Wenn die Instanzen einander nicht bekannt sind, können Sie sie in Zeit zusammenführen, indem Sie en.wikipedia.org/wiki/…

O (n)

$O(n)$

user3563894

Was ist der Input des Problems? Wenn Sie die Sätze initialisieren, können Sie die Elemente in einen gemeinsamen Baum einfügen / löschen. Wenn Sie dann aufeinanderfolgende Operationen zum Löschen und Einfügen verwenden, wirkt sich dies nicht auf die Komplexität einer Abfrage aus, für die

O (\log n)

$O(\log n)$

user3563894

Das ist der Punkt, die Sets können nicht gekoppelt werden. Lassen Sie mich meine Frage mit einer Beispielanwendung einer solchen Datenstruktur aktualisieren, um dies zu verdeutlichen.

Pre-Niere

Übrigens habe ich Sie nicht abgelehnt - ich denke, Ihre Antwort ist nützlich für die Diskussion und zusätzliche Klarstellung, die sie generiert hat, auch wenn sie meine Frage nicht wirklich beantwortet.

Pre-Niere

-1

Initialisieren:
1) Erstellen Sie einen rot-schwarzen Baum, der alle Elemente der Liste Nr. 1 - O (n log n) für die gesamte Liste enthält.
2) Durchlaufen Sie alle Elemente der Liste Nr. 2 und prüfen Sie, ob sie im rot-schwarzen Baum vorhanden sind - O (n log n) für die gesamte Liste.
3) Wenn sie im rot-schwarzen Baum vorhanden sind, fügen Sie dieses Element aus der Liste ein # 2 in Ihren Lieblings-Min-Heap - O (n log n) für die gesamte Liste

Um dann nach dem sich überschneidenden Element zu suchen, schauen Sie einfach oben auf den Heap, das ist also O (1).

Churro
quelle

Dieser Ansatz weist dieselben Probleme auf wie die Antwort von Benutzer 3563894 (siehe Kommentare dort).

Pre-Niere