Setzen Sie die Kombinationsdatenstruktur (und Speicherkomplexität)

Question

Ich habe diese Frage bereits veröffentlicht Paketüberfluss, aber ich fange an zu denken, dass dies der richtige Ort ist.

Ich habe ein Problem, bei dem ich einzigartige Kombinationen von einem Satz (eindeutige Teilmengen) mit einem bestimmten Wert assoziieren muss. EG: Lass S={a, b, c, d}, Die erforderliche Datenstruktur sollte Folgendes ausführen:

Schlüssel -> Wert

{a,b} -> value1
{a,c} -> value2
{c,d} -> value3

• Eigenschaft 1: Die Länge des Sets im Schlüssel wird festgelegt (in diesem Beispiel ist sie auf 2 festgelegt).
• Eigenschaft 2: Die Datenstruktur enthält nicht alle möglichen Teilmengen von S.

Frage 1: Was ist die Speicherkomplexität einer einfachen Karte, die diese Werte hält? AN!)? (Angesichts der Tatsache, dass | s | = n und es nicht repariert ist)

Frage 2: Gibt es effiziente Datenstruktur, die solche Elemente speichern könnten? (Die wichtigste Effizienz wäre in der Speicherkomplexität erforderlich)

Answer 1

Frage 1: Die Speicherkomplexität einer Karte für das Halten dieser Werte beträgt $ theta (M) $, wobei $ M $ die Anzahl der Einträge auf der Karte ist, vorausgesetzt, wir zählen den Raum nicht, um die Sets selbst zu speichern, und nicht Angenommen, wir speichern sie in einer Hash -Tabelle (oder einer ähnlichen Datenstruktur).

Dies beinhaltet nicht den Raum, um die Sets in den Schlüssel zu speichern, wie es vermutlich bereits existieren. Wenn Sie diesen Raum auch in Ihre Schätzung der Raumkomplexität einbeziehen möchten, benötigen wir höchsten SET enthält $ k $ Elements) für insgesamt $ theta (MK) $ Space. Ich gehe davon aus, dass jedes Element von $ s $ in einem einzelnen Wort ($ theta (1) $ space), z. B. $ n le 2^{64} $, gespeichert werden kann. Wenn $ n $ enorm ist, so dass ein Element von $ s $ in einem einzigen Wort nicht gespeichert werden kann, beträgt eine bessere Schätzung der gesamten Raumnutzung $ theta (Mk lg n) $, da es $ theta ($ theta ( lg n) $ bit, um ein einzelnes Element von $ s $ zu speichern. Jede Untergruppe von $ k $ Elements benötigt $ theta (k lg n) $ bit, und es gibt $ m $ Einträge in der Karte, von denen jede von ihnen Benötigt $ theta (k lg n) $ bit, um es zu speichern.

Die Anzahl der eindeutigen Teilmengen von $ k $, aus einem Universum von $ n $ Artikeln, beträgt $ {n wählen K} $. Wenn Sie also wissen, dass die Schlüssel Teilmengen von Größe $ k $ sind, wissen Sie, dass $ m le {n wählen K} $. Sie haben jedoch in der Frage erwähnt, dass die Anzahl der Einträge auf der Karte weniger als alle möglichen Teilmengen von Größe $ K $ ist. Dies ist also nicht hilfreich.

Frage 2: Ja, eine Hash -Tabelle wäre eine effiziente Datenstruktur, um diese Elemente zu speichern. Es gibt eine einfache Möglichkeit, eine Hash -Funktion auf Teilmengen von $ S $ zu definieren, sodass Sie diese verwenden können, um eine Hash -Tabelle zu erstellen. Eine Hash -Tabelle erreicht die oben aufgeführten Raumkomplexitäten.