Angesichts einer ungeordneten Liste von n nichtnegativen ganzen Zahlen (ohne Garantien für Verteilung oder Wiederholung) möchte ich eine ganze Zahl erhalten, die möglicherweise nicht in der Liste ist, und mit der Anzahl der ganzen Zahlen antworten, die mindestens so groß sind In der Liste. Ich habe bis zu n ^ 2 Vorverarbeitungszeit und bis zu n * log (n) Speicher. Ist das möglich?
Meine nicht gut genug Lösung ist binäre Suche (log n Zeit, konstanter Raum).
Das Speichern einer Karte aller möglichen Abfragen in einer Karte würde zu viel Speicherplatz beanspruchen.
Edit: Teillösungen, die einige Annahmen über die Eingaben benötigen, wie die Verteilung oder die maximale Größe einer ganzen Zahl, sind ebenfalls nützlich.
Edit: Dies ist bekannt als das Vorgänger / Nachfolger-Problem. Es gibt ein Papier von Beame & amp; Fich, in dem sie eine Datenstruktur konstruieren, die n Elementmengen von Ganzzahlen aus einem Universum der Größe N im O (n) -Raum speichert und Vorgängerabfragen in O ausführt (min {(log log N) / (log log log N), sqrt (log n / (log log n))}) Zeit.
Bearbeiten - Kopfgeld: Keine der Antworten von heute morgen ist genau das, wonach ich suche. N ist nicht begrenzt. Ganzzahlen sind nicht notwendigerweise unter 32 Bits. Das größte Element kann viel größer als die Anzahl der Elemente sein. Ich nehme keine Verteilung auf den Eingängen an. Von den vorhandenen Antworten akzeptierte ich Coffins für das Kopfgeld, weil es die relativ große Teilmenge von Problemen abdeckt, bei denen ich die Verteilung habe.
Unter der Annahme, dass Ihre Elemente einigermaßen gleichmäßig verteilt sind (oder zumindest einigen -Distributionen ziemlich genau folgen), wäre die naheliegende Methode, die Daten zu sortieren und dann eine interpolierende Suche anstelle einer binären Suche zu verwenden. p>
Eine interpolierende Suche hat normalerweise ungefähr O (log log n) Komplexität.
Oh, falls es aus dem Namen nicht offensichtlich ist, besteht die Grundidee einer interpolierenden Suche darin, eine Interpolation zu verwenden, um den ungefähren Ort des Elements, nach dem Sie suchen, zu erraten. Wenn Sie z. B. mit Ganzzahlen zwischen 0 und 100.000 arbeiten und z. B. 21.000 finden müssen, können Sie an einer Stelle etwa 21% des Weges in das Array beginnen, anstatt von der Mitte aus zu beginnen. Basierend auf dem Wert, den Sie dort finden, können Sie Interpolation verwenden, um eine bessere Schätzung zu finden, und so weiter.
Dieses Beispiel dient der linearen Interpolation, aber die gleiche Grundidee gilt auch für andere Distributionen - Sie müssen nur eine Funktion verwenden, die (angemessen gut) mit der Datenverteilung übereinstimmt.
Abhängig von Ihren Parametern können Sie Ссылка - "eine Baumdatenstruktur, die ein assoziatives Array mit m- bit integer keys. Es führt alle Operationen in O (log m) -Zeit oder äquivalent in O (log log M) -Zeit durch, wobei M = 2 ^ m die maximale Anzahl von Elementen ist, die im Baum gespeichert werden können. " (Beachten Sie die Warnung oben im Artikel, die besagt, dass ein Bug in ihrem Pseudocode enthalten ist)
(Hinweis: Diese Antwort wurde gepostet, bevor OP seinen Kommentar zu templatetypedef entfernt hat: "Wie bei der Integer-Größe können wir 32 Bit ohne Vorzeichen annehmen.")
Bereiten Sie einen Hash-Satz vor, der auf 65536 sortierte Buckets zeigt (technisch ist das O(1) zusätzlicher Speicherplatz, obwohl wir sagen können, dass etwa 5500 Elemente den Schwellenwert darstellen, oberhalb dessen der Speicherplatz kleiner wäre als Ihr festgelegter n * log n ) . Jeder Schlüssel stellt eine mögliche Konfiguration der linken 16 Bits von Ihrem zugeteilten 32 dar. Jeder Bucket speichert, wie viele Elemente sich über dem aktuellen Bucket befinden, sowie die Listenwerte in diesem ganzzahligen Bereich und zählt gegebenenfalls deren Duplikate.
Beim Einfügen müssen alle unteren Bucket-Zählwerte aktualisiert werden; technisch, eine O(1) Aktualisierungszeit, obwohl deutlich signifikant für niedrigere Listen; Wenn die Liste jedoch im Voraus bekannt ist, wie Sie es vorgeschlagen haben, kann die Vorverarbeitungszeit O(n * log n) sein, indem die Zähler von oben nach unten von Bucket zu Bucket "gemeldet" werden. Eine Abfrage benötigt O(1) time, um den Bucket zu suchen. Die Suche innerhalb des Buckets könnte höchstens log m annehmen, wobei m , die Anzahl der Elemente im Bucket, kleiner oder gleich 65536 ist, eine Konstante unabhängig von n .
Bei der Vorverarbeitung können je nach Bereich und Verteilung zwei oder drei Offset-Hashes zur weiteren Optimierung verwendet werden.
(Hinweis: Diese Antwort wurde gepostet, bevor OP seinen Kommentar zu templatetypedef entfernt hat: "Wie bei der Integer-Größe können wir 32 Bit ohne Vorzeichen annehmen.")
Der Y-schnelle Trie (siehe meine andere Antwort) könnte uns zu O(log log U + log log U) lookup time bringen, was bedeutet, dass, wenn Ihr Bereich in Milliarden liegt, wir praktisch 5 + 5 = 10 Iterationen pro Suche suchen.
Aber es gibt eine Möglichkeit, eine praktische Nachschlagezeit von 5 Iterationen zu erreichen.
Hash alle Kombinationen der am weitesten links 17 Bits. Zeigen Sie diese 131.072 Schlüssel auf X-schnelle Versuche (siehe meine andere Antwort) von max. Höhe 15 und maximalem Platz m * 15 wobei m die Anzahl der Elemente in diesem bestimmten Bucket ist. Die Versuche enthalten nur die äußersten 15 Bits jedes geeigneten Elements der Liste. Da diese X-Fast-Versuche in ihrer Größe beschränkt sind, wird die Nachschlagezeit auf 1 + log 15 = 5 begrenzt. Wenn Ihre Liste unter 32.768 Elemente liegt, ist der Speicherplatz praktisch 131,072 + n * 15 , etwas mehr als die angeforderte n * log n ; Da aber die Hash- und Max-Trie-Höhe konstant sind, ist die asymptotische Raumkomplexität tatsächlich O(n) , und bei einer Liste von 32.768 Elementen oder mehr wäre die Raumkomplexität praktisch kleiner als n * log n .
Hier ist eine grobe Skizze in JavaScript eines X-schnellen Baumes:
%Vor%Ausgabe:
%Vor%(Hinweis: Diese Antwort wurde gepostet, bevor OP seinen Kommentar zu templatetypedef entfernt hat: "Wie bei der Integer-Größe können wir 32 Bit ohne Vorzeichen annehmen.")
Die von Dan Willard erfundene Y-fast trie ( Ссылка ) unterstützt die Art von Operationen und Zeit-Komplexität, nach der Sie suchen. Es verwendet O(n) Leerzeichen und O(log log U) asymptotische Suchzeit, wobei U der größte Wert in der Domäne ist, der für unsere Zwecke der größte Wert in Ihrer Liste sein könnte. Das bedeutet, dass eine reguläre binäre Suche mit mehr als 32 Elementen in Ihrer Liste bereits asymptotisch langsamer wäre.
Der Y-schnelle Trie wird aus n / log U binären Suchbäumen konstruiert, die zusammen die ganze sortierte Liste als eine Folge enthalten; und ein X-schneller Trie ( Ссылка ), der einen Repräsentanten für jeden der binären Suchbäume in enthält um nachzusehen, in welchem Baum gesucht werden soll.
Ich werde ein wenig von dem beschreiben, was ich gelernt habe (weil ich nur ein wenig gelernt habe) über die Methode des Nachfolge- / Vorgänger-Looks des X-schnellen Trie, die Operation, an der Sie interessiert scheinen. Asymptotische Zeitkomplexität für die Suche ist O(log log U) .
Eine Suche nach dem Vorgänger / Nachfolger von k beginnt mit einer binären Suche durch die Ebenen des Trie, die die Höhe log U hat. Wir beginnen den halben Weg durch den Trie - wenn das Präfix von k der Länge, die diesem Level entspricht, nicht zu den gehashten Knoten des Trie gehört, muss der Vorgänger von k darüber sein, sonst unten.
Sobald der Vorgänger gefunden wurde, wissen wir, dass ein Unterbaum dieses Knotens Blätter hat (Blätter sind wo die Werte des Trie gespeichert sind), aber der andere, wo k gewesen wäre, nicht. Hier wird auf den genialen descendant pointer zugegriffen, der entweder auf das kleinste Blatt in einem rechten Teilbaum zeigt, wenn der linke Teilbaum fehlt, oder auf das größte Blatt in der linken, wenn das rechte fehlt.
Wir befinden uns jetzt entweder direkt beim Vorgänger oder Nachfolger von k und können den gespeicherten Wert des Trie melden: In welchen Binärbaum soll gesucht werden. Asymptotische Raumkomplexität: O(n + n / log U * log U) = O(n) . Asymptotische Zeitkomplexität: O(log log U + log log U) = O(log log U)
Wenn die Zeit und der Speicherplatz für die Vorverarbeitung ausreichen, um die Daten in einen Baum zu übertragen, können Sie einen sortierten Baum erstellen, in dem jeder Zweig speichert, wie viele Blätter mit seiner rechten Seite (größer als) verbunden sind. Beim Konstruieren des Baumes kann diese Anzahl für jeden Zweig, den Sie rechts passieren, beim Einfügen eines neuen Blattes inkrementiert werden, so dass es nicht (viel) zusätzliche Zeit benötigt. Die Anzahl der Werte, die größer oder gleich einer bestimmten Ganzzahl sind, kann dann ermittelt werden, indem die Stelle der Ganzzahl im Baum gefunden wird und alle Zählungen der Zweige, die Sie auf der linken Seite passieren, addiert werden.
Die Zeitkomplexität wäre die reguläre Komplexität des Baumtyps plus ein paar Wertinkremente pro Blatt während der Konstruktion, und der Raum wäre der reguläre Raum plus ein Zähler für jedes Blatt, dessen Größe von der maximalen Anzahl abhängt Blätter.
Im Beispielcode habe ich einen einfachen Binärbaum verwendet; Sie könnten die verbleibende Vorverarbeitungszeit verwenden, um den Baum in der Höhe zu balancieren (stellen Sie sicher, dass die Zählerstände aktualisiert werden), oder verwenden Sie einen selbstbalancierenden Baumtyp (was sich jedoch als übermäßig kompliziert erweisen würde).
Beispiel Code-Snippet in Javascript: (verwendet 100.000 zufällige Ganzzahlen; behandelt doppelte Werte und sucht Werte, die nicht in der Baumstruktur vorhanden sind)
Update: Das Erhöhen des Zählwerts könnte verwendet werden, um doppelte Werte zu behandeln, wenn Sie davon viele erwarten und Speicherplatz ein Problem darstellt.
Mit auf 32 Bits begrenzten Ganzzahlen macht die Frage keinen Sinn. In der Tat, wenn N kleiner als 2 ^ 32 ist, dann ist es begrenzt und asymptotische Komplexitäten ergeben keinen Sinn.
Wenn N unbeschränkt ist, können Sie die Werte sortieren und ihre Multiplizität in der linearen Zeit zählen. Auf diese Weise ist die Anzahl der Elemente wieder begrenzt und asymptotische Komplexitäten ergeben keinen Sinn mehr.
Etwas ist in der Problembeschreibung fehlerhaft.
Tags und Links algorithm language-agnostic data-structures