复杂度分析

这是学习 ADS(算法和数据结构)的第一篇文章。

这篇文章主要总结如何应用『复杂度分析』,提升算法性能。

定义

复杂度分为空间复杂度时间复杂度。时间复杂度又分为最好、最坏、平均、均摊时间复杂度。

  • 大 O 复杂度表示法(时间复杂度):时间随数据规模的变化趋势
  • 空间复杂度:空间随数据规模的增长关系
  • 时间复杂度分析
    • 只关注循环次数最多的代码
    • 加法法则
    • 乘法法则
  • 空间复杂度分析

常见时间复杂度

  • $O(1)$
  • $O(logn)$、$O(nlogn)$
  • $O(m+n)$、$O(m*n)$

应用

例子一


参考资料