Diferencia entre revisiones de «Problema de la suma de subconjuntos»
Contenido eliminado Contenido añadido
m modificación enlace interno |
m →Algoritmo de tiempo exponencial: corrección |
||
Línea 24:
==Algoritmo de tiempo exponencial==
Hay varias maneras de resolver la suma de subconjuntos en tiempo exponencial sobre N. El algoritmo más inocente verificaría todos los posibles subconjuntos de N
Se conoce un mejor algoritmo de tiempo exponencial, que corre en tiempo de orden ''O(2<sup>N/2</sup>N)''. El algoritmo parte los N elementos en dos conjuntos de N/2 cada uno. Para cada conjunto, calcula la suma de todos los posibles subconjuntos ''2<sup>N/2</sup>'' y los almacena en una matriz de longitud ''2<sup>N/2</sup>''. Entonces ordena estas dos matrices, lo que se puede hacer en tiempo ''O(2<sup>N/2</sup>N)''. Una vez que las matrices están ordenadas, el algoritmo puede verificar si un elemento de la primera matriz más un elemento de la segunda dan el total ''s'' buscado en tiempo ''O(2<sup>N/2</sup>)''. Para hacer esto, el algoritmo pasa por la primera matriz en orden decreciente (empezando en el elemento más grande) y por el segundo en orden creciente (empezando por el más pequeño). Cuando la suma del elemento en turno de las dos matrices es mayor que ''s'', el algoritmo se mueve al siguiente elemento en la primera matriz, cuando es menor que ''s'' se mueve al siguiente elemento en la segunda matriz. Si se encuentra ''s'' el algoritmo termina.
| |||