1.3.3 算法效率的評價

一個算法是由控制結構（順序、分支和循環）和原操作（指固有數據類型的操作）構成的，算法的執行時間取決于二者的綜合結果。為了便于比較同一問題的不同算法，通常從算法中選取一種對于所研究的問題來說是基本運算的原操作，算法執行的時間大致為基本運算所需的時間與其運行次數（一條語句的運行次數稱為語句頻度）的乘積。

微課1-3　算法效率的評價

顯然，在一個算法中，執行的基本運算次數越少，其執行時間就相對越少；執行基本運算的次數越多，其運行時間也相對越多。換言之，一個算法的執行時間可以看成基本運算執行的次數。

算法基本運算次數T(n)是問題規模n的某個函數f(n)，記作

T(n)=O(f(n))

其中，記號“O”讀作“大歐”（值數量級），它表示隨問題規模n的增大，算法執行時間的增長和f(n)的增長率相同，稱為算法的時間復雜度。

“O”的形式定義為：若f(n)是正整數n的一個函數，則T(n)=O(f(n))表示存在一個正的常數M，使得當n≥n₀時都滿足|T(n)|≤M|f(n)|，也就是只求出T(n)的最高階，忽略其低階項和常數，這樣既可以簡化計算，又可以較為客觀地反映當n很大時算法的效率。

一個沒有循環的算法中基本運算次數與問題規模n無關，記為O(1)，也稱作常數階。一個只有一重循環的算法中基本次數與問題規模n的增長呈線性增大關系，記為O(n)，也稱線性階。例如，以下3個程序段：

（a）{ ++ x; s = 0; }
（b）for(i = 1; i <= n; i ++ ){ ++ x; s += x; }
（c）for(j = 1; j <= n; j ++ )
     for(k = 1; k <= n; k ++) { ++ x; s += x; }

含基本操作“++x”的語句頻度分別為1、n和n2，則這3個程序段的時間復雜度分別為O(1)、O(n)和O(n2)，分別稱為常量階、線性階和平方階。各種不同數量級對應的值存在如下關系：

O(1)<O(log₂n)<O(n)<O(nlog₂n)<O(n2)<O(n3)<O(2n)<O(n!)

例1-4　分析以下算法的時間復雜度。

void fun(int a[],int n,int k)
{
    int i;
    i = 0;                                                      //語句（1）
    while(i < n && a[i] != k)                                   //語句（2）
        i ++;                                                   //語句（3）
    return (i);                                                 //語句（4）
}

解　該算法完成在一維數組a[n]中查找給定值k的功能。語句（3）的頻度不僅與問題規模n有關，還與輸入實例中a的各個元素取值是否等于k的取值有關，即與輸入實例的初始狀態有關。若a中沒有與k相等的元素，則語句（3）的頻度為n；若a中的第一個元素a[0]等于k，則語句（3）的頻度是常數0。在這種情況下，可用最壞情況下的時間復雜度作為算法的時間復雜度。這樣做的原因是，最壞情況下的時間復雜度是在任何輸入實例里運行時間的上界。

有時也可以選擇以算法的平均時間復雜度作為討論目標。所謂平均時間復雜度，是指所有可能的輸入實例在以等概率出現的情況下算法的期望運行時間與問題規模n的數量級的關系。例1-4中，k出現在任何位置的概率相同，都為1/n，則語句（3）的平均時間復雜度為

(0+1+2+…+(n?1))/n = (n?1)/2

它決定此程序的平均時間復雜度的數量級為O(n)。

例1-5　分析以下算法的時間復雜度。

float RSum(float list[],int n)
{
    count ++;
    if(n){
        count ++;
        return RSum(list,n-1) + list[n-1];
    }
    count ++;
    return 0;
}

解　例1-5是求數組元素之和的遞歸程序。為了確定這一遞歸程序的程序步，首先考慮當n=0時的情況。顯然，當n=0時，程序只執行if條件判斷語句和第二條return語句，所需程序步數為2。當n>0時，程序在執行if條件判斷語句后，將執行第一條return語句。此return語句不是簡單返回，而是在調用函數RSum(list,n?1)后，再執行一次加法運算后返回。

設RSum(list,n)的程序步為T(n)，則RSum(list,n?1)為T(n?1)，那么，當n>0時，T(n)=T(n?1)+2。于是有

這是一個遞推關系式，它可以通過轉換成如下公式來計算

根據上述結果可知，該程序的時間復雜度為線性階，即O(n)。