algorithm - 背包伪多项式时间算法

Question

我正在学习背包（0/1）问题。该解决方案的运行时间为 NW，其中 N 是物品数量，W 是允许携带的总重量。

那么为什么将解决方案称为伪多项式时间算法？

我从（ http://www.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/20/Small20.pdf）读到一个论点

该解决方案讨论了写出输入 W 所需的位 写出这些位 (log W) 所需的位如何？

Answer 1

该算法的输入值是多项式的。但是，以普通方式（例如以 2 为底）表示的数字的存储大小是log(number)，使得算法在输入大小上呈指数级增长。O() 表示法通常与输入大小有关，而不是值，因此不能将伪多项式算法视为多项式时间。

这很重要，因为您可以只为算法提供两个 1KB 的数字，并且需要数千年才能完成。相比之下，真正的多项式时间算法将根据其输入的物理大小进行多项式缩放：例如，计算机可以在几毫秒内将 1KB 的数字相乘。