Nous savons que le problème du sac à dos peut être résolu en complexité O(nW) par programmation dynamique. Mais nous disons que c'est un problème NP-complet. Je pense que c'est difficile à comprendre ici.
(n est le nombre d'articles. W est le volume maximal).
O(n*W) ressemble à un temps polynomial, mais il est no c'est pseudo-polynôme .
La complexité temporelle mesure le temps que prend un algorithme en fonction de la taille de l'échantillon. longueur en bits de son entrée. La solution de programmation dynamique est en effet linéaire dans la valeur de W mais exponentielle dans la longueur de W - et c'est ce qui compte !
Plus précisément, la complexité temporelle de la solution dynamique pour la problème de sac à dos est essentiellement donnée par une boucle imbriquée :
// here goes other stuff we don't care about
for (i = 1 to n)
for (j = 0 to W)
// here goes other stuffAinsi, la complexité temporelle est clairement O(n*W) .
Que signifie augmenter linéairement la taille de l'entrée de l'algorithme ? Cela signifie qu'il faut utiliser des tableaux d'éléments de plus en plus longs (donc n , n+1 , n+2 ...) et progressivement plus longues W (donc, si W es x bits, après une étape, nous utilisons x+1 bits, alors x+2 bits, ...). Mais le valeur de W croît de manière exponentielle avec x L'algorithme n'est donc pas vraiment polynomial, il est exponentiel (mais il a l'air d'être polynomial, d'où le nom de "pseudo-polynomial").
Il y a deux façons de mesurer la taille des chiffres. Si l'on prend les nombres 10 et 1000, on peut dire que 1000 est soit deux fois plus grand (en nombre de caractères), soit cent fois plus grand. Comme la différence est exponentielle, on peut avoir un algorithme polynomial mesuré par rapport à la magnitude numérique et exponentiel mesuré par rapport au nombre de bits.
Je ne vois pas du tout en quoi le nombre de bits dans le codage a un rapport avec cette question. Je comprends que le nombre de bits joue un rôle dans la complexité de la factorisation des entiers, puisque l'entier unique est votre "entrée". Cependant, les nombres W y n représentent ici le nombre d'itérations de la boucle. Vous pouvez les coder comme vous voulez, et cette boucle va toujours itérer n * W fois. Je crois que la raison de ce "pseudo-polynôme" est que n est la taille réelle de l'entrée, et W peut être beaucoup plus grande que n et ne peut donc pas être traitée comme une constante.
@The111 : le but de l'analyse de la complexité temporelle n'est pas d'exprimer seulement le nombre d'itérations d'un algorithme, c'est d'exprimer le nombre d'itérations en tant que fonction de la taille de son entrée c'est à peu près comme cela qu'il est défini. Vous devez donc savoir ce que signifie augmenter la taille des variables d'entrée de l'algorithme que vous analysez pour étudier sa complexité temporelle.
Tout dépend des paramètres que vous mettez à l'intérieur O(...) .
Si le poids cible est limité par le nombre W alors le problème est O(n*W) la complexité, comme vous l'avez mentionné.
Mais si les poids sont beaucoup trop importants et que vous avez besoin d'un algorithme dont la complexité est indépendante de celle de l'algorithme de l'utilisateur. W alors le problème est NP-complet. ( O(2^n*n) dans l'implémentation la plus naïve).
Qu'en est-il des autres problèmes de programmation dynamique ? Par exemple, le problème de la plus longue sous-séquence commune peut être résolu en O(L_1*L_2) temps ? Peut-on dire que ce n'est pas polynomial ?
@cnhk On dirait que sa complexité est polynomiale, O(n^2). Mais il y a toutes sortes d'algorithmes DP, par exemple ceux qui travaillent sur tous les sous-ensembles d'un ensemble donné (2^n combinaisons), donc je ne dirais pas que tous les problèmes DP peuvent être résolus en temps polynomial.
Cela s'explique par le fait que le problème de sac à dos a un pseudo-polynôme et est donc appelé _faiblement NP-complet (et non fortement NP-complet_ ).
Vous pouvez lire cette courte explication : La complétude NP du Knapsack .
Pour comprendre NP-complétude il faut apprendre un peu de théorie de la complexité. Cependant, en gros, c'est NP-complet parce qu'un algorithme efficace pour le problème du sac à dos serait aussi un algorithme efficace pour le problème du sac à dos. SAT , TSP et le reste.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
0 votes
Cette réponse de Quora utilise un exemple qui montre un raisonnement très clair qui vous conduit à une contradiction et à la compréhension de ce sujet.