怎樣計算一個算法的復雜度？

分析一個算法主要看這個算法的執(zhí)行需要多少機器資源。在各種機器資源中，時間和空間是兩個最主要的方面。因此，在進行算法分析時，人們最關心的就是運行算法所要花費的時間和算法中使用的各種數(shù)據所占用的空間資源。算法所花費的時間通常稱為時間復雜度，使用的空間資源稱為空間復雜度。接下來學習如何計算一個算法的時間復雜度和空間復雜度。

1.時間復雜度

在進行算法分析時，語句總的執(zhí)行次數(shù)T(n）是關于問題規(guī)模n的函數(shù)，然后分析T(n）隨n的變化。

這樣用大寫的O來標記算法的時間復雜度，稱之為大O(Order的簡寫）標記法。一般隨著n的增長，T(n)也會隨之增長，其中T(n
)增長最慢者就是時間性能最優(yōu)的算法。

在計算時間復雜度的時候，根據T(n)與n的最高階數(shù)關系，我們給這些算法的復雜度進行了歸類，如表1所示。

當然還會有一些其他階數(shù)關系，這里只是列出了幾種較常見的關系。算法的執(zhí)行次數(shù)可能會與規(guī)模n呈現(xiàn)出這些關系，那么這些關系又是如何推導出來的呢？下面給出大O階的推導方法：

（1）用常數(shù)1取代運行中的所有加法常數(shù)。

（2）在修改后的運行次數(shù)函數(shù)中，只保留最高階項。

（3）如果最高階項存在，且不是1，則除去其常系數(shù)，得到的結果就是大O階。

接下來通過分析幾段程序的執(zhí)行過程來推導出其時間復雜度，程序段1代碼如下所示：

int a=100;              //執(zhí)行一次

int b=200;              //執(zhí)行一次

int sum=a+b;            //執(zhí)行一次

printf("&d\n",sum);      //執(zhí)行一次

上述程序段有4行代碼，每一行執(zhí)行1次，加起來一共執(zhí)行了4次，f(n）=4，即T(n)=O(4）。根據推導方法中的第一條，將常數(shù)項以1代替。在保留其最高階項時，發(fā)現(xiàn)其沒有最高階項，因此該算法的時間復雜度為O(1），為常數(shù)階。程序段2代碼如下所示：

void func()
{
    int i,sum=0;                         //執(zhí)行一次
    for (i=0;i<=100;i++)
    {
    sum +=i;                              //執(zhí)行n次
    }

    printf("sd\n",sum);               //執(zhí)行一次
}

該程序段的執(zhí)行次數(shù)為1+n+1，則f(n)=n+2，即T(n)=O(n+2)。然后將常數(shù)項以1替換，且只保留最高階項，則得出T(n)=O(n），因此該算法的時間復雜度為O(n），為線性階。

程序段3代碼如下所示：

void func()
{
    int i=l;
    do
    {
    i*=2；
    }
    while (i<n);
}

在這個程序段中，當i<n時，循環(huán)結束。如果循環(huán)了f(n)次，則2(fn)=n，即f(n)=log2n，T(n)=O(log2n)。然后消除常系數(shù)，保留最高階項，最后得出T（n)=O（logn)，為對數(shù)階。

用大O階來推導算法的復雜度并不難，讀者在以后的學習中設計算法，就可以用此法來估測算法的優(yōu)劣。

2.空間復雜度

空間復雜度是對一個算法在運行過程中所占存儲空間大小的度量，一般也作為問題規(guī)模n的函數(shù)，以數(shù)量級形式給出，格式如下所示：

一個算法的存儲量包括輸入數(shù)據所占空間、程序本身所占空間和輔助變量所占空間。在對算法進行分析時，只考慮輔助變量所占空間。若所需輔助空間相對于輸入數(shù)據量來說是常數(shù)，則稱此算法為原地工作。若所用空間量依賴于特定的輸入，則除了有特殊說明外，均按最壞情況考慮。

有時候，在寫代碼時可以用空間來換取時間，例如，寫一個算法來判斷某年是否是閏年，這樣每輸入一個年份都要調用算法去判斷一下，在時間上就有點復雜。為了提高效率，可以用空間來換取時間，即建立一個大小合適的數(shù)據，編號從0到n，如果是閏年，則存入數(shù)據1，否則存入數(shù)據0。這樣只要通過判斷年份編號上存儲的是0還是1就知道該年份是否是閏年了。

用空間換取時間可以將運算最小化，但這兩種情況哪種更好，要結合具體情況而定。一般情況下，都是用時間復雜度來度量算法，當不加限定地使用“復雜度”這一術語時，都是指時間復雜度。