B-Tree Révision

Question

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

tri de la liste des points d'extrémité de la ligne sur la valeur y sera prendre la N log N en utilisant mergesort

Chaque insert supprimer et la recherche de notre structue de données (son hypothèse d'un b-arbre) sera < log n

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

Qu'est-ce que je manque ici, si t Le temps pour trier en utilisant mergesort prend un temps de N log N et insérer et supprimer prend un temps de < log n abandons-nous le facteur constant pour donner un temps total de N log N. Si non alors comment ça se passe < log n va de pair au total ONotation temps de fonctionnement?

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 va éclipser la partie de l'algorithme qui prend le journal N temps. La signification de la partie log N diminue à relativement rien car N devient grand.

Answer 2

Je suppose que votre tuteur fait référence au problème de Line Segment Intersection, qui est plus complexe que de simplement trier les segments. Vous remarquerez que cet article fait référence à l'algorithme de Shamos-Hoey, qui utilise un arbre binaire pour stocker les segments de ligne et détecter efficacement les intersections.

Michael a raison de dire que l'utilisation d'un arbre binaire est inutile pour un tri ponctuel des segments de ligne. Cependant, dans le contexte de la détection d'intersections, le tri suivi d'une recherche donnera des performances quadratiques et n'est pas la meilleure approche, d'où la raison pour laquelle les algorithmes de détection de ligne utilisent des arbres binaires. Par exemple, supposons que vous triez vos segments de droite le long de l'axe des x de gauche à droite. Par exemple, supposons que vous triez vos segments de ligne le long de l'axe des x. 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 ne se chevauchent sur l'axe des x.

Vous pouvez commencer par implémenter l'algorithme naïf suivi de celui qui utilise une structure B-tree.