2.1 计算复杂性函数的阶

2.1.1 增长的阶

  • 增长函数用于描述阶
  • 阶用于描述增长率快慢
  • 增长率用于衡量算法效率

  • 忽略低阶项，保留高阶项，忽略常系数

    2.1.2 增长函数

  • 渐进效率

    • 输入规模非常大
    • 忽略低阶项和常系数
    • 只考虑高阶

  • 增长记号：Ο、Θ、Ω、ω、ο

    2.1.3 同阶函数集合

  • 同阶描述的是当 n 足够大时，函数增长率之间的关系

    image.png

2.1.4 低阶函数集合

  1. ![image.png](https://cdn.nlark.com/yuque/0/2020/png/632230/1583212322521-47e01655-acc0-454c-b231-29ef2606039b.png#align=left&display=inline&height=343&name=image.png&originHeight=686&originWidth=966&size=307579&status=done&style=none&width=483)

2.1.5 Θ(g(n))与Ο(g(n))之间的关系

  1. ![image.png](https://cdn.nlark.com/yuque/0/2020/png/632230/1583212557377-02ded2bf-1bcd-4868-a420-789fcfe23815.png#align=left&display=inline&height=210&name=image.png&originHeight=420&originWidth=636&size=167286&status=done&style=none&width=318)

2.1.6 高阶函数集合

image.png

2.1.7 Ο、Θ、Ω的关系

image.png

2.1.8 严格低阶函数

image.png

2.1.9 严格高阶函数集合

image.png

2.1.10 五个记号的性质

image.png

2.2 和式的估计与界限

  • 线性和

image.png

  • 级数

    image.png
    image.png

    2.3 递归方程

  • 递归方程：使用小的输入值来描述一个函数的方程或不等式。

  • 求解递归方程的三个主要方法
    • 替换方法
      • 首先猜想
      • 然后用数学归纳法证明
    • 迭代方法
      • 把方程转换为一个和式
      • 然后用估计和的方法求解
    • Master定理方法
      • 求解型为 T(n)=aT(n/b)+f(n)的递归方程