數(shù)據(jù)結(jié)構(gòu)——《大話數(shù)據(jù)結(jié)構(gòu)》之時(shí)間復(fù)雜度

聲明:該文章中內(nèi)容為《大話數(shù)據(jù)機(jī)構(gòu)》一書中的內(nèi)容

1 函數(shù)的漸近增長(zhǎng)

我們現(xiàn)在來(lái)判斷一下则奥,兩個(gè)算法A和B哪個(gè)更好。假設(shè)兩個(gè)算法的輸入規(guī)模都是n步藕,算法A要做2n + 3次操作垮卓,你可以理解為先有一個(gè)n次的循環(huán),執(zhí)行完成后鲜戒,再有一個(gè)n次循環(huán)柬讨,最后有三次賦值或運(yùn)算,共2n + 3次操作袍啡。算法B要做3n + 1次操作踩官。你覺得它們誰(shuí)更快呢?

準(zhǔn)確說(shuō)來(lái)境输,答案是不一定的(如表2-8-1所示)蔗牡。

當(dāng)n = 1時(shí),算法A效率不如算法B(次數(shù)比算法B要多一次)嗅剖。而當(dāng)n = 2時(shí)辩越,兩者效率相同;當(dāng)n > 2時(shí)信粮,算法A就開始優(yōu)于算法B了黔攒,隨著n的增加,算法A要越來(lái)越好過(guò)算法B了(執(zhí)行的次數(shù)比B要少)强缘。于是我們可以得出結(jié)論督惰,算法A總體上要好過(guò)算法B。

此時(shí)我們給出這樣的定義旅掂,輸入規(guī)模n在沒有限制的情況下赏胚,只要超過(guò)一個(gè)數(shù)值N,這個(gè)函數(shù)就總是大于另一個(gè)函數(shù)商虐。我們稱函數(shù)是漸近增長(zhǎng)的觉阅。

函數(shù)的漸近增長(zhǎng):給定兩個(gè)函數(shù)f(n)和g(n)崖疤,如果存在一個(gè)整數(shù)N,使得對(duì)于所有的n > N典勇,f(n)總是比g(n)大劫哼,那么,我們說(shuō)f(n)的增長(zhǎng)漸近快于g(n)割笙。

從中我們發(fā)現(xiàn)沦偎,隨著n的增大,后面的 +3還是 +1其實(shí)是不影響最終的算法變化的咳蔚,例如算法A’與算法B’豪嚎。所以,我們可以忽略這些加法常數(shù)谈火。后面的例子侈询,這樣的常數(shù)被忽略的意義可能會(huì)更加明顯。

我們來(lái)看第二個(gè)例子糯耍。算法C是4n + 8扔字,算法D是2n2+ 1(如表2-8-2所示)。

當(dāng)n < = 3的時(shí)候温技,算法C要差于算法D(因?yàn)樗惴–次數(shù)比較多)革为,但當(dāng)n > 3后,算法C的優(yōu)勢(shì)就越來(lái)越優(yōu)于算法D了舵鳞,到后來(lái)更是遠(yuǎn)遠(yuǎn)勝過(guò)震檩。而當(dāng)后面的常數(shù)去掉后,我們發(fā)現(xiàn)其實(shí)結(jié)果沒有發(fā)生改變蜓堕。甚至我們?cè)儆^察發(fā)現(xiàn)抛虏,哪怕去掉與n相乘的常數(shù),這樣的結(jié)果也沒發(fā)生改變迂猴,算法C’ 的次數(shù)隨著n的增長(zhǎng),還是遠(yuǎn)小于算法D’傻寂。也就是說(shuō)息尺,與最高次項(xiàng)相乘的常數(shù)并不重要。

我們?cè)賮?lái)看第三個(gè)例子崎逃。算法E是2n2+ 3n + 1掷倔,算法F是2n3+ 3n + 1(如表2-8-3所示)眉孩。

當(dāng)n = 1的時(shí)候个绍,算法E與算法F結(jié)果相同勒葱,但當(dāng)n > 1后,算法E的優(yōu)勢(shì)就要開始優(yōu)于算法F巴柿,隨著n的增大广恢,差異非常明顯凯旋。通過(guò)觀察發(fā)現(xiàn),最高次項(xiàng)的指數(shù)大的钉迷,函數(shù)隨著n的增長(zhǎng)至非,結(jié)果也會(huì)變得增長(zhǎng)特別快。

我們來(lái)看最后一個(gè)例子舰蟆。算法G是2n2趣惠,算法H是3n + 1,算法I是2n2+ 3n + 1(如表2-8-4所示)身害。

這組數(shù)據(jù)應(yīng)該就看得很清楚味悄。當(dāng)n的值越來(lái)越大時(shí),你會(huì)發(fā)現(xiàn)塌鸯,3n+1已經(jīng)沒法和2n2的結(jié)果相比較侍瑟,最終幾乎可以忽略不計(jì)。也就是說(shuō)丙猬,隨著n值變得非常大以后丢习,算法G其實(shí)已經(jīng)很趨近于算法I。于是我們可以得到這樣一個(gè)結(jié)論淮悼,判斷一個(gè)算法的效率時(shí)咐低,函數(shù)中的常數(shù)和其他次要項(xiàng)常常可以忽略袜腥,而更應(yīng)該關(guān)注主項(xiàng)(最高階項(xiàng))的階數(shù)见擦。

判斷一個(gè)算法好不好,我們只通過(guò)少量的數(shù)據(jù)是不能做出準(zhǔn)確判斷的羹令。根據(jù)剛才的幾個(gè)樣例鲤屡,我們發(fā)現(xiàn),如果我們可以對(duì)比這幾個(gè)算法的關(guān)鍵執(zhí)行次數(shù)函數(shù)的漸近增長(zhǎng)性福侈,基本就可以分析出酒来,某個(gè)算法,隨著n的增大肪凛,它會(huì)越來(lái)越優(yōu)于另一算法堰汉,或者越來(lái)越差于另一算法辽社。這其實(shí)就是事前估算方法的理論依據(jù),通過(guò)算法時(shí)間復(fù)雜度來(lái)估算算法時(shí)間效率翘鸭。

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

2.1?算法時(shí)間復(fù)雜度定義

在進(jìn)行算法分析時(shí)滴铅,語(yǔ)句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù),進(jìn)而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級(jí)就乓。算法的時(shí)間復(fù)雜度汉匙,也就是算法的時(shí)間量度,記作:T(n) = O(f(n))生蚁。它表示隨問題規(guī)模n的增大噩翠,算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同,稱作算法的漸近時(shí)間復(fù)雜度邦投,簡(jiǎn)稱為時(shí)間復(fù)雜度绎秒。其中f(n)是問題規(guī)模n的某個(gè)函數(shù)。

這樣用大寫O()來(lái)體現(xiàn)算法時(shí)間復(fù)雜度的記法尼摹,我們稱之為大O記法见芹。

一般情況下,隨著n的增大蠢涝,T(n)增長(zhǎng)最慢的算法為最優(yōu)算法玄呛。

顯然,由此算法時(shí)間復(fù)雜度的定義可知和二,我們的三個(gè)求和算法的時(shí)間復(fù)雜度分別為O(n)徘铝,O(1),O(n2)惯吕。我們分別給它們?nèi)×朔枪俜降拿Q惕它,O(1)叫常數(shù)階,O(n)叫線性階废登,O(n2)叫平方階淹魄,當(dāng)然,還有其他的一些階堡距,我們之后會(huì)介紹甲锡。

2.2?推導(dǎo)大O階方法

那么如何分析一個(gè)算法的時(shí)間復(fù)雜度呢?即如何推導(dǎo)大O階呢羽戒?我們給出了下面的推導(dǎo)方法缤沦,基本上,這也就是總結(jié)前面我們舉的例子

推導(dǎo)大O階

1.用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)易稠。

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

3.如果最高階項(xiàng)存在且不是1,則去除與這個(gè)項(xiàng)相乘的常數(shù)企量。

得到的結(jié)果就是大O階测萎。

哈,仿佛是得到了游戲攻略一樣梁钾,我們好像已經(jīng)得到了一個(gè)推導(dǎo)算法時(shí)間復(fù)雜度的萬(wàn)能公式绳泉⊙仿眨可事實(shí)上姆泻,分析一個(gè)算法的時(shí)間復(fù)雜度,沒有這么簡(jiǎn)單冒嫡,我們還需要多看幾個(gè)例子拇勃。

2.3?常數(shù)階

首先順序結(jié)構(gòu)的時(shí)間復(fù)雜度。下面這個(gè)算法孝凌,也就是剛才的第二種算法方咆,為什么時(shí)間復(fù)雜度不是O(3),而是O(1)蟀架。

intsum=0,n=100;/*執(zhí)行一次*/

sum=(1+n)*n/2;/*執(zhí)行一次*/

printf("%d",?sum);/*執(zhí)行一次*/

這個(gè)算法的運(yùn)行次數(shù)函數(shù)是f(n)=3瓣赂。根據(jù)我們推導(dǎo)大O階的方法,第一步就是把常數(shù)項(xiàng)3改為1片拍。在保留最高階項(xiàng)時(shí)發(fā)現(xiàn)煌集,它根本沒有最高階項(xiàng),所以這個(gè)算法的時(shí)間復(fù)雜度為O(1)捌省。

另外苫纤,我們?cè)囅胍幌屡瞎妫绻@個(gè)算法當(dāng)中的語(yǔ)句sum=(1+n)*n/2有10句盗冷,即:

intsum=0,?n=100;/*執(zhí)行一次*/

sum=(1+n)*n/2;/*執(zhí)行第1次*/

sum=(1+n)*n/2;/*執(zhí)行第2次*/

sum=(1+n)*n/2;/*執(zhí)行第3次*/

sum=(1+n)*n/2;/*執(zhí)行第4次*/

sum=(1+n)*n/2;/*執(zhí)行第5次*/

sum=(1+n)*n/2;/*執(zhí)行第6次*/

sum=(1+n)*n/2;/*執(zhí)行第7次*/

sum=(1+n)*n/2;/*執(zhí)行第8次*/

sum=(1+n)*n/2;/*執(zhí)行第9次*/

sum=(1+n)*n/2;/*執(zhí)行第10次*/

printf("%d",sum);/*執(zhí)行一次*/

事實(shí)上無(wú)論n為多少募胃,上面的兩段代碼就是3次和12次執(zhí)行的差異择浊,這種與問題的大小無(wú)關(guān)(n的多少)模燥,執(zhí)行時(shí)間恒定的算法恬偷,我們稱之為具有O(1)的時(shí)間復(fù)雜度在辆,又叫常數(shù)階规揪。

注意工闺,不管這個(gè)常數(shù)是多少横腿,我們都記作O(1),而不能是O(3)斤寂、O(12)等其他任何數(shù)字耿焊。這是初學(xué)者常常犯的錯(cuò)誤。

對(duì)于分支結(jié)構(gòu)而言遍搞,無(wú)論是真罗侯,還是假,執(zhí)行的次數(shù)都是恒定的溪猿,不會(huì)隨著n的變大而發(fā)生變化钩杰,所以單純的分支結(jié)構(gòu)(不包含在循環(huán)結(jié)構(gòu)中)纫塌,其時(shí)間復(fù)雜度也是O(1)。

2.4?線性階

循環(huán)結(jié)構(gòu)就會(huì)復(fù)雜很多讲弄。要確定某個(gè)算法的階次措左,我們常常需要確定某個(gè)特定語(yǔ)句或某個(gè)語(yǔ)句集運(yùn)行的次數(shù)。因此避除,我們要分析算法的復(fù)雜度怎披,關(guān)鍵就是要分析循環(huán)結(jié)構(gòu)的運(yùn)行情況。

下面這段代碼瓶摆,它的循環(huán)的時(shí)間復(fù)雜度為O(n)凉逛。因?yàn)檠h(huán)體中的代碼須要執(zhí)行n次。

inti;

for(i=0;?i

{

/*時(shí)間復(fù)雜度為O(1)的程序步驟序列*/

}

2.5?對(duì)數(shù)階

那么下面的這段代碼群井,時(shí)間復(fù)雜度又是多少呢状飞?

intcount=1;

while(count

{

count=count*2;

/*時(shí)間復(fù)雜度為O(1)的程序步驟序列*/

}

由于每次count乘以2之后,就距離n更近了一分书斜。也就是說(shuō)诬辈,有多少個(gè)2相乘后大于n,則會(huì)退出循環(huán)荐吉。由2x=n得到x=log2n焙糟。所以這個(gè)循環(huán)的時(shí)間復(fù)雜度為O(logn)。

2.6?平方階

下面的例子是一個(gè)循環(huán)嵌套稍坯,它的內(nèi)循環(huán)剛才我們已經(jīng)分析過(guò)酬荞,時(shí)間復(fù)雜度為O(n)。

inti,j;

for(i=0;?i

{

for(j=0;?j

{

/*時(shí)間復(fù)雜度為O(1)的程序步驟序列*/

}

}

而對(duì)于外層的循環(huán)瞧哟,不過(guò)是內(nèi)部這個(gè)時(shí)間復(fù)雜度為O(n)的語(yǔ)句混巧,再循環(huán)n次。所以這段代碼的時(shí)間復(fù)雜度為O(n2)勤揩。

如果外循環(huán)的循環(huán)次數(shù)改為了m咧党,時(shí)間復(fù)雜度就變?yōu)镺(m×n)。

inti,j;

for(i=0;?i

{

for(j=0;?j

{

/*時(shí)間復(fù)雜度為O(1)的程序步驟序列*/

}

}

所以我們可以總結(jié)得出陨亡,循環(huán)的時(shí)間復(fù)雜度等于循環(huán)體的復(fù)雜度乘以該循環(huán)運(yùn)行的次數(shù)傍衡。

那么下面這個(gè)循環(huán)嵌套,它的時(shí)間復(fù)雜度是多少呢负蠕?

inti,j;

for(i=0;?i

{

for(j=i;?j

{

/*時(shí)間復(fù)雜度為O(1)的程序步驟序列*/

}

}

由于當(dāng)i = 0時(shí)蛙埂,內(nèi)循環(huán)執(zhí)行了n次,當(dāng)i = 1時(shí)遮糖,執(zhí)行了n-1次绣的,……當(dāng)i = n-1時(shí),內(nèi)循環(huán)執(zhí)行了1次。所以總的執(zhí)行次數(shù)為

用我們推導(dǎo)大O階的方法屡江,第一條芭概,沒有加法常數(shù)不予考慮;第二條惩嘉,只保留最高階項(xiàng)罢洲,因此保留n2/2;第三條文黎,去除這個(gè)項(xiàng)相乘的常數(shù)惹苗,也就是去除1/2,最終這段代碼的時(shí)間復(fù)雜度為O(n2)臊诊。

從這個(gè)例子鸽粉,我們也可以得到一個(gè)經(jīng)驗(yàn)斜脂,其實(shí)理解大O推導(dǎo)不算難抓艳,難的是對(duì)數(shù)列的一些相關(guān)運(yùn)算,這更多的是考察你的數(shù)學(xué)知識(shí)和能力帚戳,所以想考研的朋友玷或,要想在求算法時(shí)間復(fù)雜度這里不失分,可能需要強(qiáng)化你的數(shù)學(xué)片任,特別是數(shù)列方面的知識(shí)和解題能力偏友。

我們繼續(xù)看例子,對(duì)于方法調(diào)用的時(shí)間復(fù)雜度又如何分析对供。

inti,j;

for(i=0;?i

{

function(i);

}

上面這段代碼調(diào)用一個(gè)函數(shù)function位他。

voidfunction(intcount)

{

print(count);

}

函數(shù)體是打印這個(gè)參數(shù)。其實(shí)這很好理解产场,function函數(shù)的時(shí)間復(fù)雜度是O(1)鹅髓。所以整體的時(shí)間復(fù)雜度為O(n)。

假如function是下面這樣的:

voidfunction(intcount)

{

intj;

for(j=count;?j

{

/*時(shí)間復(fù)雜度為O(1)的程序步驟序列*/

}

}

事實(shí)上京景,這和剛才舉的例子是一樣的窿冯,只不過(guò)把嵌套內(nèi)循環(huán)放到了函數(shù)中,所以最終的時(shí)間復(fù)雜度為O(n2)确徙。

下面這段相對(duì)復(fù)雜的語(yǔ)句:

n++;/*執(zhí)行次數(shù)為1*/

function(n);/*執(zhí)行次數(shù)為n*/

inti,j;

for(i=0;?i

{

function?(i);

}

for(i=0;?i

{

for(j=i;j

{

/*時(shí)間復(fù)雜度為O(1)的程序步驟序列*/

}

}

它的執(zhí)行次數(shù)

醒串,根據(jù)推導(dǎo)大O階的方法,最終這段代碼的時(shí)間復(fù)雜度也是O(n2)鄙皇。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末芜赌,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子伴逸,更是在濱河造成了極大的恐慌缠沈,老刑警劉巖,帶你破解...
    沈念sama閱讀 216,372評(píng)論 6 498
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異博烂,居然都是意外死亡香椎,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,368評(píng)論 3 392
  • 文/潘曉璐 我一進(jìn)店門禽篱,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)畜伐,“玉大人,你說(shuō)我怎么就攤上這事躺率÷杲纾” “怎么了?”我有些...
    開封第一講書人閱讀 162,415評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵悼吱,是天一觀的道長(zhǎng)慎框。 經(jīng)常有香客問我,道長(zhǎng)后添,這世上最難降的妖魔是什么笨枯? 我笑而不...
    開封第一講書人閱讀 58,157評(píng)論 1 292
  • 正文 為了忘掉前任,我火速辦了婚禮遇西,結(jié)果婚禮上馅精,老公的妹妹穿的比我還像新娘。我一直安慰自己粱檀,他們只是感情好洲敢,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,171評(píng)論 6 388
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著茄蚯,像睡著了一般压彭。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上渗常,一...
    開封第一講書人閱讀 51,125評(píng)論 1 297
  • 那天壮不,我揣著相機(jī)與錄音,去河邊找鬼凳谦。 笑死忆畅,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的尸执。 我是一名探鬼主播家凯,決...
    沈念sama閱讀 40,028評(píng)論 3 417
  • 文/蒼蘭香墨 我猛地睜開眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼如失!你這毒婦竟也來(lái)了绊诲?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 38,887評(píng)論 0 274
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤褪贵,失蹤者是張志新(化名)和其女友劉穎掂之,沒想到半個(gè)月后抗俄,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,310評(píng)論 1 310
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡世舰,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,533評(píng)論 2 332
  • 正文 我和宋清朗相戀三年动雹,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片跟压。...
    茶點(diǎn)故事閱讀 39,690評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡胰蝠,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出震蒋,到底是詐尸還是另有隱情茸塞,我是刑警寧澤,帶...
    沈念sama閱讀 35,411評(píng)論 5 343
  • 正文 年R本政府宣布查剖,位于F島的核電站钾虐,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏笋庄。R本人自食惡果不足惜效扫,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,004評(píng)論 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望无切。 院中可真熱鬧荡短,春花似錦丐枉、人聲如沸哆键。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,659評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)籍嘹。三九已至,卻和暖如春弯院,著一層夾襖步出監(jiān)牢的瞬間辱士,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,812評(píng)論 1 268
  • 我被黑心中介騙來(lái)泰國(guó)打工听绳, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留颂碘,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 47,693評(píng)論 2 368
  • 正文 我出身青樓椅挣,卻偏偏與公主長(zhǎng)得像头岔,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子鼠证,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,577評(píng)論 2 353

推薦閱讀更多精彩內(nèi)容