算法分析4(MIT)英文版.ppt

《算法分析4(MIT)英文版.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、GrowthofFunctionAsymptoticnotation举例：(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)时这个不等式不

2、成立，所以N3≠Ο(N2)。SinceO-notationdescribesanupperbound,whenweuseittoboundtheworst-caserunningtimeofanalgorithm,wehaveaboundontherunningtimeofthealgorithmoneveryinput.Thus,theO(n2)boundonworst-caserunningtimeofinsertionsortalsoappliestoitsrunningtimeoneveryinput.TheΘ(n2)bou

3、ndontheworst-caserunningtimeofinsertionsort,however,doesnotimplyaΘ(n2)boundontherunningtimeofinsertionsortoneveryinput.Forexample,wesawinChapter2thatwhentheinputisalreadysorted,insertionsortrunsinΘ(n)time.根据记号Ο的定义，用它评估算法的复杂性，得到的只是当规模充分大时的一个上界。这个上界的阶越低则评估就越精确，结果就越有价值。用Ω

4、评估算法的复杂性，得到的只是该复杂性的一个下界。这个下界的阶越高，则评估就越精确，结果就越有价值。明白了记号Ο和Ω之后，记号θ将随之清楚，因为我们定义f(N)=θ(g(N))则f(N)=Ο(g(N))且f(N)=Ω(g(N))。这时，我们说f(N)与g(N)同阶。Θ-notationMath:Θ(g(n))={f(n):thereexistpositiveconstantsc1,c2,andn0suchthat0≤c1g(n)≤f(n)≤c2g(n)foralln≥n0}AsymptoticperformanceWhenngetsl

5、argeenough,aΘ(n2)algorithmalwaysbeatsaΘ(n3)algorithm.Asymptoticperformance•Weshouldnotignoreasymptoticallysloweralgorithms,however.•Real-worlddesignsituationsoftencallforacarefulbalancingofengineeringobjectives.•Asymptoticanalysisisausefultooltohelptostructureourthinki

6、ng.Conclusions•Θ(nlgn)growsmoreslowlythanΘ(n2).Therefore,mergesortasymptoticallybeatsinsertionsortintheworstcase.•Inpractice,mergesortbeatsinsertionsortforn>30orso.•Gotestitoutforyourself!(实验1）结论：对于低效的算法，计算机的计算速度成倍乃至数10倍地增长基本上不带来求解规模的增益。因此，对于低效算法要扩大解题规模，不能寄希望于移植算法到高速的计

7、算机上，而应该把着眼点放在算法的改进上。作业：证明：