执行效率是算法的一个重要的考量指标，算法的执行效率用时间、空间复杂度来衡量。
今天我们来学习一下复杂度的分析。
1.为什么需要复杂度分析
通常我们可以通过运行程序来获得算法的真正的执行时间，这种方法我们可以称为事后统计法，但这种方法得到的是具体的数据，测试结果很依赖测试环境，而且受数据规模影像最大。因此，我们需要一个不需要具体测试数据，就能粗略估算算法执行效率的方法，这即是我们今天要说的时间、空间复杂度分析。
2.大O复杂度表示法
我先来解释下，什么是大O时间复杂度表示法。大O时间复杂度表示法并不具体的表示代码执行时间，而是代表代码执行时间随数据规模增长的变化趋势，因此也叫较进时间复杂度，简称时间复杂度。
- 所有代码的执行时间和每行代码的执行次数成正比
- 如下所示，若每行执行时间设为unit_time，则总时间需要
- 通过类似的推导，我们可以得到
T(n)=O(f(n))
- 这里，n表示数据规模，f(n)表示每行代码的执行总和，O表示，代码执行时间T(n)和f(n)成正比。
- 大O时间复杂度在表示时，长忽略低阶、常量、系数等，只记录最大量级，如O(n),O(n²）
3.时间复杂度分析
- 只关注循环执行最多的代码行即可。
- 加法法则：总复杂度=量级最大的那段代码的复杂点
- 乘法法则：总复杂度=嵌套内外代码复杂度的乘积
4.常见的时间复杂度
- 多项式复杂度：O(1) O(logn) O(n) O(nlogn) O(n²） O(n³) O(n^k)
- 非多项式复杂度：O(2^n) O(n!)
5.空间复杂度分析
类比实际复杂度，空间复杂度全称渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到
============================我是可爱的分割线(๑•ᴗ•๑)=================================
本计划将以下内容重新做为一节，但是考虑到内容的连贯性，觉得还是放在这里合适。
下面，我们学习一下不同情况下的几种复杂度分析。
浅析最好、最坏、平均、均摊时间复杂度
首先，我们先来说以下这几个概念：
- 最好情况时间复杂度：最理想情况下，代码执行的时间复杂度，简称最好时间复杂度
- 最坏情况时间复杂度：最坏情况下，代码执行的时间复杂度，简称最坏时间复杂度
- 平均情况时间复杂度：最好及最坏情况属于极端情况，因此，我们在分析时，还要分析平均情况时间复杂度，简称平均时间复杂度
这里需要注意的是，只有在同一段代码在不同情况下，时间复杂度有量级差距时，我们才会使用三种复杂度来区分，下面我们距离来分析以下这三种情况。
就以在数组a[n]中查找给定的元素为例来说明把。
当按顺序遍历数组时，若第一个就是要查找的元素，则时间复杂度为O(1),即最好时间复杂度。若要查找的元素是最后一个元素或元素不在数组内，则要遍历完整个数组，此时，时间复杂度为O(n)，即最坏时间复杂度。那平均时间复杂度又该如何来分析呢？
我们知道，要查找的元素，在数组中的位置，有n+1种情况，我们把每种情况下，查找需要遍历的元素个数加起来，再除以n+1，就可以得到遍历的元素个数的平均值，可得（1+2+3+...n+n)/(n+1)=n(n+3)/2(n+1)，用大O表示法可得，平均复杂度为O(n)。
我们知道，在数学种，有个叫期望值/加权平均值的概念，那在这里，对应的，n+1种情况出现的概率并不均等，按照这种计算方法，平均要遍历的元素个数应该为（1+2+3+..n)/n*0.5+n*0.5=(3n+1)/4，用大O表示也是O(n)，这种情况下的复杂度称为加权平均时间复杂度或期望时间复杂度。
最后，我们来特别说以下均摊时间复杂度。因为这个概念比较特殊。
在支持动态扩容的数组种，若数组已满，那我们在插入数据时，需要申请一个2倍大小的空间，并把原来数组中的数据拷贝到新数组中，在执行插入，那么此时，需要搬移整个数组，搬移所用的时间复杂度为O(n)，在扩容完成后，可以继续执行n-1此时间复杂度为O(1)的插入操作，那么我们可以这么想，要是把O(n)操作的时间均摊到接下来n-1次O(1)时间的操作上，那是不是类似与每次操作的时间复杂度还是O(1)？这便是均摊思想的大致思路。
一般，均摊时间复杂度的应用场景比较特殊。比如，在对一个数据结构进行一组连续操作中，大部分情况下时间复杂度很低，只有个别情况下时间复杂度较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。
好了，今天的内容就先写到这里，如果想了解更多复杂度的内容，可以关注公众号李哥学编程 查阅更多相应文章。下一节，正式进入数据结构和算法章节。
