Un conjunto dado de longitud N tendrá 2 ^ N subconjuntos. Entonces, la complejidad mínima (simplemente para enumerar todos los subconjuntos) es O (2 ^ N).
Cuando enumere todos los conjuntos en orden creciente de longitud del conjunto, encontrará que los conjuntos más grandes (digamos la longitud 4) se forman eligiendo uno de los conjuntos más pequeños (longitud 3) y agregando un elemento que aún no está en el conjunto.
Entonces, si está almacenando la suma de elementos en un conjunto más pequeño, simplemente tiene que agregarle el nuevo número para obtener la suma del conjunto más grande. (p. ej. suma de {1,2} = 3, suma de {1,2,4} = 3 + 4 = 7)
- ¿Cuál es el mejor recurso para aprender el algoritmo KMP?
- Cómo resolver este problema de matriz (detalles en la descripción)
- Es un método de retroceso para imprimir permutaciones de cadena. No entiendo de qué manera se produce el flujo de control, como después de encontrar el intercambio, el intercambio se llama luego permutar y luego nuevamente. ¿Esto no se me viene a la cabeza?
- ¿Cómo saben los codificadores cómo codificar e implementar un algoritmo instintivamente?
- ¿Cuáles son algunos programas / algoritmos recursivos interesantes (como la Torre de Hanoi y N-Queens)?
Esto evitaría iterar sobre todos los elementos para cada subconjunto para calcular la suma (que será aproximadamente O (N * 2 ^ N), en realidad menor, ya que no todos los subconjuntos son de longitud N. Sería realmente suma (i * 2 ^ i ) para i = 0 a N).
Entonces, al almacenar todas las sumas de subconjuntos, su algoritmo permanecerá O (2 ^ N) ya que cada vez que agrega un número constante y no itera. Pero necesitará memoria adicional de O (2 ^ N)
