为什么需要复杂度分析？

• 1.测试结果非常依赖测试环境
• 2.测试结果受数据规模的影响很大

所以，我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。

大O时间复杂度表示法

大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

时间复杂度分析

• 1.只关注循环执行次数最多的一段代码
• 2.加法法则：总复杂度等于量级最大的那段代码的复杂度
• 3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

复杂度量级

• 常量阶O(1)
• 对数阶O(logn)
• 线性阶O(n)
• 线性对数阶O(nlogn)
• 平方阶O(n^{2)、立方阶O(n}3)…k次方阶O(n^k)
• 指数阶O(2^n)
• 阶乘阶O(n!)

复杂度两级可以粗略分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2^n)和O(n!)。当数据规模n越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。

1.O(1)

首先你必须明确一个概念，O(1)只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。只要代码的执行时间不随n的增大而增长，这样代码的时间复杂度我们都记作O(1)。或者说，一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。

2.对数阶O(logn)、O(nlogn)

不管是以2为底、以3为底，还是以10为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。
如果一段代码的时间复杂度是O(logn)，我们循环执行n遍，时间复杂度就是O(nlogn)了。而且，O(nlogn)也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是O(nlogn)。

3.O(m+n)、O(m*n)

代码的复杂度由两个数据的规模来决定。我们无法事先评估m和n谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，时间复杂度就是 O(m+n)。

空间复杂度分析

空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

最好、最坏情况时间复杂度

最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度。
最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。

平均情况时间复杂度

这个值就是概率论中的加权平均值，也叫作期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

均摊时间复杂度

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。