什么是多项式时间-酷问二

什么是多项式时间

的有关信息介绍如下：

什么是多项式时间

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