Chr*_*her 7 algorithm big-o time-complexity
我有难以理解为什么使用动态编程的0/1背包不是多项式时间可解决的.这里也提出了类似的问题.为什么背包问题是伪多项式？.有人给出了解释,但我仍然不明白为什么我们应该考虑权重输入的二进制表示.怎么样的n,如果用二进制表示法考虑,我可以说它是对项目数量的指数吗？类似地,对于任何其他多项式时间算法,我可以声称它们具有指数时间复杂度,因为每个输入在计算机中以二进制数字表示.我知道我错了.有人可以通过简单易懂的方式指出原因吗？提前致谢.
一个非常简单的思考方式是,如果你加倍限制,输入的大小只增加一位(因为限制是输入的一部分),而运行时间加倍.这显然是关于输入大小的指数行为.
但是,虽然将项目数量加倍也会使运行时间加倍,但它也会使输入项目的大小加倍,因此输入大小和运行时间之间的部分关系只是线性的.