数据结构和算法–效率的度量方法

算法效率度量方法

事后统计方法

简介&＃xff1a; 类似利用计时器对不同的算法的运行时间进行比较&＃xff0c;时间短的效率高。

**优点&＃xff1a;**容易理解&＃xff0c;实现不难

缺陷&＃xff1a;

• 测试程序需要提前编写&＃xff0c;需要花费不少时间
• 不同的设计环境的效果差别大

前分析方法

简介&＃xff1a; 编写程序前&＃xff0c;利用统计的方法对算法进行估计。

影响时间效率取决与一下的几个因素

• 算法采用的策略&＃xff0c;方案&＃xff08;重点&＃xff09;
• 编译器编译产生代码的质量
• 问题的输入规模
• 机器执行指令的效率

将算法复杂度进行抽象&＃xff1a;这个是分析算法时间一个重要的方法&＃xff0c;只需要知道算法执行次数的数量级即可。数量级越低&＃xff0c;
算法越好。

注意&＃xff1a;不需要看判断指令&＃xff0c;只需要看执行多少次&＃xff0c;只需要看数量级。&＃xff08;2n&＃43;3和n²&＃43;4&＃xff0c;中只看数量级&＃xff0c;前者是1&＃xff0c;后者是2&＃xff0c;不用管前面的系数和后面的系数&＃xff0c;因为总体而言影响不大&＃xff09;
。
例子&＃xff1a;

算法一执行n次&＃xff0c;算法二&＃xff0c;执行1次&＃xff0c;也就是数量级是n的一次方和n的0次方进行比较&＃xff0c;在同一条件下&＃xff0c;算法二比算法一优秀。

这篇是为下一篇算法时间复杂度做铺垫。