什么是伪多项式时间算法

首先一定要搞清楚下面的定义。

输入规模：一个问题的输入规模是保存输入数据所需要的bit位数。
（不理解“伪多项式时间”，可能很大程度上是由于对“输入规模”的误解。输入规模不是指输入的大小，也不是指多少，而是指在2进制下保存它们需要的位数！）

多项式时间算法：在输入规模为x的情况下，算法能够在O(x^k) 时间(k为常数)内解决该问题。

伪多项式时间算法：算法的时间复杂度是输入数据大小的多项式时间表达，但却是输入数据长度（输入规模）的指数时间表达。

对比下面两个例子。

1. 冒泡排序：给定 n 个32位的数字，将数字从小到大排序。输入规模增长与数字大小无关，输入规模 = 32n。输入规模为x时，n = x / 32，算法用时为O((x/32)²）= O(x²）。

2. 素数判定：给定数字 n，判断 n 是否为素数。增长规模与数字大小相关，输入规模 = logn 。输入规模为x时，n = 2^x，算法用时为O(2^x）。

所以冒泡排序为多项式时间算法，素数判定则是伪多项式时间算法。

处理图论、链表、数组、树等问题时，一般是多项式时间算法；处理背包问题、与数论有关的问题时，有时就是伪多项式时间算法了。

参考资料：
什么是伪多项式时间算法？ - 詹宇的回答 - 知乎
https://www.zhihu.com/question/20013122/answer/44460397

什么是伪多项式时间算法？ - 唐燕琳的回答 - 知乎
https://www.zhihu.com/question/20013122/answer/13786174