4.1 Definición de memoización y sus conceptos principales
Memoización es una técnica de optimización que consiste en guardar los resultados de funciones costosas para poder reutilizarlos en invocaciones posteriores con los mismos argumentos. Esto reduce la cantidad de recalculaciones, incrementando así el rendimiento.
Conceptos principales:
1. Caché:
Almacenar los resultados de una función en alguna estructura de datos (por ejemplo, un diccionario o una lista) para devolver el mismo resultado cuando se llama de nuevo con los mismos argumentos, en lugar de recalcularlo.
2. Tabla de búsqueda (Lookup Table):
Una estructura de datos utilizada para almacenar los resultados de llamadas previas a la función. Puede ser una hash table (diccionario) o una lista.
3. Llamadas recursivas:
La memoización es especialmente útil para funciones recursivas, donde las mismas sub-tareas pueden ejecutarse varias veces con los mismos parámetros.
Complejidad temporal y espacial de algoritmos optimizados:
Complejidad temporal:
Para muchos problemas recursivos, la memoización reduce la complejidad temporal al
disminuir la cantidad de recalculaciones. Por ejemplo, el cálculo recursivo
de números de Fibonacci tiene una complejidad temporal de O(2^n), y con memoización es O(n).
Complejidad espacial:
La complejidad espacial aumenta debido al almacenamiento de resultados en el caché.
Usualmente es O(n) para un problema que requiere memoización.
Resumen:
La memoización es una técnica potente para la optimización de algoritmos recursivos, permitiendo mejorar significativamente su rendimiento al reducir la cantidad de recalculaciones.
Es especialmente útil para problemas donde las mismas sub-tareas se ejecutan repetidamente con los mismos parámetros. Comprender los conceptos de memoización y su aplicación práctica permite
resolver eficientemente problemas con alta carga computacional.
4.2 Ejemplos de optimización
Ejemplos de optimización de algoritmos recursivos utilizando memoización
Ejemplo 1: Números de Fibonacci
El algoritmo recursivo para calcular los números de Fibonacci sin memoización tiene una complejidad temporal exponencial. Usar memoización mejora significativamente el rendimiento.
def fibonacci(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]
# Ejemplo de uso:
print(fibonacci(10)) # Salida: 55
¡Importante! Ten en cuenta que usamos
memo=None como valor por defecto y luego creamos un
diccionario vacío dentro de la función si memo no se pasa. Esto
permite evitar problemas con un objeto mutable como valor por defecto.
Ejemplo 2: Suma de subconjuntos
Necesitas determinar si existe un subconjunto dado de un conjunto, cuya suma de elementos sea igual a un valor dado.
def is_subset_sum(arr, n, sum_value, memo=None):
if memo is None:
memo = {}
if (n, sum_value) in memo:
return memo[(n, sum_value)]
if sum_value == 0:
return True
if n == 0 and sum_value != 0:
return False
if arr[n - 1] > sum_value:
memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo)
return memo[(n, sum_value)]
memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo) or is_subset_sum(arr, n - 1, sum_value - arr[n - 1], memo)
return memo[(n, sum_value)]
# Ejemplo de uso:
arr = [3, 34, 4, 12, 5, 2]
sum_value = 9
n = len(arr)
print(is_subset_sum(arr, n, sum_value)) # Salida: True
La memoización es básicamente el almacenamiento en caché de los resultados de las sub-tareas.
Por ejemplo, el número de Fibonacci F(10) == F(9) + F(8), pero para
calcular F(9), necesitas calcular F(8) y F(7). Es decir,
F(8) se tiene que calcular dos veces: como primer término para F(9) y como
segundo término para F(10). Para evitar calcularlo dos veces, necesitas almacenarlo en caché
después del primer cálculo.
GO TO FULL VERSION