Pourquoi l'algorithme de programmation dynamique du problème du sac à paquet n'est-il pas polynomial? [dupliquer

Question

Cette question a déjà une réponse ici:

• Le temps d'exécution du problème de sac à dos est $ o (n cdot min (b, v)) $ et n'est pas polynomial, pourquoi? 1 réponse

L'algorithme de programmation dynamique pour le problème de sac à dos a une complexité temporelle de $ o (nw) $ où $ n $ est le nombre d'articles et $ w $ est la capacité du sac à dos.

Pourquoi n'est-ce pas un algorithme de temps polynomial?

J'ai lu qu'il a besoin de $ lg w $ bits pour représenter $ w $, donc c'est un temps exponentiel. Mais, je ne comprends pas, il a également besoin de $ lg n $ bits pour représenter $ n $, n'est-ce pas? Ainsi, par exemple, tri par fusion Le temps polynomial n'est-il pas, car sa complexité est $ o (n lg n) $ et on a besoin de $ lg n $ pour représenter $ n $?

Qu'est-ce que j'oublie ici?