算法分析4(MIT)英文版

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

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

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

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

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

對于低效的算法，計算