学习目标
- 掌握算法复杂度相关概念
- 熟悉常见的时间复杂度实例
- 掌握平均复杂度, 均摊复杂度等概念
打卡
打卡day01:
今天学习: 数据结构与算法之复杂度分析
收获: 理解算法复杂度的意义, 相关概念以及分析方式
数据结构和算法的目的, 是写出计算时间更短(快)且占用内存空间更少(省)的程序.
为了能够在忽略所有外在条件的情况下, 粗略地估计一段代码的执行效率问题, 所以才有了复杂度分析.
复杂度
复杂度可分为时间复杂度和空间复杂度.
- 时间复杂度, aka, 渐近时间复杂度, 计算的是代码执行时间随数据规模增长而变化的关系.
常用的时间复杂度有: O(1), O(log(n)), O(n), O(nlog(n)), O(n2) - 空间复杂度, aka, 渐近空间复杂度, 计算的是代码占用内存空间随数据规模增长而变化的关系.
空间复杂度比较简单, 常常复杂度的讨论是指时间复杂度.
区分复杂度
在不同输入情况下, 一段代码的执行效率可能并不总是相同.
对一个数组进行排序, 其时间复杂度不会发生变化, 但是对于在一个数组中进行查找, 随着查找元素的不同, 其查找效率会随着查找条件而发生改变.
因此, 对于这种不稳定的复杂度分析, 有了最好情况时间复杂度, 最坏情况时间复杂度和(加权)平均时间复杂之间的区分.
还有一种采用摊还分析的均摊时间复杂度.
例如一个大部分情况下, 某段代码执行效率为 O(1), 但是在有规律的间隔 n 下, 其时间复杂度会变为 O(n); 当这次特殊的执行时间分摊到所有 n 次执行的总时间中, 其整体时间复杂则为 O(1), 也即均摊时间复杂度.
均摊时间复杂度其实并不多见.
复杂度是个很重要的概念, 在平时习惯中就要去有意识地分析代码的复杂度几何.