数据结构与算法01-算法的评估(大O表示法) 算法的优化方向
文章目录
- 评估算法的方法
- 大O表示法
- 算法优化的方向
评估算法的方法
- 算法的正确性, 可读性, 健壮性 (对不合理输入的反应能力和处理能力)
- 时间复杂度: 估算程序指令的执行次数 (执行时间)
- 空间复杂度: 估算所需占用的存储空间
大O表示法
数据规模n对应的复杂度
大O表示法的规则
- 忽略常数, 系数, 低阶
忽略常数: 对于15 , 统一用 O(1) 来表示
忽略系数: 对于 5n+5, 用 O(n) 表示
忽略低阶: 对于 n^5 + 2n + 6 , 用O(n^5) 来表示
对于对数: log2n , log9n 统称为logn
大O 表示法, 仅仅是一种粗略的分析模型, 是一种估算, 能帮助我们短时间内了解一个算法的时间复杂度.
常见的时间复杂度 :
不同算法的时间复杂度
数据规模较小时:
数据规模较大时:
算法优化的方向
- 尽可能少的存储空间
- 尽可能少的执行步骤 (执行时间)
- 空间换时间 时间换空间