算法分析4(MIT)英文版

第一頁(yè)第二頁(yè)，共21頁(yè)。舉例：(1)因?yàn)閷?duì)所有的N≥1有3N≤4N，我們有3N=Ο(N)；(2)因?yàn)楫?dāng)N≥1時(shí)有N+1024≤1025N，我們有N+1024=Ο(N)；(3)因?yàn)楫?dāng)N≥10時(shí)有2N2+11N-10≤3N2，我們有2N2+11N-10=Ο(N2)；(4)因?yàn)閷?duì)所有N≥1有N2≤N3，我們有N2=Ο(N3)；(5)作為一個(gè)反例N3≠Ο(N2)。因?yàn)槿舨蝗?，則存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N≥N0時(shí)有N3≤CN2，即N≤C。顯然當(dāng)取N=max(N0,[C]+l)時(shí)這個(gè)不等式不成立，所以N3≠Ο(N2)。第二頁(yè)第三頁(yè)，共21頁(yè)。SinceO-notationdescribesanupperbound,whenweuseittoboundtheworst-caserunningtimeofanalgorithm,wehaveaboundontherunningtimeofthealgorithmoneveryinput.Thus,theO(n2)boundonworst-caserunningtimeofinsertionsortalsoappliestoitsrunningtimeoneveryinput.TheΘ(n2)boundontheworst-caserunningtimeofinsertionsort,however,doesnotimplyaΘ(n2)boundontherunningtimeofinsertionsortoneveryinput.Forexample,wesawinChapter2thatwhentheinputisalreadysorted,insertionsortrunsinΘ(n)time.第三頁(yè)第四頁(yè)，共21頁(yè)。第四頁(yè)第五頁(yè)，共21頁(yè)。第五頁(yè)第六頁(yè)，共21頁(yè)。第六頁(yè)第七頁(yè)，共21頁(yè)。

根據(jù)記號(hào)Ο的定義，用它評(píng)估算法的復(fù)雜性，得到的只是當(dāng)規(guī)模充分大時(shí)的一個(gè)上界。這個(gè)上界的階越低則評(píng)估就越精確，結(jié)果就越有價(jià)值。用Ω評(píng)估算法的復(fù)雜性，得到的只是該復(fù)雜性的一個(gè)下界。這個(gè)下界的階越高，則評(píng)估就越精確，結(jié)果就越有價(jià)值。

第七頁(yè)第八頁(yè)，共21頁(yè)。明白了記號(hào)Ο和Ω之后，記號(hào)θ將隨之清楚，因?yàn)槲覀兌xf(N)=θ(g(N))則f(N)=Ο(g(N))且f(N)=Ω(g(N))。這時(shí)，我們說(shuō)f(N)與g(N)同階。第八頁(yè)第九頁(yè)，共21頁(yè)。Θ-notationMath:Θ(g(n))={f(n):thereexistpositiveconstantsc1,c2,andn0suchthat0≤c1g(n)≤f(n)≤c2g(n)foralln≥n0}第九頁(yè)第十頁(yè)，共21頁(yè)。第十頁(yè)第十一頁(yè)，共21頁(yè)。第十一頁(yè)第十二頁(yè)，共21頁(yè)。第十二頁(yè)第十三頁(yè)，共21頁(yè)。第十三頁(yè)第十四頁(yè)，共21頁(yè)。第十四頁(yè)第十五頁(yè)，共21頁(yè)。AsymptoticperformanceWhenngetslargeenough,aΘ(n2)algorithmalwaysbeatsaΘ(n3)algorithm.第十五頁(yè)第十六頁(yè)，共21頁(yè)。Asymptoticperformance?

Weshouldnotignoreasymptoticallysloweralgorithms,however.?Real-worlddesignsituationsoftencallforacarefulbalancingofengineeringobjectives.?Asymptoticanalysisisausefultooltohelptostructureourthinking.第十六頁(yè)第十七頁(yè)，共21頁(yè)。Conclusions?

Θ(nlgn)growsmoreslowlythanΘ(n2).Therefore,mergesortasymptoticallybeatsinsertionsortintheworstcase.?Inpractice,mergesortbeatsinsertionsortforn>30orso.?Gotestitoutforyourself!(實(shí)驗(yàn)1）第十七頁(yè)第十八頁(yè)，共21頁(yè)。第十八頁(yè)第十九頁(yè)，共21頁(yè)。結(jié)論：

對(duì)于低效的算法，計(jì)算