复杂度
复杂度是对一段代码消耗的资源的评估，包括空间和时间上。
- 时间复杂度与代码结构设计高度相关
- 空间复杂度与选用的数据结构高度相关
复杂度的函数表示
如果我们用 f(n) 来表示一个函数或者一段功能代码的话，那么用 O(f(n)) 来表示这段代码的复杂度
- O(n) 表示的就是复杂度和计算实例的个数线性相关
- O(lgn) 表示就是复杂度和计算实例的个数对数相关
复杂度与具体的常量系数无关
例如 O(2n) 与 O(n) 表示的是相同的复杂度 O(2n) = O(n + n) = O(n) + O(n)
O(2n) 表示的仅仅是一段复杂度为 O(n) 的代码先后执行两次
多项式的复杂度相加时，选用高的作为结果
例如 O(n²) + O(n) = O(n² + n) = O(n²)
因为随着变化率的增大，2阶多项式部分的变化率要远大于1阶
O(1) 表示一个特别的复杂度
与输入的 n 无关，使用算法使用有限可数的资源
减少时间复杂度的方法论
- 暴力解法。在不考虑时间和空间的约束下，完成功能。
- 剔除冗余。审查代码，将其中无效的计算和存储剔除。（递归，二分，排序，动态规划）
- 时空转换。设计合理的数据结构，完成时间复杂度向空间复杂度的转移。（针对问题进行细分，选择合适的数据结构）
网友评论