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

Question

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

Answer 1

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