伪多项式算法

什么是伪多项式算法？ 伪多项式算法是一种算法，其最坏情况下的时间复杂度是输入数值（而不是输入数量）的多项式。 例如，考虑计数正数数组中所有元素的频率的问题。一个伪多项式时间的解决方案是首先找到最大值，然后从1迭代到最大值，对于每个值，找到其在数组中的频率。根据输入数组中的最大值，该解决方案需要时间，因此需要伪多项式。另一方面，将时间复杂度为数组中元素数的多项式（非数值）的算法视为多项式时间算法。

伪多项式与NP完全性 一些NP完全问题有伪多项式时间解。例如，问题的动态规划解决方案 0-1背包 , 子集和 和 隔断 问题是伪多项式。可以用伪多项式时间算法求解的NP完全问题称为弱NP完全问题。

参考： https://en.wikipedia.org/wiki/Pseudo-polynomial_time

StackOverflow–什么是伪多项式时间？它与多项式时间有何不同？（最上面的答案）

本文由 德埃拉吉·古普塔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论