Curso 2024/2025
Lo que sigue es un resumen de los pasos a realizar para encontrar la distancia entre los dos puntos más cercanos mediante Divide y Vencerás.
distanciaMinima
, antes de empezar la recursión
Recibimos n puntos en un vector, no necesariamente ordenados.
|
||||||||||||||||
puntos |
Creamos una copia del vector de puntos ordenada por X y, en caso de empate en X, por Y.
Coste temporal: O(n log n).
|
||||||||||||||||
puntosPorX |
Detectamos duplicados y terminamos si los hay.
Coste temporal: O(n).
Creamos una copia del vector de puntos ordenada por Y.
Coste temporal: O(n log n).
|
||||||||||||||||
puntosPorY |
Llamamos a la función recursiva pasándole las dos copias ordenadas.
Coste temporal: T(n) = 2 T(n/2) + O(n) = O(n log n).
Coste temporal total: O(n log n + n + n log n + n log n) = O(n log n).
Si estamos en el caso base de la recursión, terminamos (piensa cómo completar eso).
Dividimos los puntos ordenados por X entre la mitad izquierda y la mitad derecha sin perder esa ordenación.
Coste temporal: O(n).
|
|
||||||||||||||||
puntosIzquierdaPorX | puntosDerechaPorX |
Repartimos los puntos ordenados por Y entre la mitad
izquierda y la mitad derecha sin perder esa ordenación, poniendo en la
mitad izquierda y en la mitad derecha los mismos del paso B pero
ordenados por Y.
Coste temporal: O(n), piensa muy bien cómo.
|
|
||||||||||||||||
puntosIzquierdaPorY | puntosDerechaPorY |
Llamamos a la función recursiva pasándole los puntos de la mitad izquierda ordenados por X y ordenados por Y.
Coste temporal: T(n/2).
Llamamos a la función recursiva pasándole los puntos de la mitad derecha ordenados por X y ordenados por Y.
Coste temporal: T(n/2).
Creamos un vector con los puntos en la franja central ordenados por Y.
Coste temporal: O(n).
Calculamos distancias entre puntos de la franja central con criterio de parada por distancia vertical.
Coste temporal: O(n).