B-Baum-Revision

Question

Wenn wir suchen Linie Kreuzungen (horizontale und vertikale Linien nur), und wir haben n Zeilen mit der Hälfte von ihnen senkrechter und keine Kreuzungen dann

Die Sortierung der Liste der Linienendpunkte auf y-Wert nehmen N log N mit mergesort

Jeder Einsatz löschen und die Suche unserer Daten structue (es ist ein B-Baum unter der Annahme) wird

so die gesamte Suchzeit wird N log N

Was bin ich hier fehlt, wenn die Zeit mit mergesort zu sortieren eine Zeit von N log N nimmt und Einfügen und Löschen dauert eine Zeit von

Danke

Answer 1

Die Big-O-Notation beschreibt das asymptotische Verhalten des Algorithmus. Das heißt, es beschreibt das Verhalten des Algorithmus als N Trends in Richtung Unendlichkeit. Der Teil des Algorithmus, der N log N Zeit, um den Teil des Algorithmus wird Zwerg nimmt das Protokoll nimmt N Zeit. Die Bedeutung des log N Teil abnimmt relativ nichts als N groß wird.

Answer 2

Ich vermute, dass Ihr Tutor für das Problem bezieht sich auf von Liniensegment Überschneidung , das ist komplexer als einfach die Segmente sortieren. Sie werden bemerken, dass dieser Artikel verweist die Shamos-Hoey-Algorithmus, der einen binären Baum der Liniensegmente zu speichern, verwendet und effizient Kreuzungen erkennen.

ist Michael richtig, dass ein binären Baum verwendet, ist sinnlos für eine einmalige Art der Liniensegmente. Doch im Zusammenhang Schnittpunkte zu erfassen, durch eine Suche gefolgt Sortierung quadratische Leistung ergeben wird und ist nicht der beste Ansatz, also warum Linienerkennungsalgorithmen verwenden Binärbäumen.

Zum Beispiel: Angenommen, Sie sortieren Sie Ihre Liniensegmente entlang der x-Achse von links nach rechts. Ein naiver Erkennungsalgorithmus wäre dann so etwas wie:

for (int i=0; i<segs.length - 1; ++i) {
  boolean searching = true;

  for (int j=i+1; j<segs.length && searching; ++j) {
     if (segments overlap on x-axis) {
       // Check for intersection.
     } else {
       // No overlap so terminate inner loop early.
       // This is the advantage of having a sorted list.
       searching = false;
     }
  }
}

Aufgrund der doppelt verschachtelten Schleife ist der schlimmste Fall O (n ^ 2) und tritt auf, wenn alle Liniensegmente auf der x-Achse überlappen. Der beste Fall ist linear und tritt auf, wenn keines der Segmente auf der x-Achse überlappt.

Sie können anschließend den naiven Algorithmus gestartet werden soll, indem man durch die Implementierung, die eine B-Baumstruktur verwendet wird.