精华内容
下载资源
问答
  • 多项式时间复杂度指的是解决问题需要的时间与问题的规模之间是多项式关系。 多项式关系形如,k为某个常数,n是问题的输入规模(例如n个未知数)。例如,时间复杂度为O(nlog(n))、O(n3)O(nlog(n))、O(n^3)O(nlog(n))、...

    多项式时间复杂度指的是解决问题需要的时间与问题的规模之间是多项式关系。

    多项式关系形如,k为某个常数,n是问题的输入规模(例如n个未知数)。例如,时间复杂度为 O ( n l o g ( n ) ) 、 O ( n 3 ) O(nlog(n))、O(n^3) O(n

    展开全文
  • 1.多项式时间复杂度 定义: 解决问题需要的时间与问题的规模之间是多项式关系。 多项式关系形如O(n^k)O(n^k),k为某个常数,n是问题的输入规模。例如,时间复杂度为O(nlog(n))、O(n^3)都是多项式时间复杂度。...

    https://blog.csdn.net/K346K346/article/details/51026006

    1.多项式时间复杂度

    定义: 解决问题需要的时间与问题的规模之间是多项式关系。

    多项式关系形如O(n^k)O(n^k),k为某个常数,n是问题的输入规模。例如,时间复杂度为O(nlog(n))、O(n^3)都是多项式时间复杂度。时间复杂度为O(n^log(n))、O(2^n)是指数时间复杂度,O(n!)是阶乘时间复杂度。像O(a^n)和O(n!)型的时间复杂度,它是非多项式级的,其复杂度计算机往往不能承受。

    为什么多项式时间复杂度的定义形式是O(nk)O(nk)呢,它的多项式的多项性体现在哪呢?

    因为算法的时间复杂度的表达式O(nk)O(nk)可以为O(nk+nk−1)O(nk+nk−1),在表示时O(nk)=O(nk+nk−1)O(nk)=O(nk+nk−1),取指数最高项保留作为时间复杂度的表达式,未删除低指数项就可以看出多项式的多项性了吧!当然,单项式也算作多项式。

    注:图G的顶点个数称为图G的阶(Order)。

    2.P问题

    《算法导论》给出的定义:在多项式时间内可解的问题为P问题(Polynomial Problem,多项式问题)。

    更为具体的是:P问题指可以在多项式时间内求解的问题,例如:时间复杂度为O(nlog(n))的快速排序和堆排序,O(n2)O(n2)的冒泡排序和直接选择排序算法都是P问题,也就是多项式时间算法。相反,时间复杂度为O(nlogn)O(nlogn)、O(2n)O(2n)的算法是指数时间算法。

    3.NP问题

    定义: NP问题((Non-deterministic Polynomial Problem,非确定性多项式问题),指问题只能通过验证给定的猜测是否正确来求解。所谓多项式指的是验证猜测可在多项式时间内完成,所谓非确定性指的是问题只能通过验证猜测来解,而不能直接求解。

    如Hamilton回路是NP问题,因为验证一条路是否恰好经过了每一个顶点可在多项式时间内完成,但是找出一个Hamilton回路却要穷举所有可能性,不能直接求解。

    又如大合数的质因数分解,没有给定的公式可直接求出一个合数的两个质因数是什么,但是验证两个数是否是质因数却可在多项式时间完成,所以它也是非确定性多项式问题,即NP问题。

    之所以要定义NP问题,是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。

    简单的说,存在多项式时间的算法的一类问题,称之为P类问题;而像梵塔问题,推销员旅行问题等问题,至今没有找到多项式时间算法解的一类问题,称之为NP问题。同时,P类问题是NP问题的一个子集。也就是说,能多项式时间地解决一个问题,必然能多项式时间地验证一个问题的解。

    3.1NP与P的关系

    目前,人类还未解决的问题是:是否所有的NP问题都是P类问题,即P=NP?。这就是注明的世界七大数学难题之首。虽然这个问题尚未解决,但是,一个总的趋势和大方向是人们普遍认为,P=NP不成立,也就是说,多数人相信,存在至少一个不可能有多项式级复杂度的算法的NP问题。

    人们如此坚信P≠NP是有原因的,就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题(Non-deterministic Polynomial Complete Problem),也即所谓的 NPC问题。正是NPC问题的存在,使人们相信P≠NP。

    4.NPC问题

    4.1约化

    为了说明NPC问题,我们先引入一个概念——约化(Reducibility,有的资料上叫“归约”(Reduction)) 。

    约化的概念: 
    约化的标准概念:如果能找到这样一个变化法则,对任意一个程序A的输入,都能按这个法则变换成程序B的输入,使两程序的输出相同,那么我们说,问题A可约化为问题B,即可以用问题B的解法解决问题A,或者说,问题A可以“变成”问题B。 如:一元一次方程可以“归约”为一元二次方程。

    约化的性质: 
    约化具有一项重要的性质:约化具有传递性。如果问题A可约化为问题B,问题B可约化为问题C,则问题A一定可约化为问题C。

    约化的意义: 
    问题A可约化为问题B”有一个重要的直观意义:B的时间复杂度高于或者等于A的时间复杂度。也就是说,问题A不比问题B难。

    约化的要求: 
    我们所说的“可约化”指的是可“多项式时间地”约化(Polynomial-time Reducible),即变换输入的方法是能在多项式的时间里完成的。约化的过程只有用多项式的时间完成才有意义。

    4.2NPC问题

    NPC问题是指满足下面两个条件的问题: 
    (1)它是一个NP问题; 
    (2)所有的NP问题都可以用多项式时间约化到它。

    所以显然NP完全问题具有如下性质:它可以在多项式时间内求解,当且仅当所有的其他的NP完全问题也可以在多项式时间内求解。这样一来,只要我们找到一个NPC问题的多项式解,所有的NP问题都可以多项式时间内约化成这个NPC问题,再用多项式时间解决,这样NP就等于P了。

    目前,NPC问题还没有找到一个多项式时间算法,因此我们就此可直观地理解,NPC问题目前没有多项式时间复杂度的有效算法,只能用指数级甚至阶乘级复杂度的搜索。

    大多数人的观点对于 P类问题,NP类问题,NPC之间的关系可用下图表示(此图正确性有待验证):

    这里写图片描述

    4.3第一个NPC问题

    逻辑电路问题是第一个NPC问题。逻辑电路问题指的是这样一个问题:给定一个逻辑电路,问是否存在一种输入使输出为True。

    逻辑电路问题属于NPC问题。这是有严格证明的。它显然属于NP问题,并且可以直接证明所有的NP问题都可以约化到它(不要以为NP问题有无穷多个将给证明造成不可逾越的困难)。证明过程相当复杂,其大概意思是说任意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出(想想计算机内部也不过是一些0和1的运算),因此对于一个NP问题来说,问题转化成了求出满足结果为True的一个输入(即一个可行解)。

    有了第一个NPC问题后,一大堆NPC问题就出现了,因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。后来,Hamilton回路成了NPC问题,TSP问题(旅行商问题)也成了NPC问题。现在被证明是NPC问题的还有很多,任何一个NPC问题找到了多项式算法的话所有的NP问题都可以完美解决了。因此说,正是因为NPC问题的存在,P=NP变得难以置信。P=NP问题还有许多有趣的东西,有待大家自己进一步的挖掘。攀登这个信息学的巅峰是我们这一代的终极目标。现在我们需要做的,至少是不要把概念弄混淆了。

    5.NPH问题

    NPH问题(NP难问题,英文NP-hard问题),其满足NPC问题定义的第二条但不一定要满足第一条(就是说,NP-Hard问题要比 NPC问题的范围广,但不一定是NP问题)。

    NP-Hard问题同样难以找到多项式时间复杂度的算法,但它不列入我们的研究范围,因为它不一定是NP问题。即使NPC问题发现了多项式级的算法,NP-Hard问题有可能仍然无法得到多项式级的算法。事实上,由于NP-Hard放宽了限定条件,它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。


    参考文献

    [1]http://blog.csdn.net/liufeng_king/article/details/8475508
    [2]多项式时间算法
    [3]NP(Non-Deterministic Polynomial, 非确定多项式) 
    [4]什么是P问题、NP问题和NPC问题
    [5]图论中P、NP、NPC和NP难问题详解.

    展开全文
  • 什么是伪多项式时间算法

    千次阅读 2020-04-02 09:54:43
    首先一定要搞清楚下面的定义。 “输入规模”:一个问题的输入规模是保存输入数据所需要的bit位数。 (不理解“伪多项式时间”,可能很大程度上是由于对...伪多项式时间算法算法时间复杂度是输入数据大小的多项式...

    首先一定要搞清楚下面的定义。

    输入规模:一个问题的输入规模是保存输入数据所需要的bit位数
    (不理解“伪多项式时间”,可能很大程度上是由于对“输入规模”的误解。输入规模不是指输入的大小,也不是指多少,而是指在2进制下保存它们需要的位数!)

    多项式时间算法:在输入规模为x的情况下,算法能够在O(xk) 时间(k为常数)内解决该问题。

    伪多项式时间算法:算法的时间复杂度是输入数据大小的多项式时间表达,但却是输入数据长度(输入规模)的指数时间表达。

    对比下面两个例子。

    1. 冒泡排序:给定 n 个32位的数字,将数字从小到大排序。输入规模增长与数字大小无关,输入规模 = 32n。输入规模为x时,n = x / 32,算法用时为O((x/32)2)= O(x2)。

    2. 素数判定:给定数字 n,判断 n 是否为素数。增长规模与数字大小相关,输入规模 = logn 。输入规模为x时,n = 2x,算法用时为O(2x)。

    所以冒泡排序为多项式时间算法,素数判定则是伪多项式时间算法。

    处理图论、链表、数组、树等问题时,一般是多项式时间算法;处理背包问题、与数论有关的问题时,有时就是伪多项式时间算法了。

    参考资料:
    什么是伪多项式时间算法? - 詹宇的回答 - 知乎
    https://www.zhihu.com/question/20013122/answer/44460397

    什么是伪多项式时间算法? - 唐燕琳的回答 - 知乎
    https://www.zhihu.com/question/20013122/answer/13786174

    展开全文
  • 多项式时间算法

    千次阅读 2019-04-16 22:06:29
    在计算理论领域中,若一个数值算法的实践复杂度可以表示为输入数值N的多项式,则称其时间复杂度为伪多项式时间。由于N的值是N的位数的幂,故该算法时间复杂度实际上应视为输入数值N的位数的幂。 伪多项式时间)...
  • 多项式时间复杂度及NP问题

    千次阅读 2014-11-06 10:24:45
    与非多项式时间复杂度相关的问题叫:非确定性多项式(non-deterministic polynomial NP)   NP: 不能在多项式时间内解决或不确定能不能在多项式时间内解决,但能在多项式时间验证的问题,P问题是NP问题的一个子类...
  • 这是最近一篇的关于多项式复杂度的笔记嘞~大家也在疫情期间加油学习!!! #9.3.5 Multinomial fitness complexity(多项式复杂度) #subset,子集;intersect,相交 def isSubset(L1, L2): """ 假定L1和L2是列表 ...
  • 多项式复杂度

    千次阅读 2014-09-06 10:37:49
    上篇的标记算法中,谈到这个O(K)的算法是一个指数级复杂度算法,其实对那道题目本身来说,K是固定的,既然不是输入,那也无所谓复杂度,之所以有O(K)这种说法,是把K当做一种输入了,这是看待输入的角度问题,倒...
  • 多项式时间复杂度

    2016-12-25 12:33:00
    转载于:https://www.cnblogs.com/chy89224/p/6379669.html
  • 1.多项式时间复杂度定义:问题需要的时间复杂度)与问题的规模之间是多项式关系。例如,多项式关系形如O(nk)O(n^k),k为某个常数,n是问题的输入规模。例如,时间复杂度为O(nlog(n))、O(n^3)都是多项式时间复杂度...
  • BM算法,用于计算序列的线性复杂度及其反馈多项式。使用JAVA实现
  • 背包问题的多项式时间近似解

    千次阅读 2020-06-19 01:09:19
    背包问题的多项式时间近似解一些概念背包问题的伪多项式时间算法强NP难问题和FPTAS 一些概念 ∏\prod∏ 是一个NP难问题的优化问题 f∏f_{\prod}f∏​ 是这个优化问题的目标函数,也就是我们要优化得到的近似解 I 是...
  • 算法复杂度分析看这一篇就够了

    千次阅读 2020-04-18 12:05:56
    执行效率是算法一个非常重要的考量指标,而时间复杂度和空间复杂度则是衡量算法代码的执行效率。 为什么需要复杂度分析 通常情况下,我们可以在写完代码的情况下把程序跑一遍,通过统计、监控,就能得出算法执行的...
  • 多项式时间算法

    万次阅读 2012-02-27 16:33:53
    例如:时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指时间算法。 一个优化问题如果已经找到了多项式时间算法,则称该问题为多项式时间可解问题,并将...
  • 算法复杂度分析

    2021-03-30 08:21:19
    复杂度分析对算法来说非常的重要,也是整个算法学习的精髓。 为什么要做复杂度分析?   当然,我们写完之后把代码跑一遍,也能得到算法损耗的时间以及存储空间(像力扣刷题一样)。 我们做数据分析真的能比把代码...
  • 算法时间复杂度

    千次阅读 2017-05-09 19:56:21
    1. 算法度量标准算法设计的标准包括以下四个方面 正确性(correctness) 算法应满足用户的具体需求 可读性(readability) 算法应好读,利于读者对算法的理解 健壮性(robustness) ...时间效率指的是算法
  • 多项式复杂度有弱多项式和强多项式两种,弱多项式就是关于输入长度( nnn、 mmm 之类的,以及 log值域log 值域log值域)为多项式复杂度,强多项式就是在加减乘除为 O(1)O(1)O(1) 时复杂度关于数据规模为多项式(就是
  • 算法复杂度

    2019-09-18 10:59:07
    前导知识点对数 在数学中,对数是对求幂的逆运算。 如果a的x次方等于N(a>...一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素: (1). 算法采用的策略、方法;(2). 编译产生的代码质量;(3)....
  •         通常,对于一个给定的算法,我们要做 两项分析。...算法时间复杂度反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能很好反映出算法的优劣与否。...
  • 算法中七种常见的时间复杂度

    千次阅读 多人点赞 2020-09-17 17:11:17
    O(nᵏ) — 多项式复杂度 在这里,我们开始着手研究时间复杂度较差的算法,通常应尽可能避免使用它(请参考上文的图表,我们正处于红色区域!)。但是,许多「暴力」算法都属于多项式复杂度,可以作为帮助我们解决...
  • 8 } 每次循环迭代,pow函数内部都会执行i次乘法,然后一次加法,所以整体的算法复杂度为O = 1/2 * n ^ 2 + 3/2n,尽管pow函数的实现方法是利用递归优化后的,但是算法复杂度还是达到了O(nlogn) 2.秦九韶法: 1 ...
  • P和NP问题,如果一个问题能用多项式时间复杂性的算法求解,那么就叫做P(英文多项式polynomial的第一个字母)问题。
  • 20200809_数据结构C++语言版_读书笔记14_对数多项式复杂度 每日小知识 【mount -o】。是用loop设备,在linux挂载本地iso文件使用的。-o就是loop回环设备。 一、相关术语 logarithmic-time algorithm 对数多项式时间...
  • 通常,对于一个给定的算法,我们要做 两项分析。第一是从数学上证明算法的正确性,这一步主要用到形式化证明的方法及相关推理模式,如...因此,作为程序员,掌握基本的算法时间复杂度分析方法是很有必要的。 算法执...
  • 算法常见复杂度分析

    2020-04-16 15:00:11
    算法(algorithm) 是指用来操作...时间维度:算法执行所消耗的时间,即时间复杂度 空间维度:算法执行所消耗的内存,即空间复杂度 一、大O时间复杂度分析法 1> 概念:并不表示代码真正执行花费的时间,而是表示...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,491
精华内容 7,796
关键字:

多项式时间复杂度算法