¿Por qué el problema de la mochila es pseudo-polinomio?

En la mayoría de nuestros problemas, estamos tratando con grandes listas de números que se ajustan cómodamente dentro de los tipos de datos int/float estándar. Debido a la forma en que la mayoría de los procesadores están diseñados para manejar números de 4-8 bytes a la vez sin costo adicional (en relación con los números que caben, digamos, 1 byte), rara vez encontramos un cambio en el tiempo de ejecución al escalar nuestros números hacia arriba o hacia abajo dentro de los rangos que encontramos en problemas reales, por lo que el factor dominante sigue siendo factores a los que estamos acostumbrados.

(Puede imaginar que la notación Big-O oculta un factor constante que divide 32 o 64 bits por dato, dejando solo el número de puntos de datos cuando cada uno de nuestros números encaja en tantos bits o menos)

Pero intente volver a trabajar con otros algoritmos para actuar sobre conjuntos de datos que involucren grandes ints - números que requieren más de 8 bytes para representar - y vea lo que eso hace al tiempo de ejecución. La magnitud de los números involucrados siempre marca la diferencia, incluso en los otros algoritmos como el tipo binario, una vez que se expande más allá del búfer de los procesadores convencionales de seguridad nos dan "gratis" al manejar lotes de 4-8 bytes.

El truco con el algoritmo de mochila que discutimos es que es inusualmente sensible (en relación con otros algoritmos ) a la magnitud de un parámetro en particular, W. Agregue un bit a W y duplica el tiempo de ejecución del algoritmo. No hemos visto ese tipo de respuesta dramática a los cambios en el valor en otros algoritmos antes de esta, por lo que podría parecer que estamos tratando a Knapsack de manera diferente, pero eso es un análisis genuino de cómo responde de una manera no polinómica a los cambios en el tamaño de entrada.

El tiempo de ejecución del algoritmo de la mochila está limitado no solo al tamaño de la entrada (n-el número de elementos) sino también a la magnitud de la entrada (W - la capacidad de la mochila) O(nW) que es exponencial en cómo se representa en la computadora en binario (2^n) .La complejidad computacional (es decir, cómo se realiza el procesamiento dentro de una computadora a través de bits) solo se refiere al tamaño de las entradas, no a sus magnitudes/valores .

Ignorar la lista de valor / peso para una momento. Digamos que tenemos una instancia con capacidad de mochila 2. W tomaría dos bits en los datos de entrada. Ahora aumentaremos la capacidad de la mochila a 4, manteniendo el resto de la entrada. Nuestra entrada solo ha crecido en un bit, pero la complejidad computacional se ha duplicado. Si aumentamos la capacidad a 1024, tendríamos solo 10 bits de la entrada para W en lugar de 2, pero la complejidad ha aumentado en un factor de 512. La complejidad del tiempo crece exponencialmente en el tamaño de W en binario (o decimal) representación.

Otro ejemplo simple que me ayudó a entender el concepto pseudo-polinomio es el algoritmo ingenuo de pruebas de primalidad. Para un número dado n estamos comprobando si se divide uniformemente por cada número entero en el rango 2..√n, por lo que el algoritmo toma pasos √(n-1). Pero aquí, n es la magnitud de la entrada, no es tamaño.

                     Now The regular O(n) case

Por el contrario, la búsqueda de un array para un elemento dado se ejecuta en tiempo polinómico: O(n). Toma a lo sumo n pasos y aquí n es el tamaño de la entrada (la longitud de la matriz).

[ ver aquí ]

Cálculo de los bits necesarios para almacenar el número decimal

La forma en que entiendo esto es que la capacidad habría sido O (W) si la entrada de capacidad fuera una matriz de [1,2,..., W] , que tiene un tamaño de W. Pero la entrada de capacidad no es una matriz de números, es en cambio un entero único. La complejidad temporal es sobre la relación con el tamaño de la entrada. El tamaño de un entero NO es el valor del entero, sino el número de bits que lo representan. Más tarde convertimos este entero W en una matriz [1,2,..., W] in el algoritmo, llevando a la gente a pensar erróneamente que W es el tamaño, pero esta matriz no es la entrada, el entero en sí es.

Piense en la entrada como "una matriz de cosas", y el tamaño como "cuántas cosas en la matriz". La entrada de elemento es en realidad una matriz de n elementos en la matriz, por lo que size = n. La entrada de capacidad NO es una matriz de números W en ella, sino un solo entero, representado por una matriz de bits log(W). Aumenta el tamaño de la misma en 1 (añadiendo 1 bit significativo), W se duplica así que el tiempo de ejecución se duplica, de ahí la complejidad de tiempo exponencial.