多项式时间
多项式时间
首先知道多项式吗?
也就是对于变量n,
5n2+2n+1
这种就叫做多项式。前面再加上n3甚至一路增加到nm,只要m是个常量,就都是多项式。因为这样的式子合并同类项什么的简化到最后还是会有好几个含n的项,所以叫做多项式。
然后再说问题大小n。其实字面理解就对了…也就是说,我们要解决一个问题,这个问题里面有n个“东西”要处理,这个问题的大小就是n。比方说,我们要把5、7、9这三个数字排序,问题大小就是3。我们要把全世界人类里面的男的找出来,问题大小就是全世界人口数。然后是多项式倍数。
这个倍数是指,对于一个变量n,有这样一个倍数,它的值是n的一个多项式。
比方说,我们假设n=5,那么n2+10=52+10=35,这个35就是n的一个多项式倍数。因为对于n有无限多种多项式组合,所以它也就有无穷多个多项式倍数。多项式倍数之所以特殊,主要是由于其值随n增大而加速增大的特性。
如果是常数时间的话,意思就是无论n是什么值运算所花时间都一样。
线性时间则是说多大n就花多少时间。
多项式时间则意味着随着n增大,n每增加1所花的时间增长越来越多。
对于n2−3这样一个多项式时间来说,n=2的时候可能只要花1的时间,甚至低于线性时间,但n=4的时候可能就要花13的时间了,可以想象再大一些这个数值会变得巨大。但是它又不及指数时间增长快(mn),且mn不能写成多项式形式,所以它又和多项式时间有区别。而且,这个增长变速的特性是不受参数限制的。也就是说,无论你把m∗n2的m这个常量改成多么微小的一个值,总有一个n让这个多项式的值大于n,也就是说到这一刻多项式时间的算法耗时高于了线性时间的算法,之后耗时差距一定会越来越大。这一特性是多项式本身的性质决定的。类似,指数级时间也是如此,无论你将n的一个多项式中的所有常量设置到多大,总有一个n的指数值大于多项式值。
所以我们说
指数时间 > 多项式时间 > 线性时间 > 常数时间,
一定要注意这些大于并不是对于所有n的所有情况成立的,只是在说随着n增加前者一定超过后者。希望有帮助。专业人士请在评论区轻喷,谢谢。
作者:沈万马
链接:https://www.zhihu.com/question/24653072/answer/28547757
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。