Publicado · en mejora
Algorithm
Divide y vencerás parte un problema en subproblemas menores, los resuelve recursivamente y combina los resultados, como en merge sort o quickselect.
Divide y vencerás es una técnica de diseño de algoritmos: se parte un problema en instancias más pequeñas del mismo problema (dividir), se resuelven de forma recursiva (vencer) y con sus resultados se construye la respuesta final (combinar). Merge sort, la búsqueda binaria, la exponenciación rápida, quickselect, la multiplicación de Karatsuba y el par de puntos más cercano siguen este esquema.
Es importante porque a menudo convierte una solución de fuerza bruta O(n^2) en O(n log n) o incluso O(log n). La idea clave de calcular en el paso de combinación la información que cruza la división, como al contar inversiones, aparece una y otra vez en las entrevistas de programación, y las mismas ideas están detrás de las bibliotecas de ordenación, la multiplicación de números grandes, la FFT y la exponenciación modular en criptografía.
Empieza siguiendo merge sort a mano para interiorizar dividir, vencer y combinar; después practica cómo plantear recurrencias como T(n) = aT(n/b) + f(n) y resolverlas con el teorema maestro. Luego implementa tú mismo el conteo de inversiones, la exponenciación rápida y quickselect, y aprende a reconocer cuándo los subproblemas superpuestos requieren programación dinámica.
Dividir la entrada, resolver las partes de forma recursiva y combinar las respuestas. Un caso base detiene la recursión y el coste de combinar suele decidir el tiempo de ejecución.
El tiempo se expresa como T(n) = aT(n/b) + f(n); comparar f(n) con n^(log_b a) da resultados como O(n log n) para merge sort.
Resolver en tiempo lineal los casos que abarcan ambas mitades, como al contar inversiones o en el subarreglo máximo, es la idea central.
Si solo queda un subproblema, como en la búsqueda binaria, la exponenciación rápida y quickselect, se obtienen algoritmos O(log n) u O(n) esperado.
sort_count ordena la lista con merge sort y, cada vez que se toma primero un elemento de la mitad derecha, suma cuántos elementos esperan aún a la izquierda; así cuenta las inversiones en O(n log n). power es la exponenciación rápida: divide el exponente a la mitad y eleva al cuadrado, por lo que solo necesita O(log e) multiplicaciones. Al ejecutar python divide_and_conquer.py se imprime la lista ordenada con sus 14 inversiones y 3^200 módulo 1.000.000.007.
divide_and_conquer.py
def sort_count(a):
"""Return (sorted list, number of inversions) using merge sort."""
if len(a) <= 1:
return list(a), 0
mid = len(a) // 2
left, x = sort_count(a[:mid])
right, y = sort_count(a[mid:])
merged, i, j, cross = [], 0, 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
cross += len(left) - i # right[j] is smaller than every left[i:]
merged += left[i:] + right[j:]
return merged, x + y + cross
def power(base, exp, mod):
"""base ** exp % mod with O(log exp) multiplications."""
if exp == 0:
return 1 % mod
half = power(base, exp // 2, mod)
result = half * half % mod
return result * base % mod if exp % 2 else result
if __name__ == "__main__":
print(sort_count([5, 2, 4, 7, 1, 3, 2, 6])) # ([1, 2, 2, 3, 4, 5, 6, 7], 14)
print(power(3, 200, 1_000_000_007)) # 136318165
python divide_and_conquer.pySeis capítulos que te llevan desde la instalación hasta las ideas clave de Divide y vencerás.
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Divide y vencerás.
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.