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)，使得算法在 size 中呈指数时间输入。 O() 符号通常与输入大小有关，而不是值，因此不能将伪多项式算法视为多项式时间。

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