渐进分析: 大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
意即:就目前模型而言,不存在在多项式时间内回答此问题的算法。
除非,添加条件:分布规律啦, 票的总数啦,
复杂度增长速度表格。