Untere Schranken für Datenstrukturen

14

Sind Ergebnisse bekannt, die das Vorhandensein von "Too Good To Be True" -Datenstrukturen ausschließen?

Beispiel: Kann man einer Auftragsverwaltungsdatenstruktur (siehe Dietz und Sleator STOC '87 ) die Funktionen und hinzufügen und trotzdem -Zeitoperationen erhalten ? $Split$ $Join$ $\mathcal{O}(1)$

Oder: Kann man eine geordnete Menge mit ganzzahligen Schlüsseln und -Zeitoperationen implementieren ? Dies ist natürlich mindestens so schwierig wie die Entdeckung eines linearen Zeitalgorithmus zum Sortieren ganzer Zahlen. $\mathcal{O}(1)$

Hat sich herausgestellt, dass die Antwort für jede dieser Fragen Nein ist ? Sind untere Ergebnisgrenzen für eine natürliche Datenstruktur bekannt?

ds.data-structures big-list lower-bounds time-complexity Shaun Harker
quelle

Die Dinge ändern sich, wenn wir den Problembereich einschränken können. Wenn wir zum Beispiel einen begrenzten Satz von Schlüsseln und genügend Speicher haben, können wir sie in linearer Zeit unter Verwendung eines Bitvektors sortieren.

Jetru

1

Ich denke, der Grund, warum Sie nicht zu viele Antworten auf diese Frage bekommen, ist, dass es einfach so viele Möglichkeiten gibt. Viele, viele Datenstrukturen kennen Untergrenzen, und es ist schwierig, nicht nur darüber zu stolpern. Eine Google-Suche nach "Datenstruktur" "Untergrenze" enthält für mich 5 Artikel, die in diesem Thread noch nicht erwähnt wurden. Ich denke, Sie hätten mehr Erfolg mit der Beantwortung Ihrer Frage, wenn Sie sie einschränken würden, indem Sie vielleicht den Teil über "natürliche Datenstruktur (en)" entfernen und nur nach der Listenpflege oder nach ganzzahlig geordneten Mengen fragen (aber nicht beides in einer Frage).

Jbapple

Ich habe weggelassen, dass die 5 Artikel, die ich in der Google-Suche gefunden habe, nur auf der ersten Seite der Suchergebnisse waren.

Jbapple

@jbapple: Du hast recht! Ich denke, dass die Klicks von Leuten in dieser Community, die mir bei meiner Frage helfen wollten, die guten Ergebnisse an die Spitze der Liste gebracht haben. (Zum Beispiel ist DIESE Seite jetzt in der Liste!) Ich erinnere mich nicht, dass es nützlich war, als ich die Suche zum ersten Mal durchführte, oder ich hätte die Frage wahrscheinlich eingeschränkt, wie Sie vorschlagen. (Oder ich war ein großer Dummy, das ist auch möglich. :))

Shaun Harker

19

Es gibt einen sehr schönen Vortrag über die dynamischen Untergrenzen von Graphen von Mihai Pătraşcu. Zusammenfassend (auf Seite 20 der Folien) haben wir die Untergrenzen in Bezug auf die Abfragezeit und die Aktualisierungszeit (Einfügen einer Kante): $t_q$ $t_u$

Bildbeschreibung hier eingeben

Einzelheiten finden Sie im Papier . Einige andere Artikel von Mihai sind auch relevant und nett.

UPDATE: Ich fand heraus, dass seine Doktorarbeit " Lower Bound Techniques for Data Structures " mit den von ihm entwickelten Techniken untere Grenzen für viele zentrale Datenstrukturprobleme liefert. Es ist auf jeden Fall eine Lektüre wert.

Hsien-Chih Chang 張顯張顯
quelle

1

Diese These ist wunderbar. Vielen Dank, dass Sie den Link geteilt haben.

Shaun Harker

6

Die Antwort auf eine Ihrer Fragen hängt vom Berechnungsmodell ab. Zum Beispiel ist das Multiplizieren von ganzen Zahlen auf vielen Maschinen teurer als das Addieren. Einige Modelle spiegeln dies wider, andere nicht.

$O(\sqrt{\log n/ \log \log n})$

Apfel
quelle

Nett. Aber anscheinend haben Sie das Ergebnis in den Zeitungen von Andersson und Thorup übertrieben. Sie gilt nur für lineare Raumstrukturen, nicht für alle polynomialen Raumstrukturen.

Shaun Harker

2

Andersson und Thorup zitieren Beame und Fich für den Polynomraum: "Die untere Schranke ergibt sich aus einem Ergebnis von Beame und Fich. Sie zeigt, dass, selbst wenn wir nur Einfüge- und Vorgängeroperationen im Polynomraum unterstützen wollen, eine dieser beiden Operationen a Worst-Case-Schranke von Ω (sqrt (log n / log log n)), passend zu unserer gemeinsamen oberen Schranke. Wir stellen fest, dass man für einige der einzelnen Operationen bessere Schranken und Kompromisse finden kann. In der Tat werden wir min unterstützen, max, Vorgänger, Nachfolger und Löschoperationen in konstanter Zeit und nur in only (sqrt (log n / log log n)) Zeit einfügen und suchen. "

Jbapple

Ich verstehe, der lineare Raum kommt herein, um für die obere Schranke zu werben , aber Korollar 3.10 von Beame und Fich gibt die untere Schranke des Polyraums an , wie Sie sagten, und ich widerspreche törichterweise. Mir kommt auch der Gedanke, dass man die Worst-Case-Zeiten für Obergrenzen und die Amortisationszeiten für Untergrenzen ankündigen möchte. Das Papier von Andersson und Thorup zitiert tatsächlich (Seite 5) Beame und Fich für eine amortisierte untere (und obere) Grenze. Korollar 3.10 scheint jedoch nur die Untergrenze für den schlimmsten Fall anzugeben. Vielleicht könnte mir auch jemand einen Hinweis geben?

Shaun Harker

2

In Ergänzung zu dem, was Sie zu Ihrer Frage erwähnt haben, wird als klassisches Beispiel die Tatsache verwendet, dass Ganzzahlen nicht schneller als durch Vergleiche sortiert werden können $O(n \log n)$ um das Fehlen von Aufbauten zu beweisen.

Darüber hinaus ist es nicht ungewöhnlich, informationstheoretische Argumente (z. B. Kolmogorov-Komplexität) zu verwenden, um untere Grenzen für Datenstrukturen zu beweisen.

Chazisop
quelle

Untere Schranken für Datenstrukturen

Antworten: