生活资讯
多项式时间 、多项式时间算法
2023-04-19 01:02  浏览:34

什么叫多项式时间算法

定义:若存在一个常数C,使得对于所有n=0,都有|f(n)|

=

C*|g(n)|,则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法,这里p(n)是关于n的多项式。不能够这样限制时间复杂度的算法被称为指数时间算法。

例如:时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法,时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指时间算法。

一个优化问题如果已经找到了多项式时间算法,则称该问题为多项式时间可解问题,并将这类问题的集合记为P,因此多项式时间可解问题就称为P类问题。

一个问题如果没有找到多项式时间算法,那么直觉上它是“难解”的,但又往往无法证明多项式时间算法的不存在性。由于在寻找有效算法上的失败未必一定意味着这样的算法不存在,这就给理论工作者带来了一个难题:一方面证明一个问题不存在多项式时间算法是困难的,至今尚未给出;另一方面有越来越多的问题无法给出多项式时间算法。同时,理论工作者又渴望解决此难题。为此,在20世纪70年代提供了一个漂亮的理论,它把这种失败归结为一个深刻的数据猜想,这个理论就是NP-完全性理论。

定义:给定一个判定问题,如果存在一个算法,对任何一个答案为“是”的实例I。该算法首先给出一个猜想,该猜想规模不超过I的输入长度的某个多项式函数,且验证猜想的正确性仅需多项式时间,则称该问题属于NP类。

定义:如果NP类中所有问题都可以多项式时间归约到NP类中某个问题x,则称x是NP-完全问题。

定义:如果某优化问题x的判定问题是NP-完全的,则称问题x是NP-难的;如果x的判定问题是强NP-完全的,则称x是强NP-难的。

什么是多项式时间

就是问题需要的时间(复杂度)与问题的规模之间是多项式关系。

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

(急)多项式时间内算法 看论文上写算法复杂度控制在多项式时间内,什么叫多项式时间

多项式时间就是指时间复杂度是个多项式

或者说,就是这个程序运行的时间随着数据规模n变化的函数为

f(n)

那么,f(n)是个多项式函数,那么就可以说是控制在多项式之内.

多项式时间的介绍就聊到这里吧,感谢你花时间阅读本站内容,更多关于多项式时间算法、多项式时间的信息别忘了在本站进行查找喔。

发表评论
0评