Ich lese die 4. Ausgabe von Algorithmen. Ich habe einige Fragen beim Lesen von Kapitel 3 Suchen. Aus der Kostenübersicht die Einfügekosten von BinarySearchST (2N im schlimmsten Fall) ist ein bisschen schlechter als SequentialSearchST (N im schlimmsten Fall). Aber der FrequencyCounter-Test mit VisualAccumulator (der Plots zeichnet) zeigt
Zurück zu den Kosten der put () - Operationen für FrequencyCounter für Wörter von Länge 8 oder mehr, sehen wir eine Verringerung der durchschnittlichen Kosten von 2.246 Vergleiche (plus Array-Zugriffe) pro Operation für SequentialSearchST bis 484 für BinarySearchST.
Sollten die put () - Operationen von BinarySearchST nicht mehr Vergleiche (plus Array-Zugriffe) benötigen als SequentialSearchST?
Eine weitere Frage, für BinarySearchST, sagt das Buch
Vorschlag B (Fortsetzung). Das Einfügen eines neuen Schlüssels in ein geordnetes Array der Größe N verwendet im schlimmsten Fall ~ 2 N Array-Zugriffe Wenn Sie N Schlüssel in eine anfänglich leere Tabelle einfügen, wird ~ verwendet N 2 Array greift im schlimmsten Fall auf
zu
Wenn ich mir den Code von BinarySearchST anschaue, denke ich, dass das Einfügen eines neuen Schlüssels in ein geordnetes Array der Größe N ungefähr 4N dauert Array-Zugriffe.
%Vor%Weil für jedes i in der Schleife 4 Array-Zugriffe vorhanden sind, 2 für das Lesen und Aktualisieren von Schlüsseln, 2 für Werte lesen und aktualisieren. Warum sagt Prop B also ~ 2N Array-Zugriffe?
Sollten die put () - Operationen von BinarySearchST nicht mehr Vergleiche (plus Array-Zugriffe) benötigen als SequentialSearchST?
Der Schlüssel zu verstehen ist, woher kommt die Komplexität für jede dieser zwei Symboltabellenimplementierungen. SequentialSearchST erreicht seinen schlimmsten Fall, wenn der Eingabeschlüssel nicht vorhanden ist, weil er in diesem Fall N sequestions ausführen muss (und N fehlt). Je nach Typ des Eingabetextes kann dies häufig vorkommen. selbst wenn der Schlüssel bereits vorhanden ist , gibt es N/2 im Vergleich, um ihn sequenziell zu finden.
Wie bei BinarySearchST wird im schlimmsten Fall nach den Schlüsselkosten logN gesucht. Die Komplexität ergibt sich daher aus der Größenänderung des Arrays und / oder dem Verschieben der vorhandenen Elemente nach rechts, um Platz für einen neuen Schlüssel zu schaffen. Beachten Sie, dass wenn der Schlüssel fehlt, Sie N/2 im Durchschnitt bewegen sollten, und wenn Schlüssel dort ist, vergleicht nur logN im Durchschnitt. In diesem Fall hängt die Gesamtlaufzeit stark von der Verteilung der Schlüssel ab - wenn neue Schlüssel kommen, wird die Laufzeit höher sein!
Der von ihnen durchgeführte Test beinhaltete den Text "Tale of two cities" von Charles Dickens, der nur Wörter mit 8 oder mehr Buchstaben umfasste. Es gibt 14350 solcher Wörter, von denen 5737 verschieden sind. Nach 14350 put() Operationen und 5737 Schlüsseln in der Tabelle würden Sie erwarten, dass 5737/2 = 2868 Vergleiche eine weitere put() in SequentialSearchST ausführen. Aber es ist besser als das, du brauchst "nur" 2246 Vergleiche. Die Laufzeit von BinarySearchST hängt wesentlich vom Vorhandensein des Schlüssels ab; Das Experiment zeigte, dass für diesen Text weit mehr O(logN) Suchen existierender Schlüssel als O(N) Bewegungen erforderlich waren, um neue Schlüssel einzufügen, was zusammengenommen kleinere Kosten als SequentialSearchST ergibt. Kombinieren Sie nicht Durchschnitts- und Worst-Case-Laufzeit, diese Analyse basiert auf der durchschnittlichen Fallkomplexität für das spezifische Beispiel.
Wenn ich mir den Code von BinarySearchST ansehe, denke ich, einen neuen Schlüssel einzufügen in ein geordnetes Array der Größe N verwendet ~ 4N Array-Zugriffe.
Die Autoren sollten die genaue Definition des Zugriffs präzisiert haben. Wenn der Verweis auf das Array-Element Zugriff bedeutet, gibt es noch mehr, 8N-Array-Zugriffe, da Sie im schlimmsten Fall zuerst die Größe des gesamten Arrays ändern sollten (schauen Sie sich die Implementierung von resize() an). Natürlich könnte die gesamte Implementierung neu geschrieben werden, um die Anzahl der Zugriffe in diesem Fall zu optimieren, indem ein neuer Schlüssel an der richtigen Stelle während der Größenänderung eingefügt wird.
"Sollten die put() -Operationen von BinarySearchST nicht mehr Vergleiche (plus Array-Zugriffe) als SequentialSearchST benötigen?"
Nein, weil das Buch früher über den WORST-Fall spricht.
Worst- und Average-Fälle sind unterschiedlich. Aus dem nächsten Satz des Buches können wir lesen: "Nach wie vor sind diese Kosten noch besser, als durch die Analyse vorhergesagt werden würde, und die zusätzliche Verbesserung wird wahrscheinlich wieder durch Eigenschaften der Anwendung erklärt ..."
"Also, warum prop B sagt, dass es ~ 2N Array-Zugriffe verwendet?"
Irgendwann denke ich, du hast Recht, formal gibt es 4N Zugriffe, aber
Was ist, wenn wir die Schleife wie folgt umschreiben:
%Vor%wird es bedeuten, dass wir immer noch 4N Zugriffe verwenden? Ich gehe davon aus, dass der JIT-Compiler die Schleife richtig optimieren kann.
Auch können wir eine Annahme machen, dass Arrays normalerweise als linearer Speicher dargestellt werden, Computer Daten in virtuelle Seiten lesen, also wurde auf eine solche Seite bereits zugegriffen und sie befindet sich in einem Cache.
Wenn ein binärer Suchbaum "ausgeglichen" ist, wird es viel weniger Vergleiche geben.
%Vor%Im schlimmsten Fall "unausgeglichen", wird es mehr, in der gleichen "Reihenfolge" wie sequentiell. Es ist keine lineare Reduktion, wenn der Baum ausgeglichen ist, ich denke, es ist C * (ln (2) / ln (n + 1)) oder kurz O (log (N)). Für Millionen von Datensätzen gibt es viel weniger.
%Vor%Wenn es nur ein wenig unausgewogen ist, liegt das Ergebnis irgendwo in der Mitte.
%Vor%Ich bin mir nicht sicher, ob Ihr Code optimal ist, aber wenn das Buch sagt, dass es im schlimmsten Fall doppelt so viele Operationen gibt, ist es wahrscheinlich genau. Versuchen Sie, es auf jedem Level zu 2x zu bekommen, wenn Sie aus akademischen Gründen an den Details interessiert sind.
Ich würde mir keine Sorgen um den Wert von C machen - wahrscheinlich möchten Sie nur eine BST verwenden, wenn Sie im Voraus wissen, dass es basierend auf Ihrer Einfüge- / Aktualisierungsmethode ausgeglichen oder fast ausgeglichen ist, weil O (N) wahrscheinlich sei katastrophal. Betrachte 40 * (ln (2) / ln (1.000.000.000.000.000 + 1)) gegenüber 1 * 1.000.000.000.000.
Der Punkt über die BinarySearchST vs. SequentialSearchST-Leistung im durchschnittlichen Fall wurde bereits in anderen Antworten behandelt.
Zur zweiten Frage: 2N ist für ein Array . Es ist offensichtlich wahr. Das BinarySearchST verwendet 2 Arrays, aber wenn Sie in einen anfänglich leeren Baum einfügen, erhalten Sie ~ N ^ 2 Operationen. Es liegt an einem Multiplikator. Entweder hast du 2 + 4 + 6 + ... + 2N oder 2 mal das - sowieso bekommst du ~ N ^ 2.