必威体育Betway必威体育官网
当前位置:首页 > IT技术

多项式时间

时间:2019-06-27 04:42:10来源:IT技术作者:seo实验室小编阅读:68次「手机版」
 

多项式时间

多项式时间

首先知道多项式吗?

也就是对于变量n,

5n2+2n+1 5n^2 +2n+15n2+2n+1

这种就叫做多项式。前面再加上n3n^3n3甚至一路增加到nmn^mnm,只要m是个常量,就都是多项式。因为这样的式子合并同类项什么的简化到最后还是会有好几个含n的项,所以叫做多项式。

然后再说问题大小n。其实字面理解就对了…也就是说,我们要解决一个问题,这个问题里面有n个“东西”要处理,这个问题的大小就是n。比方说,我们要把5、7、9这三个数字排序,问题大小就是3。我们要把全世界人类里面的男的找出来,问题大小就是全世界人口数。然后是多项式倍数

这个倍数是指,对于一个变量n,有这样一个倍数,它的值是n的一个多项式。

比方说,我们假设n=5,那么n2+10=52+10=35n^2+10=5^2+10=35n2+10=52+10=35,这个35就是n的一个多项式倍数。因为对于n有无限多种多项式组合,所以它也就有无穷多个多项式倍数。多项式倍数之所以特殊,主要是由于其值随n增大而加速增大的特性

如果是常数时间的话,意思就是无论n是什么值运算所花时间都一样。

线性时间则是说多大n就花多少时间。

多项式时间则意味着随着n增大,n每增加1所花的时间增长越来越多。

对于n23n^2-3n2−3这样一个多项式时间来说,n=2的时候可能只要花1的时间,甚至低于线性时间,但n=4的时候可能就要花13的时间了,可以想象再大一些这个数值会变得巨大。但是它又不及指数时间增长快(mn)(m^n)(mn),且mnm^nmn不能写成多项式形式,所以它又和多项式时间有区别。而且,这个增长变速的特性是不受参数限制的。也就是说,无论你把mn2m*n^2m∗n2的m这个常量改成多么微小的一个值,总有一个n让这个多项式的值大于n,也就是说到这一刻多项式时间的算法耗时高于了线性时间的算法,之后耗时差距一定会越来越大。这一特性是多项式本身的性质决定的。类似,指数级时间也是如此,无论你将n的一个多项式中的所有常量设置到多大,总有一个n的指数值大于多项式值。

所以我们说

指数时间 > 多项式时间 > 线性时间 > 常数时间

一定要注意这些大于并不是对于所有n的所有情况成立的,只是在说随着n增加前者一定超过后者。希望有帮助。专业人士请在评论区轻喷,谢谢。

作者:沈万马

链接:https://www.zhihu.com/question/24653072/answer/28547757

来源:知乎

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

相关阅读

分享到:

栏目导航

推荐阅读

热门阅读