Kann mir jemand Ideen für das folgende Problem geben?
Geben Sie für ein Array ar[] der Länge n und für einige Abfragen die Abfrage in der Form a, b, c die Nummer mit dem kleinsten Index ein i , so dass der Index im Bereich [c, n] und so in a < ar[i] < b liegt. Es gibt (n - 1) insgesamt, c geht von 1 bis n - 1 . Die erwartete Komplexität für jede Abfrage sollte ungefähr O(log n) und eine Vorberechnung der Komplexität höchstens O(n log n) ist geeignet. Intuitiv kam mir der Segmentbaum in den Sinn, aber ich konnte mir keinen Weg vorstellen, wie ich ihn bauen könnte oder was ich in jedem Knoten behalten würde.
Ich habe Mason Bryants Technik auf etwas geändert, das funktioniert. Die Probleme waren mehr Fehler in FindLowestIndex und ein größerer Fehler in der Baumstruktur (es können mehrere Ergebnisse zurückgegeben werden).
Trotz dieser Arbeit löst es das Problem noch immer nicht. O(n log n) Zeiteinstellung ist einfach genug, aber mit dieser Technik kann ich nur O((log n)^2) Abfragezeit bekommen. Ich frage mich, ob Sie eine Verbindung zu dem ursprünglichen Problem haben, falls es dort mehr Erklärungen gibt? Oder ich frage mich, ob das Problem wirklich lösbar ist. Oder vielleicht O((log n)^2) ist "über" O(log n) , wie das Problem anfragt, es ist sowieso weniger als O(n) .
Die Technik besteht darin, unser Array in einem typischen Segmentbaum zu speichern, aber zusammen mit den üblichen Segmentinformationen speichern wir auch in der Reihenfolge alle Indizes der Elemente unter jedem Knoten. Dieser zusätzliche Speicher benötigt nur einen zusätzlichen O(n log n) Zeit / Platz, wenn Sie ihn richtig addieren (n Elemente, die auf jedem der Protokollebenen gespeichert sind), so dass unsere Setup-Zeit in keiner Weise beeinträchtigt wird. Dann fragen wir den Baum ab, um den minimalen Satz von Knoten zu finden, die in unserem Bereich von (a, b) enthalten sind. Diese Abfrage benötigt etwa die gleiche Zeit wie eine typische Segmentbaumabfrage ( O(log n) ) und findet höchstens etwa 2 * log n passende Segmente. Bei der Abfrage finden wir den niedrigsten Index in jedem übereinstimmenden Segment, der unserer Bedingung c entspricht. Wir können eine binäre Suche verwenden, um diesen Index zu finden, da wir die Indizes in der richtigen Reihenfolge halten, so dass es für jeden übereinstimmenden Knoten den schlimmsten Fall O(log n) -Zeit benötigt. Wenn wir alles richtig addieren, ist die Gesamtzeit O((log n)^2) .
Lassen Sie mich wissen, welche Schritte Sie klären möchten.
C # -Code:
%Vor% Ok, ich dachte ich sollte die O(nlogn) / O(logn) Lösung implementieren, die ich mit user12861 besprochen habe.
Der Code funktioniert durch Erstellen von n -Bäumen, eines für jedes c . Jeder Baum teilt den größten Teil seines Inhalts mit den kleineren, mit einem Maximum von logn neuen Knoten. Auf diese Weise sind die gesamten Speicher- und Zeitkosten für die Vorverarbeitung auf O(nlogn) begrenzt.
Die tatsächlichen Bäume sind den Intervallbäumen ziemlich ähnlich. Die Knoten speichern den minimalen und maximalen Wert, über den sie sich erstrecken, und den kleinsten Index, den sie enthalten. Meine Implementierung ist jedoch nicht selbstausgleichend, aber dies kann mit Ihren Lieblingsheuristiken hinzugefügt werden.
%Vor%Hast du das durchgesehen? Ich denke, es wird dir helfen, es zu verstehen die Struktur und denke über eine Art und Weise des Aufbaus.Rest kann aus Vergleichen.
Der erste Versuch, den ich gemacht habe, baut einen Baum aus den Bereichen.
Sie würden zuerst den Stamm eines Teilbaums finden, der alle Lösungen für die Abfrage enthält. Das ist ziemlich einfach. Allerdings: Dieser Teilbaum enthält einige Werte außerhalb des Lösungssatzes.
Um die niedrigste Zahl zu finden, durchquert man den Baum zweimal (von der Wurzel auf der linken Seite des Baumes und wieder von der Wurzel auf der rechten Seite). An jedem Punkt in diesen Durchquerungen würden Sie überprüfen, ob Sie eine niedrigere Lösung als Ihre vorherige Lösung gefunden haben.
Wenn das erledigt ist, wäre die niedrigste Lösung innerhalb dieser Menge die niedrigste.
Da die Überprüfung der Lösungen jedes Knotens eine binäre Suche in der Indexliste innerhalb dieses Unterbaums erforderte, würden Sie bei O (ln (n) ^ 2) laufen, was zu langsam ist.
Die Verbesserung ergibt sich daraus, dass dies einfach wäre, wenn wir immer nach dem ersten Element im Array suchen würden. Dann müssen Sie keine binäre Suche durchführen, Sie erhalten nur das erste Element.
Um an diesen Ort zu gelangen, baut man am Ende n Bäume.
%Vor%So enthält jeder dieser Bäume nur die einzige beste Lösung.
Also läuft die Suche in O (ln (n)).
Im Beispielcode haben Sie sich die Freiheit genommen, den Baum zu erstellen, indem Sie keine benutzerdefinierten Datenstrukturen implementiert haben.
Sie erstellen ein Array von Knoten, erstellen eine Kopie dieses Arrays und sortieren eine der Kopien. Dies läuft in O (n ln (n)). Die andere Kopie wird verwendet, um die Position im sortierten Array zu finden, sodass Sie jedes Mal ein Element löschen können, wenn Sie einen anderen Baum erstellen.
Natürlich ist es möglich, einen Knoten in einer verknüpften Liste in konstanter Zeit zu löschen, aber da Sie nur einen Verweis auf das Objekt haben, vermute ich, dass die Java-Implementierung die verknüpfte Liste nach dem zu löschenden Element durchsuchen muss. Das Bauen der Bäume nimmt in diesem Beispiel wahrscheinlich O (n ^ 2). Leicht zu beheben, obwohl.
%Vor%Übrigens verwende ich noch Tests wie diese, um es gegen den Brute-Force-Ansatz zu verifizieren:
%Vor% Erstellen Sie ein Array von Indizes und sortieren Sie sie. Mit dem Array [20, 0, 10, 15, 5] würden Sie also ein initiales Array [0, 1, 2, 3, 4] erstellen. Jetzt sortieren Sie das Array der Indizes so, dass die Elemente in sortierter Reihenfolge angezeigt werden. Der sortierte Index wäre [1, 4, 2, 3, 0] . Sie enden mit zwei Arrays:
Sie können das ursprüngliche Array über das Tag-Array durchsuchen. Das heißt, Ihre Vergleichsfunktion vergleicht original[tag[x]] und original[tag[y]] . Das löst das Problem "wo ist der Index". Sie können dann die binäre Suche im Segment tag[c] ... tag[n] verwenden.
Scheint so, als müsste das funktionieren. Sie benötigen eine stabile Sortierung, so dass gleiche Zahlen ihre relative Reihenfolge beibehalten.
Wenn ich das richtig lese, gibt es n-1 Abfragen mit nur c, Warum lösen Sie dann die Abfragen nicht rückwärts? nehmen Sie zuerst die letzte Abfrage, da es das letzte Element des Array-Checks betrifft, ob das Element zwischen a und b fällt, wenn dies der Fall ist, speichern Sie das Ergebnis in einem Array ans [n-1] = n-1 sonst setzen wir ans [n-1] = -1, für jede nächste Abfrage j von n-2 nach 0
%Vor%Das alles kann in O (n) gemacht werden.