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

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

1.時(shí)間復(fù)雜度

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

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

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

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

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

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

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

接下來通過分析幾段程序的執(zhí)行過程來推導(dǎo)出其時(shí)間復(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ù)項(xiàng)以1代替。在保留其最高階項(xiàng)時(shí)，發(fā)現(xiàn)其沒有最高階項(xiàng)，因此該算法的時(shí)間復(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ù)項(xiàng)以1替換，且只保留最高階項(xiàng)，則得出T(n)=O(n），因此該算法的時(shí)間復(fù)雜度為O(n），為線性階。

程序段3代碼如下所示：

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

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

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

2.空間復(fù)雜度

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

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

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

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