算法复杂的度的基本概念和结论

复杂度

复杂度是对一段代码消耗的资源的评估，包括空间和时间上。

• 时间复杂度与代码结构设计高度相关
• 空间复杂度与选用的数据结构高度相关

复杂度的函数表示

如果我们用 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 无关，使用算法使用有限可数的资源

减少时间复杂度的方法论

1. 暴力解法。在不考虑时间和空间的约束下，完成功能。
2. 剔除冗余。审查代码，将其中无效的计算和存储剔除。（递归，二分，排序，动态规划）
3. 时空转换。设计合理的数据结构，完成时间复杂度向空间复杂度的转移。（针对问题进行细分，选择合适的数据结构）