Chap 5 算法的效率.ppt

算法的效率 算法效率的度量 在选择算法时，要考虑效率 算法效率分析的重点是效率的差异—仅通过较好的解题方法就可获得的差异，而不是依靠编码采用的技巧获得的差异 时间和内存的有效利用也很重要 如何比较解决相同问题的两个算法的时间效率：分别编个程序运行？ 如何编码？ 使用什么样的计算机？ 使用什么样的数据？ 算法执行时间的确定 对操作进行计数 对主要操作进行计数 比较解决大型问题的效率，而不是小型问题 数量级表示 O(1) O(log n) O(n) O(n log n) O(n2) O(n3) .. O(2n) 考虑最坏的情况和平均情况 在选择数据结构的实现方法时 应考虑具体操作出现的频率 一般来说使用频率高的应该高效率的 某些使用少的操作也需要高效率的 不要过分追求高效率 常用排序算法的比较 最差情况 平均情况 选择、冒泡 n2 n2 插入 n2 n2 归并 n log n n log n 快速 n2 n log n 基数 n n 堆 n log n n log n 考虑下空间的需要 * *