首先我们通常用大O表示法来表示算法的复杂度

我们一般不用准确计算出整个算法所需要的步骤

只需要将其增长规律算出来就行

比如我要遍历一个长度为n的数组

此时时间复杂度就为O(n)

而如果我只遍历位置为 2的整数次幂的 数组元素

那么复杂度就为log2n

我们将时间复杂度简写为O(logn)

此外我们通常使用四个复杂度分析

分别是

1.最好情况时间复杂度

2.最坏情况时间复杂度

3.平均情况时间复杂度

4.均摊时间复杂度

最好/坏情况时间复杂度

图示为一个在数组中寻找一个指定元素的函数

但这样子写，无论什么情况我们都要遍历完整个数组

因此我们可以在找到数组元素的时候就中断寻找退出

现在我们把代码改写一下，加个break

现在我们来分析下

最理想的情况就是我们寻找数组元素的时候，第一个就是我们想要的，此时时间复杂度为O(1)

这对应的就是最好情况时间复杂度

最坏的情况是数组中没有我们要的那个元素，或者是那个元素在最后一个。因此我们要遍历整个数组，即时间复杂度为O(n)

# 平均情况时间复杂度

平均情况时间复杂度就要求我们在寻找数组元素的时候各个情况的复杂度

我们假设这个元素 是否在这个数组的概率都为0.5

并且出现在0~n-1这n个位置都一样

这样我们可以计算一个经过加权后的平均情况时间复杂度

此时复杂度仍为O(n)

均摊时间复杂度

我们要注意的是均摊时间复杂度与平均时间复杂度是两个完全不同的概念

下面我们先来看一段新的代码

这个代码大致意思就是我们对一个数组插入一个元素

如果该数组满了

就把前面的元素都求和放在第一位

以此类推

最好的情况下就是数组仍有空闲空间，此时最好情况时间复杂度为O(1)

最坏的情况下就是数组空间已满，你需要一个个去遍历，此时时间复杂度为O(n)

平均时间复杂度情况如下:

假设数组的长度是 n，根据数据插入的位置的不同，我们可以分为 n 种情况，每种情况的时间复杂度是 O(1)。除此之外，还有一种“额外”的情况，就是在数组没有空闲空间时插入一个数据，这个时候的时间复杂度是 O(n)。而且，这 n+1 种情况发生的概率一样，都是 1/(n+1)。所以，根据加权平均的计算方法，我们求得的平均时间复杂度就是：

但其实我们不用如此复杂地来计算时间复杂度

因为本质上find函数和后面这个insert函数有着很大区别

首先find函数只有在极端情况下才能达到复杂度O(1)

而insert大部分情况下复杂度都是O(1)

另外，对于insert函数，在它因无足够空间存放进行求和后，时间复杂度为O(n),此后的n-1个元素插入的时间复杂度均为O(1)

它是一种循环的情况

因此我们将时间复杂度高的操作均摊到时间复杂度低着几个操作

即把O(n)均摊到后续n-1个操作中

此时得到的复杂度为O(1)

我们便不需要根据复杂地加权求和来分析其复杂度了

思考题

最好的情况就是数组有空间能存放元素，这个很简单，复杂度为O(1)

最坏的情况就是要对数组进行复制

复杂度为O(n）

均摊时间复杂度

我们可以知道

在第一轮里面

我们存放n个元素后，再进行copy操作

因此是进行了n个O(1)的操作，再进行O(n)复制操作

在第二轮

我们存放了2n个元素(因为数组扩张到原来的两倍)

再进行copy

因此是进行了2n个O(1)的操作后，再进行O(2n)的复制操作

以此类推

我们把O(n)的操作均摊到n个O(1)的操作上

得出均摊复杂度为O(1)