B-Tree Révision

Question

Si nous recherchons des intersections de lignes (lignes horizontales et verticales uniquement) et nous avons n lignes avec la moitié verticale et aucune intersection puis

Le tri de la liste des points de fin de ligne sur la valeur y prendra N log N en utilisant mergesort

Chaque insert supprimer et recherche de notre structue de données (en supposant son b-arbre) sera

de sorte que le temps de recherche total sera N log N

Qu'est-ce que je suis absent ici, si le temps de trier en utilisant mergesort prend un temps de N log N et insérer et supprimer prend un temps de

Merci

Answer 1

La notation grand-O décrit le comportement asymptotique de l'algorithme. Autrement dit, il décrit le comportement de l'algorithme comme N tendances vers l'infini. La partie de l'algorithme qui prend N log N temps éclipsera la partie de l'algorithme qui prend journal N temps. L'importance du journal N partie diminue à rien relativement comme N devient grand.

Answer 2

Je soupçonne que votre tuteur fait référence au problème de intersection de segment de ligne , qui est plus complexe que la simple tri des segments. Vous remarquerez que cet article fait référence l'algorithme Shamos-Hoey, qui utilise un arbre binaire pour stocker les segments de ligne et de détecter efficacement les intersections.

Michael est correct que l'utilisation d'un arbre binaire est inutile pour une sorte unique des segments de ligne. Cependant, dans le contexte de la détection des intersections, le tri suivi d'une recherche donnera des performances du second degré et n'est pas la meilleure approche, donc pourquoi les algorithmes de détection de ligne utilisent des arbres binaires.

Par exemple, supposons que vous triez vos segments de ligne le long de l'axe x de gauche à droite. Un algorithme de détection naïf serait alors quelque chose comme:

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;
     }
  }
}

En raison de la boucle imbriquée doublement le pire des cas est O (n ^ 2) et se produit lorsque tous les segments de ligne se chevauchent sur l'axe des x. Le meilleur cas est linéaire et se produit lorsque aucun des segments se chevauchent sur l'axe des x.

Vous voudrez peut-être commencer par la mise en œuvre de l'algorithme naïf suivi par celui qui utilise une structure B-tree.