今天分享的是时间复杂度、空间复杂度相关内容，可以简单了解下复杂度相关的知识。

复杂度：复杂度描述的是算法执行时间或占用空间与数据规模的增长关系

我们用大O表示法来表达复杂度关系 T(n) = O(f(n))

其中 T(n) 是代码的执行时间，n 表示数据的规模，f(n)表示代码执行的总次数。O 表示代码的执行时间 T(n) 与 f(n) 成正比关系。要注意的是 大O时间复杂度表示的并不是代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势（大O复杂度分析法只是表示一种变化趋势，通常忽略低阶，系数，常量，只需看最大阶的量级），所以，也叫做时间渐进复杂度，简称时间复杂度。

分析时间复杂度的三种方法：

1. 只关注循环代码执行次数最多的一段代码

前面介绍到大O复杂度分析法只是表示一种变化趋势，通常忽略低阶，系数，常量，只需看最大阶的量级。所以在分析代码的时候，只关注循环次数最多的那一段代码就好

分析：2,3行是常量级执行时间，与n无关，对复杂度度没啥影响。4,5行是循环次数执行最多的，这两行代码执行了n次，所以时间复杂度是O(n)

1. 加法法则（量级最大法则）：总复杂度等于量级最大的那段代码的复杂度

上面代码主要是求sum_1,sum_2,sum_3，然后在求三者之和。

sum_1执行100次，是常量的执行时间，和规模n无关。这里需要注意，即使这段代码执行100000次或更多次，只要是一个已知的数，跟n无关，就是常量级的执行时间。当n无限大的时候，可以忽略。尽管对代码执行时间有很大影响，但时间复杂度表示的是一个算法执行效率与数据规模增长的变化趋势所以不管常量的执行时间多大，都可以忽略。因为它本身对增长趋势没有影响。

同理，sum_2和sum_3分别是 O(n)和O(n^2)，对于这三个，我们取量级最大的O(n^2)，所以总的时间复杂度就等于量级最大的那段代码的时间复杂度。

抽象一下：T1(n)=O(f(n)),T2(n)=O(g(n))，T(n)=T1(n)+T2(n)=max(O(f(n)),O(g(n)))=O(max(f(n),g(n)))

3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

f()函数的时间复杂度是 T1(n)=O(n)，如果先把f()函数看成简单的操作，则cal()函数的时间复杂度是T2(n)=O(n)，所以整个cal()函数的时间复杂度是T(n)=T2(n)*T1(n)=O(n*n)=O(n^2)

①O(1)

O(1)是常量级时间复杂度的一种表示方法，并非只执行一行代码。只要代码执行时间不是随着n的增大而增大，这样的代码的时间复杂度都是O(1)。或者说，通常只要算法中不存在循环、递归，即使代码有很多行，时间复杂度仍是O(1)

上面的代码是3行，但是时间复杂度是O(1)，而不是O(3)。

②O(logn)、O(nlogn)

对数阶时间复杂度很常见，同时也是很难分析的一种时间复杂度。下面看一个例子

通过上面的分析时间复杂度的方法，我们可以知道这段代码的第3行是执行次数最多的，只要算出第3行执行的次数，就是整个代码的时间复杂度。 i从1开始取值，每一次循环乘以2.可以看到 i=i*2是一个等比数列

我们只要算出x是多少，就是执行的次数了 2^x=n -->x=log2n，所以时间复杂度应该为O(log2n)，如果代码改下，时间复杂度是多少呢？

很容易就能看出来，应该是O(log3n)。

但是上面的O(log2n)和O(log3n)可以通过换底公式换成以2为底的对数，且可以忽略系数，所以都记做 O(logn)。

关于O(nlogn),就是把上面的代码在循环执行n遍了。其中归并排序、快速排序的时间复杂度就是O(nlogn)

③O(m+n)、O(m*n)

这种类型的时间复杂度是由两个参数决定的，先上例子

上面的代码有m和n两个数据规模，而且我们不能判断两个谁的量级大，所以不能简单的用加法法则，省略其中一个。那么这个例子的时间复杂度就是 O(m+n)

所以将加法法则做个修改：T1(m)+T2(n)=O(f(m)+g(n))

空间复杂度分析

前面说到时间复杂度全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称是渐进空间复杂度，表示算法的存储空间与数据规模的增长关系。

第2行代码，申请了一个空间存储变量i，但它是常量阶的，根数据规模n无关，可以忽略。第3行申请了大小为n的int类型的数组，其余代码则没有申请空间。所以这段代码的空间复杂度是 O(n)

常见的空间复杂度是 O(1)、O(n)、O(n^2)，对数阶的复杂度平时用不到。

下面上一个复杂度趋势图

下面再来四个复杂度相关的知识点，最好情况时间复杂度（best case time complexity）、最坏情况时间复杂度分析（worst case time complexity）、平均情况时间复杂度（average case time complexity）、均摊时间复杂度（amortized time complexity）。

最好、最坏时间复杂度分析

上面代码的功能是在一个数组中查找一个变量x出现的位置，如果没有找到，返回-1。这段代码的时间复杂度应该为O(n)，其中n为数字的长度。

但是我们在数组中查找数据，并不需要每次都把数组都遍历一遍，因为有的数据在中途就找到，可以提前退出的，所以上面的代码写的不好，看下面的

我们发现，在找到数据后，就退出了循环。但是这个代码的时间复杂度就不能简单看成 O(n)了。因为我们没有办法判断在哪个位置上找到这个元素，可能数组的第一个位置就是要找的数据，然后不需要遍历后面的n-1个数据，那么时间复杂度是O(1)。如果数组中没有找到这个元素，就需要把数组整个遍历一遍，那么时间复杂度就是O(n)。所以我们发现，不同情况，时间复杂度是不一样的。为了表示代码在不同情况下的不同时间复杂度，我们需要引入三个概念：最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度。同理，最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。像上面的例子中，如果要查找的元素没有在数组中，就需要遍历整个数组。

平均情况时间复杂度最好情况时间复杂度和最坏情况时间复杂度都是在极端情况下的代码的复杂度，发生的概率不大。为了更好的表示平均情况下的复杂度，需要引入平均情况时间复杂度。还拿上面的例子举例。要查找的元素在数组中的位置，有n+1种情况：在数组的0~n-1位置中和不在数组中，共n+1种情况。把每种情况下，查找需要遍历的元素个数累加，然后除以 n+1，就能得到需要遍历的元素的个数的平均值。

因为大O表示法，可以省略系数，所以平均情况时间复杂度为 O(n)。但是这个计算过程是不严谨的，因为上面的n+1种情况出现的概率并非都一样。要查找的元素要么在数组中，要么不在数组中，为了方便，假设在数组中和不在数组中的概率都为1/2。要查找的元素出现在 0~n-1个位置的概率也都是一样的，为 1/n。所以要查找的元素出现在 0~n-1中任意位置的概率是 1/(2n)。将上面的计算逻辑修改如下：

这个值就是概率论中的加权平均值，也叫期望值，所以平均时间复杂度的全程应该叫加权平均时间复杂度或期望时间复杂度。我们发现，引入概率后，平均值为（3n+1）/4。用大O表示法表示，去掉系数和常量，这段代码的时间复杂度依然是 O(n)。其实，大多数情况，并不需要区分最好、最坏、平均情况时间复杂度。很多时候，用一个复杂度就可以满足。只有同一个代码在不同情况下，时间复杂度有量级的差距时，才引入这三个时间复杂度。

均摊时间复杂度

上面的代码实现的是往数组中插入数据的功能。当数组满了之后，用for循环遍历数组求和，并清空数组，将求和之后的sum值放到数组的第一个位置，然后再将新的数据插入。但如果数组一开始就有空闲空间，则直接将数据插入数组。分析这个代码的时间复杂度。最好的情况下，数组中有空闲空间，直接将数据插入到数组下标为count的位置，所以最好情况时间复杂度是O(1)。最坏的情况下，数组中没有空闲空间了，需要先遍历数组求和，然后再将数组插入，所以最坏情况的时间复杂度是 O(n)。平均时间复杂度分析如下：假设数组长度为n,根据数组插入的位置不同，分为n种情况，每种情况的时间复杂度为O(1)。还有一种情况就是，数组没有空闲空间了，这个时候时间复杂度是O(n)。这n+1种情况发生的概率相同，都是 1/(n+1)。所以平均时间复杂度为：

这个insert()和前面的find()是有区别的:

①find()在极端情况，复杂度才是O(1)。而insert()在大部分情况下都是O(1)，只有个别情况才是O(n)

②insert()函数，O(1)时间复杂度的插入和O(n)时间复杂度的插入，出现的频率很有规律，并且有一定的前后时序关系，一般都是一个O(n)插入后跟着n-1个O(1)插入，如此循环。

所以针对insert()这种情况，不需要像find()那样根据概率计算平均时间复杂度。而是引入一种更加简单的分析方法：摊还分析法，通过摊还分析法得到的时间复杂度叫均摊时间复杂度。

摊还分析法的使用：

还看insert()这个函数，每一次O(n)的插入，后面会跟着n-1次O(1)的插入操作，所以把耗时较多的那次操作均摊到接下来的n-1次耗时较少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是O(1)。

摊还分析法的使用场景：

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

上面的分享希望大家好好看看，对时间复杂度扫盲还是可以的

还是那句话，“见识、目标、认清差距、努力+正确的方法”对人生成长无比重要，希望你通过此文有所启发、收获！