算法分析4(MIT)英文版

第一页第二页，共21页。举例：(1)因为对所有的N≥1有3N≤4N，我们有3N=Ο(N)；(2)因为当N≥1时有N+1024≤1025N，我们有N+1024=Ο(N)；(3)因为当N≥10时有2N2+11N-10≤3N2，我们有2N2+11N-10=Ο(N2)；(4)因为对所有N≥1有N2≤N3，我们有N2=Ο(N3)；(5)作为一个反例N3≠Ο(N2)。因为若不然，则存在正的常数C和自然数N0，使得当N≥N0时有N3≤CN2，即N≤C。显然当取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页。

根据记号Ο的定义，用它评估算法的复杂性，得到的只是当规模充分大时的一个上界。这个上界的阶越低则评估就越精确，结果就越有价值。用Ω评估算法的复杂性，得到的只是该复杂性的一个下界。这个下界的阶越高，则评估就越精确，结果就越有价值。

第七页第八页，共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页。结论：

对于低效的算法，计算