Pourquoi le problème du sac à dos est-il pseudo-polynomial?
je sais que Knapsack est NP-complet alors qu'il peut être résolu par DP. Ils disent que la solution DP est pseudo-polynomial , puisqu'elle est exponentielle dans la" longueur d'entrée " (c.-à-d. le nombre de bits nécessaires pour encoder l'entrée). Malheureusement, je n'ai pas l'obtenir. Quelqu'un peut m'expliquer ce truc de pseudo-polynomial lentement ?
4 réponses
Le temps d'exécution est O(NW) pour une surabondance de problème de sac-à-dos avec N éléments et sac à dos de taille W. W n'est pas polynomial en la longueur de l'entrée, ce qui est ce qui le rend pseudo -polynomial.
Consider W = 1.000.000.000. Il suffit de 40 bits pour représenter ce nombre, donc la taille d'entrée = 40, mais le temps d'exécution de calcul utilise le facteur 1.000.000.000 qui est O(2 40 ).
So on dit plus précisément que l'exécution est O (N. 2 bits in W ), ce qui est exponentiel.
Voir aussi:
dans la plupart de nos problèmes, nous avons affaire à de grandes listes de nombres qui s'inscrivent confortablement à l'intérieur des types de données standard int/float. En raison de la façon dont la plupart des processeurs sont construits pour traiter des nombres de 4 à 8 octets à la fois sans coût supplémentaire (par rapport aux nombres que l'ajustement dans, disons, 1 octet), nous rencontrons rarement un changement dans le temps de fonctionnement de l'augmentation de nos nombres vers le haut ou vers le bas dans les gammes que nous rencontrons dans les problèmes réels - de sorte que le facteur dominant reste juste la quantité pure de points de données, le n ou de nombreux facteurs auxquels nous sommes habitués.
(vous pouvez imaginer que la notation Big-O cache un facteur constant qui divise-out 32 ou 64 bits-per-datum, ne laissant que le nombre-de-données-points chaque fois que chacun de nos numéros s'insèrent dans ce nombre de bits ou moins)
mais essayez de retravailler avec d'autres algorithmes pour agir sur les ensembles de données impliquant de grands ins - nombres qui nécessitent plus de 8 octets pour représenter - et voir ce que cela fait à l'exécution. L'ampleur de la les nombres impliqués font toujours une différence, même dans les autres algorithmes comme le tri binaire, une fois que vous vous étendez au-delà de la mémoire tampon des processeurs conventionnels de sécurité nous donnent "gratuitement" en manipulant des lots de 4-8 octets.
le truc avec L'algorithme de Knapsack que nous avons discuté est qu'il est inhabituellement sensible (par rapport à d'autres algorithmes ) à la magnitude d'un paramètre particulier, W. Ajouter un peu à W et vous 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, c'est pourquoi il pourrait sembler que nous traitons Knapsack différemment-mais c'est une véritable analyse de la façon dont il répond d'une manière non-polynomiale aux changements de taille d'entrée.
le temps d'exécution de L'algorithme de Knapsack est lié non seulement à la taille de l'entrée (n - Le nombre d'éléments) mais aussi à la grandeur de l'entrée (W - la capacité de knapsack) O(nW) qui est exponentielle dans la façon dont elle est représentée dans l'ordinateur en binaire (2^n) .La complexité computationnelle (I. le traitement se fait à l'intérieur d'un ordinateur par bits) ne concerne que la taille des entrées, pas leurs grandeurs/valeurs .
ne pas tenir compte de la liste des valeurs/poids pendant un moment. Disons que nous avons une instance avec knapsack capacity 2. W prendrait deux bits dans les données d'entrée. Maintenant nous allons augmenter la capacité de knapsack à 4, en gardant le reste de l'entrée. Notre contribution n'a augmenté que d'un peu, mais la complexité du calcul a doublé. 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 augmenté d'un facteur de 512. Le temps de la complexité croît exponentiellement dans la taille de W dans la représentation binaire (ou décimale).
un autre exemple simple qui m'a aidé à comprendre le concept de pseudo-polynôme est l'algorithme naïf de test de primalité. Pour un nombre donné n Nous vérifions si il est divisé également par chaque nombre entier dans la gamme 2..√n, donc l'algorithme prend √(n-1) des mesures. Mais ici, n est la grandeur de l'Entrée, pas sa taille.
Now The regular O(n) case
par contraste, la recherche d'un tableau pour un un élément donné court en temps polynomial: O (n). Il faut au plus n étapes et ici, n est la taille de l'entrée (la longueur du tableau).
[voir ici]
la façon dont je comprends cela est que la capacité aurait été O(W) si l'entrée de capacité é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 à la place un seul entier. La complexité temporelle est à propos de la relation à la taille d'entrée. Le taille d'un entier n'est PAS la valeur de l'entier, mais le nombre de bits de le représenter. Nous convertissons plus tard cet entier W en un tableau [1,2,...,W] dans l'algorithme, conduisant les gens à penser à tort W est la taille, mais ce tableau n'est pas l'entrée, l'entier lui-même est.
pense à l'entrée comme "un tableau de choses", et la taille comme "combien de choses dans le tableau". L'entrée de l'élément est en fait un tableau de N éléments dans le tableau donc taille=N. l'entrée de capacité N'est pas un tableau des nombres W en elle, mais un simple entier , représenté par un tableau de bits log(W). Augmentez la taille de celui-ci par 1 (ajoutant 1 bit significatif), w double ainsi le temps d'exécution double, d'où la complexité de temps exponentielle.