复杂度分析
如何分析，统计算法的执行效率和资源消耗
- 测试结果非常依赖测试环境
- 测试结果受数据规模的影响很大
大O复杂度表示法
所有代码的执行时间T(n)与每行代码的执行次数n成正比
大O公式：T(n) = (f(n))
- 大O时间复杂度实际上并不是具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫作渐进时间复杂度（asymptotic space complexity），简称为时间复杂度。
时间复杂度分析
- 只关注循环执行次数最多的一段代码
- 加法法则：总复杂度等于量级最大的那段代码的复杂度
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
O(1)
- 一般情况下，只要不存在循环语句，递归语句，即使有成千上万行的代码，其时间复杂度也是O(1)
O(logn),O(nlogn)
$$
对数之间可以相互转化的\log3_n 就等于\log3_2\log2_n,所以O(\log3_n)=O(C\log2_n),其中 C=\log3_2 是一个常量。
$$
在采用大O标记复杂度的时候，可以忽略系数，即O(Cf(n))=O(f(n))。
$$
因此，O(\log2_n)就等于O(\log3_n)。因此，在对数阶时间复杂度的表达方法里，我们忽略对数的“底”，统一表示为O(logn)
$$
- 当一段代码的时间复杂度为O(logn)，将循环执行n遍，时间复杂度就是O(nlogn)，比如，归并排序，快速排序的时间都是O(nlogn)。
O(m+n)，O(m*n)
- m和n是表示两个数据规模。当无法事先评估m和n谁的量级大，所以我们在表示复杂度的时候，就不能简单利用加法法则而省略其中一个。所以，时间复杂就为O(m+n)。
时间复杂度最好，最坏，平均，均摊分析
最好，最坏情况时间复杂度
平均情况复杂度
均摊时间复杂度
- 摊还分析法