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

题目详情

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

▼优质解答

答案和解析

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

看了我在查阅NP问题时,查到可以在...的网友还看了以下：

我正在看关于记叙文的知识,我想把它抄下来并牢记,并阅读记叙文我阅读能力超差,可很爱读文章,郁闷,怎　2020-04-27 …

如何在阅读一篇文章时形成自己的见解?是卷子上的题~1阅读一篇文章的时候,我们可以（）或（）进行独立　2020-05-17 …

我认为读书是非常重要的，因为它可以使我们增长知识，丰富我们的阅历，我认为我们可以读一些励志名言或古　2020-07-09 …

阅读材料，解答问题：我们可以利用解二元一次方程组的代入消元法解形如x2+y2=10①2x-y=5② 　2020-07-25 …

先阅读理解下面的例题，再按要求解答下列问题：例题：对于（（x-2）（x-4）>>0，这类不等式我们　2020-07-30 …

阅读材料：在学习解一元二次方程以后，对于某些不是一元二次方程的方程，我们可通过变形将其转化为一元二　2020-08-03 …

阅读《宝黛吵架》中的一段文字：别人不知我的心，还可想，难道你就不想我的心里眼里只有你？你不能为我解烦　2020-11-03 …

阅读理解：在解形如3|x-2|=|x-2|+4这一类含有绝对值的方程时，我们可以根据绝对值的意义分x 　2021-01-05 …

以“阅读”为话题写一篇不少于800字的作文。提示：可以写一段关于阅读的故事，可以写自己阅读时的领悟，　2021-02-01 …