Tratando de entender la complejidad temporal de esta suma de subconjuntos recursiva dinámica.
Devuelve verdadero si existe una subsecuencia de A[0…n] con la suma dada
def subsetSum(A, n, k, lookup):
# devuelve verdadero si la suma se vuelve 0 (se encuentra una subsecuencia)
if k == 0:
return True
# caso base: no quedan elementos o la suma se vuelve negativa
if n < 0 or k < 0:
return False
# construye una llave única a partir de elementos dinámicos de la entrada
key = (n, k)
# si el subproblema se ve por primera vez, resuélvelo y
# almacenar su resultado en un diccionario
if key not in lookup:
# Caso 1. Incluye el elemento actual 'A[n]' en la subsecuencia y llama recursivamente
# por los otros elementos 'n-1' con el total disminuido en 'k-A[n]'
include = subsetSum(A, n - 1, k - A[n], lookup)
# Caso 2. Excluye el elemento actual 'A[n]' de la subsecuencia y llama recursivamente por
# los otros elementos 'n-1'
exclude = subsetSum(A, n - 1, k, lookup)
# asigna verdadero si obtenemos una subsecuencia incluyendo o excluyendo el elemento actual
lookup[key] = include or exclude
# devuelve la solución al subproblema actual
return lookup[key]
if name == ”main‘:
# Entrada: un conjunto de elementos y una suma
A = [7, 3, 2, 5, 8]
k = 14
# crear un diccionario para almacenar soluciones a subproblemas
lookup = {}
if subsetSum(A, len(A) - 1, k, lookup):
print('Existe una subsecuencia con la suma dada')
else:
print('No existe una subsecuencia con la suma dada')
Se dice que la complejidad de este algoritmo es O (n * sum), pero no puedo entender cómo o por qué;
¿alguien puede ayudarme? Puede ser una explicación detallada o una relación de recurrencia, cualquier cosa está bien
davy.ai
La complejidad temporal del algoritmo de suma de subconjuntos es O(n * sum), donde n es el número de elementos en el arreglo de entrada y sum es la suma objetivo que estamos tratando de alcanzar. Esta complejidad temporal se deriva del hecho de que el algoritmo resuelve todos los subproblemas posibles que se pueden construir a partir del arreglo de entrada.
Para comprender cómo es O(n * sum), consideremos los dos casos principales en el algoritmo:
a. Si n es negativo (es decir, hemos agotado todos los elementos en el arreglo de entrada), entonces devolvemos Falso.
b. Si la suma objetivo se vuelve negativa (es decir, nos hemos pasado de la suma objetivo), entonces devolvemos Falso.
Ahora necesitamos considerar los casos recursivos. El algoritmo hace lo siguiente:
Para cada subproblema, tenemos dos opciones:
Si consideramos todos los subconjuntos posibles del arreglo de entrada, entonces podemos construir 2^n subproblemas (ya que cada elemento en el arreglo de entrada puede ser incluido o excluido del subconjunto). Sin embargo, a medida que resolvemos cada subproblema, estamos almacenando el resultado en el diccionario de búsqueda. Esto significa que podemos evitar resolver el mismo subproblema varias veces. En otras palabras, si encontramos un subproblema que hemos visto antes (es decir, la clave existe en el diccionario de búsqueda), entonces podemos devolver la solución de inmediato.
Por lo tanto, dado que el algoritmo resuelve todos los subproblemas posibles que se pueden construir a partir del arreglo de entrada, y cada subproblema se puede resolver con tiempo O(1), la complejidad temporal es O(n * sum).
En resumen, la complejidad temporal del algoritmo de suma de subconjuntos es O(n * sum) porque construye todos los subproblemas posibles que se pueden construir a partir del arreglo de entrada, y cada subproblema se puede resolver con tiempo constante.