算法的复杂度分析
1 算法效率的度量
1.1 算法效率度量的方法
思考：如果两个算法都满足功能性需求，那工程中最关心的其它特性是什么？如何比较评判呢？
注意：性价比（比率）是工程中最关注的算法附件特性！
算法效率度量的方法主要分为两种：事后统计法和事前分析估算法。
1.2 事后统计法
比较不同算法对同一组输入数据的运行处理时间。
缺陷：
- 为了获得不同算法的运行时间必须编写相应程序。
- 运行时间严重依赖硬件以及运行时的环境因素。
- 算法的测试数据的选取相当困难。
事后统计法不容易准确度量算法的效率。
1.3 事前分析估算法
依据统计的方法对算法效率进行估算。
影响算法效率的主要因素：
- 算法采用的策略和方法。
- 问题的输入规模。
- 编译器所产生的代码。
- 计算机执行速度。
事前分析估算法通过操作数量度量算法效率。
判断一个算法效率时只需要关注最高阶项就能得出结论。某个算法，随着问题规模n的增大，它会越来越优于另一个算法，或者越来越差于另一个算法。
参考资料：