一個演算法的執行時間效率用什麼衡量

在忽略機器效能的基礎上我們用演算法時間複雜度來衡量演算法執行的時間。
1、時間頻度
一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。 但我們不可能也沒有必要對每個演算法都上機測試，只要知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。而一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。
2、時間複雜度
在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它改變時呈現什麼規律。為此，我們引入時間複雜度概念。

一般情況下，演算法中基本操作重複執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近於無窮大時，T（n)/f(n)的極限值為不等於零的常數，則稱f(n)為T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n)) 為演算法的漸進時間複雜度，簡稱時間複雜度。

在各種不同演算法中，若演算法中語句執行次數為一個常數，則時間複雜度為O(1),另外，在時間頻度不相同時，時間複雜度有可能相同，如T(n)=n^2 3n 4與T(n)=4n^2 2n 1它們的頻度不同，但時間複雜度相同，都為O(n^2)。
依數量級遞增排列，常見的時間複雜度有：
常數階O(1),對數階O(log2n)(以2為底n的對數，下同),線性階O( n),
線性對數階O(nlog2n),平方階O(n^2)，立方階O(n^3),...，
k次方階O(n^k) ,指數階O(2^n)。隨著問題規模n的不斷增大，上述時間複雜度不斷增大，演算法的執行效率越低。
演算法的時間效能分析
（1）演算法耗費的時間和語句頻度

一個演算法所耗費的時間=演算法中每個語句的執行時間總和

每條語句的執行時間=語句的執行次數(即頻度(Frequency Count))×語句執行一次所需時間

演算法轉換為程式後，每個語句執行一次所需的時間取決於機器的指令效能、速度、編譯所產生的程式碼品質等難以確定的因素。

若要獨立於機器的軟、硬體系統來分析演算法的時間耗費，則設每條語句執行一次所需的時間都是單位時間，一個演算法的時間耗費就是該演算法中所有語句的頻度之和。
求兩個n階方陣的乘積C=A×B,其演算法如下:

　　# define n 100 // n 可根据需要定义,这里假定为100
　　void MatrixMultiply(int A[a]，int B [n][n]，int C[n][n])
　　{ //右边列为各语句的频度
　　int i ,j ,k;
　　 for(i=0; i<n;j++) n+1
　　 for (j=0;j<n;j++) { n(n+1)
　　 C[i][j]=0; n
　　 for (k=0; k<n; k++) nn(n+1)
　　 C[i][j]=C[i][j]+A[i][k]*B[k][j];n
　　}
　　}

該演算法中所有語句的頻度總和(即演算法的時間耗費)為：

T(n)=nn(n 1) (1.1)

分析：

語句(1)的迴圈控制變數i要增加到n ，測試到i=n成立才會終止。故它的頻度是n 1。但是它的迴圈體只能執行n次。語句(2)作為語句(1)迴圈體內的語句應該執行n次，但語句(2)本身要執行n 1次，所以語句(2)的頻度是n(n 1)。同理可得語句(3)，(4)和(5)的頻度分別是n，nn(n 1)和n。

演算法MatrixMultiply的時間耗費T(n)是矩陣階數n3的函數。

（2）問題規模和演算法的時間複雜度
演算法求解問題的輸入量稱為問題的規模(Size),一般用一個整數表示。

矩陣乘積問題的尺度是矩陣的階數。

一個圖論問題的尺度則是圖中的頂點數或邊數。

一個演算法的時間複雜度(Time Complexity, 也稱時間複雜性)T(n)是該演算法的時間耗費，是該演算法所求解問題規模n的函數。當問題的規模n趨向無窮大時，時間複雜度T(n)的數量級(階)稱為演算法的漸進時間複雜度。

演算法MatrixMultidy的時間複雜度T(n)如(1.1)式所示，當n趨向無窮大時，顯然有T(n)~O(n3);

#這表明，當n充分大時，T(n)和n3之比是不等於零的常數。即T(n)和n3是同階的，或說T(n)和n3的數量級相同。記作T(n)=O(n3)是演算法MatrixMultiply的漸近時間複雜度。

（3）漸進時間複雜度評估演算法時間效能

主要用演算法時間複雜度的數量級(即演算法的漸進時間複雜度)評估一個演算法的時間效能。
演算法MatrixMultiply的時間複雜度一般為T(n)=O(n3)，f(n)=n3是此演算法中語句(5)的頻度。下面再舉例說明如何求演算法的時間複雜度。

交換i和j的內容。

#

Temp=i;
i=j;
j=temp;

　　以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。　　
注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
变量计数之一：

　　 x=0;y=0;
　　 for(k-1;k<=n;k++)
　　 x++;
　　 for(i=1;i<=n;i++)
　　 for(j=1;j<=n;j++)
　　 y++;

一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。因此，以上程序段中频度最大的语句是(6)，其频度为f(n)=n2，所以该程序段的时间复杂度为T(n)=O(n2)。

当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

变量计数之二：

x=1;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x++;

该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：

则该程序段的时间复杂度为T(n)=O(n3/6+低次项)=O(n3)。

（4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。

在数值A[0..n-1]中查找给定值K的算法大致如下：

i=n-1;
while(i>=0&&(A[i]!=k))
 i--;
return i;

此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关:

①若A中没有与K相等的元素，则语句(3)的频度f(n)=n；

②若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。

以上是一個演算法的執行時間效率用什麼衡量的詳細內容。更多資訊請關注PHP中文網其他相關文章！