复杂度分析

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

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

定义

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

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

常见时间复杂度

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

应用

例子一

参考资料：