1.2.2 算法效率的度量
原书定位
印刷页P5起,对应PDF第17页。下文为目视整理的知识提要;完整内容见原书对照。
基本操作的执行次数刻画运行时间。顺序执行的复杂度取较大的数量级;嵌套循环应按实际次数求和,只有循环次数相互独立时才能直接相乘。
- 给出渐近上界;严格的同阶界用 。教材习题常以大 O 书写主导数量级。
- 平均复杂度是给定输入分布下的期望,不必一概假定所有输入等概率;最坏复杂度给出最差情况下的保证。
- 空间复杂度通常计额外辅助空间,递归还要计算调用栈。原地工作指辅助空间为 。
- 倍增或折半循环常为对数级;三角形嵌套通常用等差求和;递归用递推式或递归树分析。
对应练习
关联知识
- 1.2 算法和算法评价
- 4.2.2 串的模式匹配算法——KMP算法
- 5.5.2 并查集
- 5.5.2.1 并查集的优化
- 7.1 查找的基本概念
- 8.1.1 排序的定义与稳定性
- 8.6.1 内部排序算法的比较
原书对照
展开原书对照截图

