算法的数量级

⑴ 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

数量级表示为O(n)。

分析过程如下：

分子分母同除n^2，则(n^3+n^2log2n+14n)/n^2=n+log2n+14n^(-1)；

当n足够大时，即n→+∞有：n>log2n，14n^(-1)=0；

因为时间复杂度数量级是计算n趋于无穷大时的最大无穷大量的最大阶次；

因此，对于n+log2n+14n^(-1)，n为最大的无穷大量，数量级表示为O(n);

即：(n^3+n^2log2n+14n)/n^2的数量级表示为O(n)。

(1)算法的数量级扩展阅读：

计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。

时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数，考察当输入值大小趋近无穷时的情况。时间复杂度数量级是计算n趋于无穷大时的最大无穷大量的最大阶次。

按数量级递增排列，常见的时间复杂度有：

1、常数阶O(1)，对数阶O(log2n)，线性阶O(n)；

2、线性对数阶O(nlog2n)，平方阶O(n^2)，立方阶O(n^3)，...

3、k次方阶O(n^k)，指数阶O(2^n)。

随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

求解算法的时间复杂度数量级的具体步骤是：

1、找出算法中的基本语句，算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

2、计算基本语句的执行次数的数量级，保证基本语句执行次数的函数中的最高次幂正确。

3、用大Ο记号表示算法的时间性能。将基本语句执行次数的数量级放入大Ο记号中。

⑵ 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

结果为：O(n)

解题过程如下：

因为时间复杂度是计算n趋于无穷大时候的无穷大量的最大阶次

结果第一项是n，第2项是log2n，第3项是1/n，

当n趋于无穷大时，第二项比第一项小，第3项为0

所以(n3+n2log2n+14n)/n2，其数量级表示为O(n)

(2)算法的数量级扩展阅读

时间复杂度计算方法：

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得T(n)/f(n)的极限值（当n趋近于无穷大时）为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

随着模块n的增大，算法执行的时间的增长率和 f(n) 的增长率成正比，所以 f(n) 越小，算法的时间复杂度越低，算法的效率越高。

在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级（它的同数量级有以下：1，log2n，n，n log2n ，n的平方，n的三次方，2的n次方，n!），找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，则时间复杂度T(n) = O(f(n))