Perché l'algoritmo di programmazione dinamica del problema dello zaino non è polinomio? [duplicare

Question

Questa domanda ha già una risposta qui:

• Il tempo di esecuzione del problema dello zaino è $ O (n CDOT min (B, V) $ e non è polinomiale, perché? 1 risposta

L'algoritmo di programmazione dinamica per il Problema dello zaino Ha una complessità temporale di $ O (NW) $ dove $ n $ è il numero di articoli e $ w $ è la capacità dello zaino.

Perché questo non è un algoritmo a tempo polinomiale?

Ho letto che uno ha bisogno di $ lg w $ bit per rappresentare $ w $, quindi è tempo esponenziale. Ma, non capisco, uno ha anche bisogno di $ lg n $ bit per rappresentare $ n $, no? Quindi, per esempio, unisci il tipo Non è il tempo polinomiale, perché la sua complessità è $ O (n lg n) $ e uno ha bisogno di $ lg n $ per rappresentare $ n $?

Cosa mi manca qui?