第3章 算法的渐近分析
发布网友
发布时间：2023-05-22 07:53
共1个回答
热心网友
时间：2024-12-02 10:20
有了算法运行时间的增长阶，不仅可以简单的描述算法的效率，而且可以比较算法间的相对性能。比如一旦输出规模n变得足够大，具有最坏情形运行时间 的归并排序就从效率上超过具有最坏情形运行时间 的插入排序。
虽然可确定一个算法的精确运行时间，但是不值得付出努力来计算额外精度。因为对于大规模输入来说，在精确运行时间里的常系数和低阶项可被输入规模自身的影响所控制。所以只需要关心算法的运行时间在规模足够大时的增长阶，即分析当输入规模增长到无穷大时，算法的运行时间是如何增长的，这就是算法的渐近分析。
通常，对于除小规模输入外的所有输入来说，一个渐近意义上更有效率的算法就是最佳选择。
本章给出了若干种用于简化算法渐近分析的方法，主要内容有：
