对于一个特定的问题,采用的数据结构不同,其设计的算法一般也不同,即使在同一种数据结构下,也可以采用不同的算法。那么,对于解决同一问题的不同算法,选择哪一种算法比较合适,以及如何对现有的算法进行改进,从而设计出更适合于数据结构的算法,这就是算法效率的度量问题。评价一个算法优劣的主要标准如下:
1. 正确性(Correctness)算法的执行结果应当满足预先规定的功能和性能的要求,这是评价一个算法的最重要,也是最基本的标准。算法的正确性还包括对于输入、输出处理的明确而无歧义的描述。
2. 可读性(Readability)算法主要是为了人阅读和交流,其次才是机器的执行。所以,一个算法应当思路清晰,层次分明,简单明了,易读易懂。即使算法已转变成机器可执行的程序,也需要考虑人能较好地阅读理解。同时,一个可读性强的算法也有助于对算法中隐藏错误的排除和算法的移植;
3. 健壮性(Robustness)一个算法应该具有很强的容错能力,当输入不合法的数据时,算法应当能做适当的处理,使得不至于引起严重的后果。健壮性要求表明算法要全面细致地考虑所有可能出现的边界情况和异常情况,并对这些边界情况和异常情况做出妥善的处理,尽可能使算法没有意外的情况发生。
4. 运行时间(Running Time)运行时间是指算法在计算机上运行所花费的时间,它等于算法中每条语句执行时间的总和。对于同一个问题如果有多个算法可供选择,应尽可能选择执行时间短的算法。一般来说,执行时间越短,性能越好;
5. 占用空间(Storage Space)占用空间是指算法在计算机上存储所占用的存储空间,算法占用的存储空间是指算法执行过程中所需要的最大存储空间,对于一个问题如果有多个算法可供选择,应尽可能选择存储量需求低的算法
- 基础
- 数据
- 数据元素
- 数据结构
- 集合结构
- 线性结构
- 树型结构
- 图状结构
- 数据存储结构
- 算法定义
- 算法效率度量
- 算法效率分析
- 时间复杂度
- O(1)
- O(n)
- O(n2)
- O(logn)
- 空间复杂度
- 线性表
- 数组
- 链表
- 串矩阵和广义表
- 串
- 矩阵
- 广义表
- 栈和队列
- 栈
- 队列
- 树和二叉树
- 二叉树
- 满二叉树
- 完全二叉树
- 哈夫曼树
- 二叉查找树-BST树
- AVL树
- 红黑树
- B树
- B+树
- 字典树
- 跳表
- 算法
- 排序算法
- 冒泡排序
- 选择排序
- 快速排序
- 插入排序
- 希尔排序
- 归并排序
- 堆排序
- 基数排序
- 计数排序
- 桶排序
- 查找算法
- 二分查找算法
- Hash算法
- 一致性hash算法
- 算法题
- 001-用两个栈实现队列
- 002-只使用栈和递归逆序一个栈
- 附录
- SkipList跳表