多項式時間

如果對於給定的輸入，完成演算法所需的步驟數是 ，其中 是某個非負整數， 是輸入的複雜度，則稱該演算法可在多項式時間內解決。多項式時間演算法被認為是“快速”的。大多數常見的數學運算，如加法、減法、乘法和除法，以及計算平方根、冪和對數，都可以在多項式時間內完成。計算大多數有趣的數學常數的數字，包括 和 ，也可以在多項式時間內完成。