什么是多项式时间

Question

我在查阅NP问题时，查到可以在多项式时间内验证解是否可行的问题为NP问题。这个理解没错吧？
我现在的问题是什么是多项式时间？我不太理解这个概念。懂算法的给解释下啊，谢谢了。

Answer 1

就是问题需要的时间（复杂度）与问题的规模之间是多项式关系。
举个例子，现在从n阶图中找两点的最短路径，复杂度为n^2级别（即O(n^2)，O是大写欧），而n^2对于n是多项式（单项式当然也算），这就称为是多项式复杂度，或者多项式时间，其中问题（算法）的规模是n。如果某一个算法的规模是n，但是复杂度比如是2^n，写不成n的多项式，那就不是多项式时间。