B-Tree Revisión

Question

Si estamos buscando intersecciones de las líneas (sólo líneas horizontales y verticales) y tenemos n líneas con la mitad de ellos verticales sin intersecciones luego

Clasificar la lista de puntos de fin de línea en Y valor tomará N log N usando mergesort

Cada inserto supresión y búsqueda de nuestra structue datos (suponiendo que es un árbol B) será

lo que el tiempo total de búsqueda será N log N

¿Qué me falta aquí, si el tiempo para ordenar el uso de mergesort toma un tiempo de N log N y insertar y eliminar toma un tiempo de

Gracias

Answer 1

La notación de orden O describe el comportamiento asintótico del algoritmo. Es decir, se describe el comportamiento del algoritmo como N las tendencias hacia el infinito. La porción del algoritmo que toma N log N tiempo empequeñecerá la parte del algoritmo que toma log N tiempo. La importancia del registro de N disminuye las porciones relativamente nada como N se hace grande.

Answer 2

Sospecho que su tutor se refiere al problema de la Segmento de línea de intersección , que es más complejo que simplemente la clasificación de los segmentos. Se habrá dado cuenta de que este artículo hace referencia al algoritmo Shamos-Hoey, que utiliza un árbol binario para almacenar los segmentos de línea y eficientemente detectar las intersecciones.

Michael tiene razón en que el uso de un árbol binario tiene sentido para un único tipo de los segmentos de línea. Sin embargo, en el contexto de la detección de las intersecciones, la clasificación seguida de una búsqueda rendirá rendimiento cuadrática y no es el mejor enfoque, de ahí algoritmos de detección de línea usan árboles binarios.

Por ejemplo, supongamos que ordenar los segmentos de línea a lo largo del eje x de izquierda a derecha. Un algoritmo de detección ingenua sería entonces algo como:

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

Debido al bucle doblemente anidado el peor caso es O (n ^ 2) y se produce cuando todos los segmentos de línea se superponen en el eje x. El mejor caso es lineal y se produce cuando ninguno de los segmentos se solapan en el eje x.

Es posible que desee comenzar con la implementación del algoritmo ingenuo seguido de uno que utiliza una estructura de árbol-B.