Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2023/2024

Ayuda del ejercicio 6.b del tema 5.2

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.

En la función distanciaMinima, antes de empezar la recursión

  1. Recibimos n puntos en un vector, no necesariamente ordenados.

    1510251020101515
    1012392785
    puntos
  2. 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).

    1010101515152025
    7912581023
    puntosPorX
  3. Detectamos duplicados y terminamos si los hay.
    Coste temporal: O(n).

  4. Creamos una copia del vector de puntos ordenada por Y.
    Coste temporal: O(n log n).

    2025151015101510
    2357891012
    puntosPorY
  5. 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).

En la función recursiva

  1. Si estamos en el caso base de la recursión, terminamos (piensa cómo completar eso).

  2. Dividimos los puntos ordenados por X entre la mitad izquierda y la mitad derecha sin perder esa ordenación.
    Coste temporal: O(n).

    10101015
    79125
    15152025
    81023
    puntosIzquierdaPorX puntosDerechaPorX
  3. 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.

    15101010
    57912
    20251515
    23810
    puntosIzquierdaPorY puntosDerechaPorY
  4. 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).

  5. 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).

  6. Creamos un vector con los puntos en la franja central ordenados por Y.
    Coste temporal: O(n).

  7. Calculamos distancias entre puntos de la franja central con criterio de parada por distancia vertical.
    Coste temporal: O(n).