事后统计方法:必须依据算法实现编制好测试程序、通常需要花费大量的时间和精力。
事前分析估算方法:在计算机程序编写前、依据统计方法对算法进行估算。
运行时所耗时间依据:
1、算法代用的策略 方案
2、编译产生的代码质量(取决于编译器等因素)
3、输出规模
4、机器执行命令的速度(计算能力)
用计算的操作次数 可以粗略评估算法效率
比如 用 输入值大小 和 计算值大小 画出平面直角坐标系 图
分析输入次数和计算次数
顺带 可以忽略掉常量
3n+2
2n+3
比如比较如上2个算法的效率区别
其实在n的值非常大的情况下 后面的小常量 基本可以忽略
与最高次项相乘的常数也并不重要、也可以忽略
结论、判断一个算法的效率时、函数中的常数和其他次要项可以忽略、
更应该关注主项(最高项)的阶数
No Leanote account? Sign up now.