Pourquoi le problème du sac à dos est-il un pseudo-polynôme?

Le temps d’exécution est O (NW) pour un problème de sac à dos sans limite avec N éléments et sac à dos de taille W. W n’est pas polynomial dans la longueur de l’entrée cependant, ce qui le rend pseudo- polynomial.

Considérez W = 1 000 000 000 000. Il ne faut que 40 bits pour représenter ce nombre, donc la taille d’entrée est 40, mais le temps d’exécution computationnel utilise le facteur 1 000 000 000 000 qui est O (2 ⁴⁰ ).

Ainsi, le temps d’exécution est plus précisément appelé O (N.2 ^{bits dans W} ), ce qui est exponentiel.

Regarde aussi:

• Comment comprendre le problème du sac à dos est NP-complet?
• La complétude NP du sac à dos
• Complexité de l’algorithme de programmation dynamic pour le problème du sac à dos 0-1
• Temps pseudo-polynomial

Dans la plupart de nos problèmes, nous traitons de grandes listes de nombres qui s’insèrent facilement dans les types de données standard int / float. En raison de la façon dont la plupart des processeurs sont conçus pour gérer des nombres de 4 à 8 octets à la fois sans coût supplémentaire (par rapport aux nombres, disons, 1 octet), nous ne rencontrons que rarement dans les fourchettes que nous rencontrons dans des problèmes réels – le facteur dominant rest donc la quantité de points de données, les n ou m facteurs auxquels nous sums habitués.

(Vous pouvez imaginer que la notation Big-O cache un facteur constant qui divise 32 ou 64 bits par donnée, ne laissant que le nombre de points de données à chaque fois que chacun de nos nombres correspond à autant de bits ou moins )

Mais essayez de retravailler avec d’autres algorithmes pour agir sur des ensembles de données impliquant de gros chiffres – des nombres nécessitant plus de 8 octets à représenter – et de voir ce que cela fait pour le moteur d’exécution. L’ampleur des nombres impliqués fait toujours une différence, même dans les autres algorithmes tels que le sorting binary, une fois que vous étendez au-delà de la mémoire tampon de sécurité, les processeurs conventionnels nous libèrent en manipulant des lots de 4 à 8 octets.

Le truc avec l’algorithme de Knapsack dont nous avons parlé est qu’il est exceptionnellement sensible (par rapport à d’autres algorithmes) à la magnitude d’un paramètre particulier, W. Ajoutez un bit à W et doublez le temps d’exécution de l’algorithme. Nous n’avons pas vu ce genre de réponse dramatique aux changements de valeur dans d’autres algorithmes avant celui-ci, ce qui explique pourquoi nous considérons que nous traitons différemment Knapsack – mais c’est une véritable parsing de la façon dont il répond de manière non polynomiale aux changements de taille de saisie.

Le temps d’exécution de l’algorithme Knapsack est lié non seulement à la taille de l’entrée (n – le nombre d’éléments) mais également à la magnitude de l’entrée (W – la capacité du sac à dos) O (nW) qui est exponentielle représenté en informatique en binary (2 ^ n). La complexité du calcul (c’est-à-dire la manière dont le traitement est effectué à l’intérieur d’un ordinateur par les bits) ne concerne que la taille des entrées et non leur magnitude / valeur .

Ne tenez pas compte de la liste valeur / poids pendant un moment. Disons que nous avons une instance avec une capacité de sac à dos 2. W prendrait deux bits dans les données d’entrée. Maintenant, nous allons augmenter la capacité de sac à dos à 4, en gardant le rest de l’entrée. Notre entrée n’a augmenté que d’un bit, mais la complexité de calcul a été multipliée par deux. Si nous augmentons la capacité à 1024, nous aurions seulement 10 bits de l’entrée pour W au lieu de 2, mais la complexité a été multipliée par 512. La complexité du temps augmente de façon exponentielle dans la taille de W en représentation binary (ou décimale) .

Un autre exemple simple qui m’a aidé à comprendre le concept de pseudo-polynôme est l’algorithme de test de primalité naïf. Pour un nombre donné n, nous vérifions s’il est divisé de manière égale par chaque nombre entier dans la plage 2..√n, donc l’algorithme prend √ (n-1) pas. Mais ici, n est l’ampleur de l’entrée, pas sa taille.

  Now The regular O(n) case 

En revanche, la recherche d’un tableau pour un élément donné s’exécute en temps polynomial: O (n). Cela prend au plus n étapes et n est la taille de l’entrée (la longueur du tableau).

[ vois ici ]

Calcul des bits requirejs pour stocker le nombre décimal

La façon dont je comprends cela est que la capacité aurait été O (W) si la capacité d’entrée était un tableau de [1,2, …, W] , qui a une taille de W. Mais l’entrée de capacité n’est pas un tableau de nombres, c’est plutôt un entier unique. La complexité du temps concerne la relation à la taille de l’entrée. La taille d’un entier n’est pas la valeur de l’entier, mais le nombre de bits le représentant. Nous convertissons ultérieurement cet entier W en un tableau [1,2, …, W] dans l’algorithme, ce qui amène les gens à penser à tort que W est la taille, mais ce tableau n’est pas l’entrée, l’entier lui-même est.

Considérez l’entrée comme “un tableau de choses”, et la taille comme “combien de choses dans le tableau”. L’entrée d’élément est en réalité un tableau de n éléments dans le tableau, donc size = n. L’entrée de capacité n’est PAS un tableau de nombres W , mais un entier unique , représenté par un tableau de bits de journal (W). Augmentez sa taille de 1 (en ajoutant 1 bit significatif), W double pour que le temps d’exécution double, d’où la complexité temporelle exponentielle.