复杂度分析
这是学习 ADS(算法和数据结构)的第一篇文章。
这篇文章主要总结如何应用『复杂度分析』,提升算法性能。
定义
复杂度分为空间复杂度和时间复杂度。时间复杂度又分为最好、最坏、平均、均摊时间复杂度。
- 大 O 复杂度表示法(时间复杂度):时间随数据规模的变化趋势
- 空间复杂度:空间随数据规模的增长关系
- 时间复杂度分析
- 只关注循环次数最多的代码
- 加法法则
- 乘法法则
- 空间复杂度分析
常见时间复杂度
- $O(1)$
- $O(logn)$、$O(nlogn)$
- $O(m+n)$、$O(m*n)$
应用
例子一
参考资料: