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

GrowthofFunction Asymptoticnotation 举例 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 SinceO notationdescribesanupperbound whenweuseittoboundtheworst caserunningtimeofanalgorithm wehaveaboundontherunningtimeofthealgorithmoneveryinput Thus theO n2 boundonworst caserunningtimeofinsertionsortalsoappliestoitsrunningtimeoneveryinput The n2 boundontheworst caserunningtimeofinsertionsort however doesnotimplya n2 boundontherunningtimeofinsertionsortoneveryinput Forexample wesawinChapter2thatwhentheinputisalreadysorted insertionsortrunsin n time 根据记号 的定义 用它评估算法的复杂性 得到的只是当规模充分大时的一个上界 这个上界的阶越低则评估就越精确 结果就越有价值 用 评估算法的复杂性 得到的只是该复杂性的一个下界 这个下界的阶越高 则评估就越精确 结果就越有价值 明白了记号 和 之后 记号 将随之清楚 因为我们定义f N g N 则f N g N 且f N g N 这时 我们说f N 与g N 同阶 notation Math g n f n thereexistpositiveconstantsc1 c2 andn0suchthat0 c1g n f n c2g n foralln n0 Asymptoticperformance Whenngetslargeenough a n2 algorithmalwaysbeatsa n3 algorithm Asymptoticperformance Weshouldnotignoreasymptoticallysloweralgorithms however Real worlddesignsituationsoftencallforacarefulbalancingofengineeringobjectives Asymptoticanalysisisausefultooltohelptostructureourthinking Conclusions nlgn growsmoreslowlythan n2 Therefore mergesortasymptoticallybeatsinsertionsortintheworstcase Inpractice mergesortbeatsinsertionsortforn 30orso Gotestitoutforyourself 实验1 结论 对于低效的算法 计算机的计算速度成倍乃