多项式时间

如果对于给定的输入，完成算法所需的步骤数是 ，其中 是某个非负整数， 是输入的复杂度，则称该算法可在多项式时间内解决。多项式时间算法被认为是“快速”的。大多数常见的数学运算，如加法、减法、乘法和除法，以及计算平方根、幂和对数，都可以在多项式时间内完成。计算大多数有趣的数学常数的数字，包括 和 ，也可以在多项式时间内完成。