首頁人工智能技術(shù)資訊正文

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

更新時(shí)間:2022-05-31 來源:黑馬程序員 瀏覽量:

分析一個(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的變化。

1653989744854_41.png

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

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

當(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í)形式給出,格式如下所示:

1653992397625_43.png

一個(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ù)雜度。


分享到:
在線咨詢 我要報(bào)名
和我們?cè)诰€交談!