C++高级_数据结构

算法特性

输入: 算法具有0个或多个输入

输出: 算法至少有1个或多个输出

有穷性: 算法在有限的步骤之后会自动结束而不会无限循环,并且每一个步骤可以在接收的实际内完成

确定性:算法中的每一步都有确定的含义,不会出现二义性

可行性:算法的每一步都是可行的,也就是说每一步都能够执行有限的次数完成。

效率的度量方法:

事后统计法

统计方法

比较不同算法对同一组输入数据的运行处理时间。

缺陷

为了获得不同算法的运行时间必须编写相应程序

运行时间严重依赖硬件以及运行时的环境因素

算法的测试数据的选取相当困难

总结

事后统计法虽然直观,但是实施困难且缺陷多

事前分析估算

统计方法:

依据统计的方法对算法效率进行估算

影响算法效率的主要因素:

算法采用的策略和方法

问题的输入规模

编译器所产生的代码

计算机执行速度

  1. 怎么判断一个算法的效率???(规则如下)

判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要项和常数项可以忽略。

在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度。

只有常数项记做1

操作数量的估算可以作为时间复杂度的估算

暂无评论

发表评论