• Dividimos la instancia original del problema en subproblemas de menor tamaño para facilitar la resolución del mismo.
• Los subproblemas resultantes se resuelven de forma independiente de los otros generados.
• Cada subproblema conserva todas las características del problema original. Esto permite que este mismo pueda a su vez ser subdividido en nuevos subproblemas de un menor tamaño.
• Mediante un proceso recursivo se continúa esta división hasta un caso base donde el problema tiene un tamaño lo suficientemente pequeño para su resolución de forma trivial.
• Es conocida como conquista la resolución de todos los subproblemas correspondientes a un problema. Posterior a esta se procede a un proceso de combinación de estos para generar la solución del problema general.
• Cada subproblema dependiente directamente de un problema determinado para su conquista se puede paralelizar, resolver y luego combinar.

Borrador TP1

$$ T(n)=A*T(n/B)+f(n) $$

$$ A=2, B = 2, f(n) = n $$

$$ \text{Al recurrir al teorema maestro tenemos:}\\ \text{A = 2 subproblemas por cada nivel de recursión}\\ \text{B = 2 partes iguales en las cuales dividimos al subproblema en cada nivel.}\\ \text{f(n) = n dado juntamos esas partes iguales realizando comparaciones en O(1) }\\ \text{y posteriormente agregamos los elementos restantes al arreglo a devolver}\\ \text{(con }n \text{ la cantidad de elementos en el subproblema actual).}\\

\text{Vamos a comenzar probando con el caso número dos de teorema, donde igualamos:}\\

f(n) = \Theta\left(n^{\log_B A}\right)\\

\text{Tras reemplazar con las variables de nuestro problema tenemos que:}\\

n = \Theta\left(n^{\log_2 2}\right)\\

n = \Theta\left(n^{1}\right)\\

n = \Theta\left(n\right)\\

\text{Finalmente observamos que se cumple satisfactoriamente que }f(n) = n\\ \text{ sea acotada tanto superior como inferiormente por } n\\ \text{ y por lo tanto se tiene que:}\\ T(n) = \Theta\left(n^{\log_B A} * log *n\right)\\ T(n) = \Theta\left(n^{\log_2 2} * log *n\right)\\ T(n) = \Theta\left(n * log *n\right) $$

evaluar_factibilidad(puentes_propuestos):
    merge_sort(puentes_propuestos, N asc)
    devolver _evaluar_factibilidad(propuestas_ordenadas, 0, len(propuestas_ordenadas) - 1)

_evaluar_factibilidad(puentes_propuestos, ini, fin):
    Si me queda una sola propuesta la devuelvo junto con cero cruces
    
    solucion_izq, cruzados_izq = _evaluar_factibilidad(puentes_propuestos, primera_mitad)
    solucion_der, cruzados_der = _evaluar_factibilidad(puentes_propuestos, segunda_mitad)
    
    devolver merge_puentes(solucion_izq, solucion_der, cruzados_izq + cruzados_der)

merge_puentes(solucion_izq, solucion_der, cruzados):
    i = j = 0
    resultado = []
    
    Mientras i < len(izq) y j < len(der):
        propuesta_izq = izq[i]
        propuesta_der = der[j]
        Si la propuesta izquierda termina en un barrio anterior a la derecha:
            res.resultado(propuesta_izq)
            i += 1
        Caso contrario:
            res.resultado(propuesta_der)
            cruzados += cantidad_restante_en_solucion_izq
            j += 1
    
    Agrego los restantes de solucion_izq si los hay
    Agrego los restantes de solucion_der si los hay
    
    devolver resultado, cruzados