数据结构与算法01-算法的评估(大O表示法) 算法的优化方向

评估算法的方法

1. 算法的正确性, 可读性, 健壮性 (对不合理输入的反应能力和处理能力)
2. 时间复杂度: 估算程序指令的执行次数 (执行时间)
3. 空间复杂度: 估算所需占用的存储空间

大O表示法

数据规模n对应的复杂度
大O表示法的规则

1. 忽略常数, 系数, 低阶
   忽略常数: 对于15 , 统一用 O(1) 来表示
   忽略系数: 对于 5n+5, 用 O(n) 表示
   忽略低阶: 对于 n^5 + 2n + 6 , 用O(n^5) 来表示

对于对数: log2n , log9n 统称为logn

大O 表示法, 仅仅是一种粗略的分析模型, 是一种估算, 能帮助我们短时间内了解一个算法的时间复杂度.

常见的时间复杂度 :

不同算法的时间复杂度

数据规模较小时:

数据规模较大时:

算法优化的方向

1. 尽可能少的存储空间
2. 尽可能少的执行步骤 (执行时间)
3. 空间换时间 时间换空间