数据结构：一组数据的存储结构 算法:一组操作数据的方法

时间复杂度：时间复杂度不表示具体的代码执行时间，而是表示代码执行时间随随数据规模增长的变化趋势，而公式中的常数、系数、低阶并不能左右变化趋势，因此可以忽略不计，只需要记录最大量级就可以了。

时间复杂度分类

  • 多项式复杂度：
    • 常量级O(1)：一般情况下，代码中不出现循环、递归
    • 对数级O(logn)
    • 线性级O(n)
    • 线性对数级O(nlogn)
    • 平方级O(n)
  • 非多项复杂度(复杂度随n增大会急剧增大，因此非常低效)
    • 指数级O(2)
    • 阶乘级O(n!)

空间复杂度：算法的存储空间随数据规模增长的变化趋势。

空间复杂度分类：

  • O(1)
  • O(n)
  • O(n)

复杂度分析：

  • 最好情况时间复杂度
  • 最坏情况时间复杂度
  • 平均情况时间复杂度：加权时间复杂度
  • 均摊时间复杂度：特殊的平均复杂度情况（ps:不是很理解）