什么是复杂度分析?
- 数据结构和算法解决的是如何让计算机
更快、更省空间的执行。 - 因此需要从两个方面评估数据结构和算法的优越性。
- 分别用时间复杂度和空间复杂度两个概念来描述性能问题,二者统称为复杂度。
- 复杂度描述的是算法的执行时间或者占用空间的大小与数据规模增长关系。
为什么需要复杂度分析?
- 和性能测试相比,复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强。
- 掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。
如何进入复杂度分析？
大O表示法：就是在不用运行代码的情况下，用“肉眼” 得出一段代码的执行时间。
- 来源：算法的执行时间与每行代码的执行次数成正比，用 T(n) = O(f(n)) 表示，其中 T(n) 表示算法执行总时间，f(n) 表示代码执行总次数，而 n 往往表示数据的规模。
- 特点：以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以“常量阶”、低阶、系数实际上对这种趋势不产生决定性影响，所以在做时间复杂度分析时可以忽略这些项；只需要记录一个最大量级就可以了。
- 大O 时间复杂度并不是实际代码真正的运行时间，而是表示代码执行时间岁数据规模增长的变化趋势；所以时间复杂度也叫
进时间复杂度。
总结：所有代码的执行时间 T(n) 与每行代码的执行次数n成正比; 总结公式: T(n) = O(f(n))
时间复杂度分析
- 只关注
循环次数最多的一段代码。 - 加法法则：总复杂度等于
量级最大的那段代码的复杂度; 总结公式: T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))) - 乘法法则: 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积; 总结公式: T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)*g(n))
- 多规模求加法: 比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。
复杂度量级（按数量级递增）
-
多项式阶
- 常量阶 O(1)
- 对数阶 O(logn)
- 线性阶 O(n)
- 线性对数阶 O(nlogn)
- 平方阶 O(n2)、立方阶 O(n3) ... k 次阶 O(nk)
-
非多项式
- 指数阶 O(2n)
- 阶乘阶 O(n!)
复杂度量级
空间复杂度分析
空间和复杂度和时间复杂度分析方法基本类似，表示算法的存储空间与数据规模之间的增长关系。
