邓俊辉<<数据结构>>-公开课-01-C

发表于

渐进分析: 大O记号

好读书不求甚解。

考察DSA（考察人）:

  • 长远
  • 主流,

渐进分析(Asymptotic Analysis) n >> 2, 对于规模为n输入，算法

  • 需要执行的基本操作数: T(n) = ?
  • ..存储单元: S(n) = ? // 通常不考虑？教材

教材P33

  • 空间复杂度不会超过常数规模，纵然是新开辟的，算法所需的空间总量，也不过与基本操作的次数同阶。从这个意义上，时间复杂度是空间复杂度的天然上限。
  • 但两种情况下会有意义:
    • 对空间效率也异常在乎(时间复杂度的平凡上界难以令人满意)
    • 数据的输入规模大。

big-O()比T(n), f(n)更简洁，但依然反应增长趋势(长远)

  • 常系数可忽略(主流):O(f(n)) = O(c*f(n))
  • 低次项可忽略(主流)

O(1)
常数

  • 2 = 2013 = 2013*2013 = O(1)
  • 效率: 最高效
  • 出现的情况，需要具体分析
    不含循环，不含分支转向，一定不能有(递归)调用？
    教材

O(logn)
对数

  • 常底数无所谓
  • 常数次幂无所谓
  • 多项式
  • 效率: 接近于常数

O(n^c)
多项式

  • 一般 取最高次
    线性：所有O(n)函数
    从O(n)到O(n^2):编程习题主要覆盖范围
    效率: 已经可令人满意。

O(2^n)
指数
效率: 算法成本增长极快，通常不可忍受。
n^x->2^n, 是从有效算法到无效算法的分水岭。

2-Subset
直觉算法：逐一枚举S的每一个子集，并统计其中元素总和
定理:2-Subset is NP-complete
意即:就目前模型而言，不存在在多项式时间内回答此问题的算法。
除非，添加条件：分布规律啦, 票的总数啦，

复杂度增长速度表格。