我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:六合报码室 > 多项式时间 >

什么叫多项式时间算法

归档日期:07-26       文本归类:多项式时间      文章编辑:爱尚语录

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  展开全部定义:若存在一个常数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-难的。

本文链接:http://barstaffuk.com/duoxiangshishijian/1059.html