Diferencia entre revisiones de «Problema de la suma de subconjuntos»
Contenido eliminado Contenido añadido
m robot Añadido: simple:Subset sum problem |
→Algoritmo de tiempo exponencial: naive aquí no es inocente sino simplista |
||
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
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 elementos cada uno. Para cada conjunto, calcula la suma de todos los ''2<sup>N/2</sup>'' posibles subconjuntos y las almacena en un vector de longitud ''2<sup>N/2</sup>''. Entonces ordena estos dos vectores, lo que se puede hacer en tiempo ''O(2<sup>N/2</sup>N)''. Una vez que los vectores están ordenados, el algoritmo puede verificar si un elemento del primer vector más un elemento del segundo dan el total ''s'' buscado en tiempo ''O(2<sup>N/2</sup>)''. Para hacer esto, el algoritmo pasa por el primer vector 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 los dos vectores es mayor que ''s'', el algoritmo se mueve al siguiente elemento en el primer vector, cuando es menor que ''s'' se mueve al siguiente elemento en el segundo vector. Si se encuentra ''s'' el algoritmo termina.
| |||