Polynomial time意思

"Polynomial time" is a term used in computer science and complexity theory to describe an algorithm's efficiency. It refers to the fact that the amount of time an algorithm takes to run (its running time) is proportional to a polynomial function of the size of the input.

More specifically, if an algorithm's running time can be expressed as O(n^k), where n is the size of the input and k is a constant, then the algorithm is said to run in polynomial time. Here, n^k is a polynomial, and the degree of this polynomial is k.

For example, if an algorithm's running time is O(n^2), it means that the time it takes to run the algorithm is proportional to the square of the input size. This is considered polynomial time because the input size is raised to a fixed, non-zero power.

Polynomial-time algorithms are highly desirable because they can handle inputs of any size, provided that the input size is finite. They are generally considered to be efficient, and many problems in computer science can be solved using polynomial-time algorithms.

However, not all problems can be solved by polynomial-time algorithms. Some problems are known to require an exponential amount of time to solve, even with the most efficient algorithms. These problems are said to be NP-hard, and they are considered to be intractable for large input sizes.