您的位置  > 互联网

倍数之所以特殊,主要是由于其值随增大的特性

也就是说,对于变量n,5n^2+2n+1称为多项式。 在前面加上n^3,甚至一直增加到n^m。 只要 m 是常数,它就是多项式。 因为这样的公式结合了类似的项和其他简化,所以最终仍然会有几个项包含n,因此称为多项式。

那么我们来谈谈问题大小n。 其实字面理解是正确的……也就是说,我们要解决一个问题。 这个问题有n个“东西”需要处理,这个问题的大小是n。 例如,如果我们要对5、7、9这三个数字进行排序,则问题大小为3。我们需要找出世界上人类中的男人。 问题的严重性在于世界人口的规模。

然后是多项式倍数。 这个倍数意味着对于一个变量n,存在这样一个倍数,其值为n的多项式。 比如我们假设n=5,那么n^2+10=5^2+10=35,而这个35就是n的多项式倍数。 因为n有无穷多个多项式组合,所以它也有无穷多个多项式倍数。

多项式倍数之所以特殊,主要是因为它们的值随着n的增加而加速的特性。 如果是常数时间,则表示无论n取什么值,操作所花费的时间都是相同的。 线性时间意味着需要与n一样多的时间。 多项式时间是指随着n的增加,每增加1,所花费的时间就越来越多。对于像n^2-3这样的多项式时间,当n=2时,可能只需要1次,甚至低于线性时间,但当n=4时,可能需要13次。 可以想象,无论时间有多大,这些值中的一些都会变得巨大。 但它的增长速度没有指数时间(m^n)快,而且m^n不能写成多项式形式,所以它与多项式时间不同。

而且,该生长速率特性不受参数限制。 换句话说,无论你把m*n^2的常数m改成多么小的值,总有一个n使得这个多项式的值大于n。 也就是说,此时的多项式时间算法比线性时间算法花费的时间还多,如果采用线性时间算法,那么以后的耗时差距肯定会越来越大。 这个特性是由多项式本身的性质决定的。 同样,指数时间也是如此。 无论将 n 多项式中的所有常数设置多大,总会存在大于多项式值的 n 指数值。 所以我们说指数时间大于多项式时间,我们说多项式时间大于线性时间,我们还说线性时间大于常数时间。 值得注意的是,这些大于的值并不适用于所有 n 的所有情况。 我们只是说,随着n的增加,前者肯定多于后者。

希望有帮助。