演算法的數量級

⑴ 一個演算法的時間復雜度為(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))