怎樣計算一個算法的復(fù)雜度？

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

1.時間復(fù)雜度

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

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

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

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

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

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

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

接下來通過分析幾段程序的執(zhí)行過程來推導(dǎo)出其時間復(fù)雜度，程序段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）。根據(jù)推導(dǎo)方法中的第一條，將常數(shù)項以1代替。在保留其最高階項時，發(fā)現(xiàn)其沒有最高階項，因此該算法的時間復(fù)雜度為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），因此該算法的時間復(fù)雜度為O(n），為線性階。

程序段3代碼如下所示：

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

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

用大O階來推導(dǎo)算法的復(fù)雜度并不難，讀者在以后的學(xué)習(xí)中設(shè)計算法，就可以用此法來估測算法的優(yōu)劣。

2.空間復(fù)雜度

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

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

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

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