算法時(shí)間復(fù)雜度的概念

本講要點(diǎn)為什么要考慮算法時(shí)間復(fù)雜度？什么是算法時(shí)間復(fù)雜度？如何計(jì)算算法時(shí)間復(fù)雜度？（1）為什么要考慮算法時(shí)間復(fù)雜度？一種數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣是由實(shí)現(xiàn)其各種操作的算法決定的。對(duì)數(shù)據(jù)結(jié)構(gòu)的分析實(shí)質(zhì)上就是對(duì)實(shí)現(xiàn)各種操作的算法進(jìn)行分析。除了要驗(yàn)證算法是否能正確解決問(wèn)題外，還需要對(duì)算法的效率進(jìn)行評(píng)價(jià)。對(duì)于一個(gè)實(shí)際問(wèn)題的解決，可以提出若干算法，那么如何從這些可行的算法中找出最有效的算法呢？或者有了一個(gè)解決實(shí)際問(wèn)題的算法，如何來(lái)分析它的性能呢？這些問(wèn)題需要通過(guò)算法分析來(lái)確定。通常，算法分析主要分析算法的時(shí)間代價(jià)和空間代價(jià)這兩個(gè)主要指標(biāo)。（1）為什么要考慮算法時(shí)間復(fù)雜度？隨著計(jì)算機(jī)功能的日益強(qiáng)大，程序的運(yùn)行效率變得越來(lái)越不那么重要了嗎？計(jì)算機(jī)功能越強(qiáng)大，人們就越想去嘗試解決更復(fù)雜的問(wèn)題。不僅需要算法，而且需要“好”的算法。在選擇和設(shè)計(jì)算法時(shí)要有效率的觀(guān)念，這一點(diǎn)比提高計(jì)算機(jī)本身的速度更為重要。（2）什么是算法時(shí)間復(fù)雜度？問(wèn)題規(guī)模的概念：是指輸入量的多少，一般來(lái)說(shuō)，它可以從問(wèn)題描述中得到。一個(gè)事實(shí)：幾乎所有的算法，對(duì)于規(guī)模更大的輸入都需要運(yùn)行更長(zhǎng)的時(shí)間。運(yùn)行算法所需要的時(shí)間是問(wèn)題規(guī)模n的函數(shù)。要精確地用函數(shù)表示算法的運(yùn)行時(shí)間是很困難的。算法時(shí)間分析度量的標(biāo)準(zhǔn)：不是針對(duì)實(shí)際執(zhí)行時(shí)間精確算出算法執(zhí)行的具體時(shí)間，而是針對(duì)算法中基本語(yǔ)句的執(zhí)行次數(shù)做出估計(jì)。（2）什么是算法時(shí)間復(fù)雜度？如何度量：引入時(shí)間復(fù)雜度（TimeComplexity）概念。算法中基本語(yǔ)句的重復(fù)執(zhí)行次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)f(n)，算法的時(shí)間度量表示為O(f(n))。這里的“O”是英文“Order”的縮寫(xiě)，但并不代表“順序”的意思，而是“階數(shù)”的概念。它表示隨著問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間增長(zhǎng)率和f(n)增長(zhǎng)率相同，稱(chēng)為算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度，記作T(n)=O(f(n))。例如f(n)=amnm+am-1nm-1+…+a1n+a0，則T(n)=O(nm)。f(n)與nm之比是一個(gè)不等于零的常數(shù)，即f(n)與nm的數(shù)量級(jí)相同。在計(jì)算算法時(shí)間復(fù)雜度時(shí)，可以忽略所有低次冪項(xiàng)和最高次冪項(xiàng)的系數(shù)。（3）如何計(jì)算算法時(shí)間復(fù)雜度？1）for(i=1;i<100;i++)s++;該程序段的語(yǔ)句執(zhí)行次數(shù)是常量，時(shí)間復(fù)雜度記為O(1)，稱(chēng)為常量階。2）for(i=0;i<n;i++)s+=i;該程序段基本語(yǔ)句“s+=i;”的執(zhí)行次數(shù)f(n)=n，因此它的時(shí)間復(fù)雜度T(n)=O(f(n))=O(n)，稱(chēng)為線(xiàn)性階。（3）如何計(jì)算算法時(shí)間復(fù)雜度？3）for(i=0;i<n;i++) for(j=0;j<n;j++) s++;f(n)=n+n+…+n=n2，時(shí)間復(fù)雜度T(n)=O(f(n))=O(n2)，稱(chēng)為平方階。4）for(i=0;i<n;i++) for(j=i;j<n;j++) s++;這是一個(gè)二重循環(huán)，基本語(yǔ)句“s++;”的執(zhí)行次數(shù)

f(n)=n+(n-1)+(n-2)+……+2+1=n(n+1)/2，是n2數(shù)量級(jí)，因此時(shí)間復(fù)雜度T(n)=O(n2)。（3）如何計(jì)算算法時(shí)間復(fù)雜度？5）for(i=1;i<=n;i=2*i) s++;設(shè)該程序段基本語(yǔ)句“s++;”的執(zhí)行次數(shù)為f(n)，則有2f(n)≤n，即f(n)≤log2n，因此該段程序的時(shí)間復(fù)雜度為O(log2n)，稱(chēng)為對(duì)數(shù)階。小結(jié)：求解算法時(shí)間復(fù)雜度的步驟1）找出算法中的基本語(yǔ)句。算法中執(zhí)行次數(shù)最多的那條語(yǔ)句就是基本語(yǔ)句。通常是最內(nèi)層循環(huán)的循環(huán)體。2）計(jì)算基本語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)。只需計(jì)算基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)。這就意味著只要保證基本語(yǔ)句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確