多项式时间算法 伪多项式时间算法

多项式时间算法是指在输入规模为n的情况下，算法的运行时间是一个多项式函数。也就是说，算法的运行时间可以表示为P(n)，其中P是一个多项式函数。

伪多项式时间算法是指在输入规模为n和数值范围为m的情况下，算法的运行时间是一个关于n和m的多项式函数。与多项式时间算法不同的是，伪多项式时间算法的运行时间与输入数值范围有关。

举个例子来说，对于一个求解0/1背包问题的算法，如果输入规模为n，但数值范围为m（比如背包中物品的重量和价值），那么该算法的运行时间是关于n和m的多项式函数，因此称为伪多项式时间算法。

总结来说，多项式时间算法和伪多项式时间算法都是在多项式时间内完成计算，只是伪多项式时间算法考虑了输入数值范围的影响。