数据结构与算法——时间复杂度

复杂度用于衡量程序的运行效率，复杂度是一个关于数据量n的函数，一般用大O表示法来表示运行的量级，常见的时间复杂度有O(1)、O(logn)、O(n)、O(n2)、O（n3）、O(2n)、O(n!)。

大O表示法表示的复杂度与常系数无关，比如计算后复杂度为O(n)和O(2n)的代码，他们的时间复杂度都是O(n)；如果计算后的时间复杂度是多项式级的时间复杂度，那么代码的时间复杂度则以最高次幂为准，比如计算后复杂度为O(n2+n)与O(n2)的两段代码，他们的时间复杂度都是O(n2)；对于O(1)的时间复杂度，O(1)指的是代码通过使用有限的可数的资源就能完成，与输入的数据量n无关。

如何计算时间复杂度？

《算法之美》一书在介绍大O表示法的时候介绍过，大O符号是用来测量算法最坏情况的速记法。大O符号的目的不是使用分钟和秒钟来表示算法的性能，而是方便我们讨论问题的规模和程序的运行时间之间的关系。

大O表示法的关于n的函数的计算为代码运行次数的总和，最终的时间复杂度由最大量级的项确定；

对于分多段的代码，总的代码时间复杂度就等于量级最大的那段代码的时间复杂度；对于嵌套代码，时间复杂度等于嵌套的多段代码的时间复杂度的乘积。

对于一个程序中出现的两个不同规模的代码段，如果不能确定大小，那么在累加的时候不能取其中一个作为时间复杂度，比如两段代码的时间复杂度分别为O(m)和O(n)，且无法比较m和n的大小，那么程序的时间复杂度应为O(n+m)；对于两个无法衡量量级大小的嵌套代码段的复杂度，跟累加的相同，该程序的时间复杂度也应该是O(m*n)。

最好情况时间复杂度

程序在最好的情况下运行的时间复杂度，比如插入一个元素到数组，如果刚好要插入到数组末尾，那么时间复杂度为O(1)，这是数组插入元素的最好情况时间复杂度。

最坏情况时间复杂度

程序在最糟糕的情况下运行的时间复杂度，就上面的数组插入元素，假如我们要插入到数组的第一个位置，由于数组是一片连续的内存空间，在存储数据时是按顺序存储的，当我们要把数据插入到数组的头部，那么我们要把数组的所有元素都按顺序一个一个往后移一位，此时需要遍历整个数组，时间复杂度为O(n)，这就是插入元素的最坏情况下的时间复杂度。

平均情况时间复杂度

平均情况时间复杂度，主要是针对像上面的数组插入元素，在已经有n个元素的数组中插入一个元素，有n种情况需要进行数据的移动，即当我们要把数据插入第0到第n-1个位置时，我们都需要进行数据的移动，所以往数组中插入元素，一共有n+1种情况，最后一种情况是直接将数据插入到数组的末尾，这里的时间复杂度可以根据每种情况发生的概率来计算期望时间复杂度。 由于在每个位置插入数据的概率是一样的，所以在数组中插入数据的时间复杂度应该是(0+1+2+…+n)/(n+1)=(n(n+1))/2(n+1)=n/2，时间复杂度为O(n)。分子为在每个位置插入数据时需要移动的数据的和。

均摊时间复杂度 均摊时间复杂度跟平均情况时间复杂度不是一个概念，均摊时间复杂度主要是将耗时多的操作均摊到耗时少的操作上。比如在数组尾部插入元素，这里是只要数组中还有空间，那么就往数组后面插入数据，当数组满了之后，要再插入数据，需要申请一个更大的空间然后将数组原来的内容搬到新的空间里，再继续往数组后面插入元素，在这种场景中，每进行一次O(n)复杂度的操作，前面都有n-1次O(1)时间复杂度的操作，整个过程中只有一步是耗时多的，那么可以把耗时多的这一步的操作的复杂度均摊到前面n-1次操作上，即(1+1+1+…+1+n)/n=(2n-1)/n。得到的均摊时间复杂度为O(1)，也就是在数组尾部插入元素的时间复杂度为O(1)，均摊时间复杂度只有在类似的应用场景中计算比较方便，其他时候分析时间复杂度还是以前面的分析方法为准。