在学习算法和数据结构考试时，我偶然发现了一个问题，如果算法具有伪多项式时间效率(分析)，这意味着什么
找了很多地方却一无所获
最佳答案
这意味着该算法是关于输入大小的多项式，但输入实际上呈指数增长。
以子集和问题为例。我们有一组 S，包含 n 个整数，我们想找到一个总和为 t 的子集。
要解决这个问题，您可以只检查每个子集的总和，所以它是 O(P)，其中 P 是子集的数量。但实际上子集的数量是2^n，所以算法具有指数复杂度。
我希望这个介绍有助于理解维基百科关于它的文章http://en.wikipedia.org/wiki/Pseudo-polynomial_time :)
关于performance - 算法的伪多项式分析，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21244831/