复杂度和时间复杂度（一次搞懂时间复杂度和空间复杂度）

数据结构和算法因何而生？其实它们的存在就是为了解决“快”和“省”两个问题。也就是如何让代码运行的效率更快！让代码的执行更节省存储空间！而时间复杂度和空间复杂度就是来衡量我们的代码是否快！是否省！掌握了这两种分析技能我们就能炼成火眼金睛！一眼瞄出“快”和“省”的代码！

时间复杂度

来咱们先看一段代码

虽然每行代码具体的执行时间是不一样的，但是我们就粗略的认为每一行代码执行的速度都为t，那这情况就是第二行t 第三行n*t 第四行n*t 第六行t。所以这段代码的总执行时间就是2t 2n*t。我们可以看到这段代码执行的总时间和每行代码执行的次数n成正比！

则可提取出一个公式T（n）=O（f(n)）。从我们的例子来看就是T（n）=O(2n 2)，而当n很大的时候，公式种的常量系数和低阶部分都不会影响整体的增长情况，所以可以忽略了，因此可以记为T（n）=O(n) 这就是我们的大0时间复杂度表示法了！

大O时间复杂度实际也叫渐进时间复杂度(asymptotic time complexity)，简称时间复杂度，它实际上表明的只是代码的执行时间随数据规模增长的变化趋势，而不是代码执行的具体时间。

咱再来看一段代码，我把每行的执行时间直接标注在代码后面

按照咱们上面说的提取出的大致总执行时间4t 2n*t 2n²*t =>t(2n 2n² 4)得到T(n) = O(2n 2n² 4)。

又因为可以忽略常量系数和低阶部分，所以最终记为T(n) = O(n²)。

所以我们只需要关注循环次数最多的那一行代码！它的执行次数就代表我们的时间复杂度

其实虽然代码有五花八门，但是常见的时间复杂度也就几种:

执行的效率从上往下递减

前面已经举过O(n) 和O(n²)，我们再讲讲O(1)和O(logn)

1. O(1)

1 int a = 1; 2 int b = 1;

面这段代码，它的时间复杂度就是O(1),注意不是O(2),也就是只要代码的执行实际不随着n的增长而增长，也就是基本上方法内没有循环递归这样的语句，即使你一个方法有几千行代码，时间复杂度就是O(1)。

2. O(logn)

1 int i= 1; 2 while( i <= n) { 3 i = i * 2； 4 }

对数阶的时间复杂度啊，相对而言是最难分析的。不过问题不大让我们来深入理解一下！

咱们看看上面的变量i，它的初始值是1，每次循环之后就乘2，这就完全符合我们学过的等比数列：

初始值是1 那就是2º ，然后 2¹ , 2² ......。最终2的x次方等于n而这个x其实就是我们运行的次数，你看看是这样的吧。所以x=log2ⁿ,时间复杂度就是O(log2ⁿ)！

那我们循环不乘2，咱们乘3那时间复杂度是不是就是O(log3ⁿ)？

实际上，咱们不过底数是多少，我们对于对数阶的时间复杂度都记为O(logn),因为对数之间是可以互相转换的log3ⁿ=log3² * log2ⁿ，提取出常数之后O(log3ⁿ) = O(常量*log2ⁿ)，所以我们统一记为O(logn)！

再更细一点，时间复杂度还分:最好情况时间复杂度、最坏情况时间复杂度，平均情况时间复杂度，均摊时间复杂度。

来上代码！

最好的情况就是查的这个x在数组的第一个位置！所以最好情况时间复杂度就是O(1)。

最坏的情况就是查的这个x在数组的最后一个位置或者没查到！这两种情况都遍历了整个数组，所以最坏情况时间复杂度就是O(n);

但是这两种都太极端了，我们来平均一下，简单点假设x在这个数组里面的概率为1/2,那不在这里面的概率也是1/2，如果在数组里的话，在0到(n-1)之间每个位置的概率就是1/2n。所以我们可以推导出公式:

在按照我们之前说的省略一下常数，平均情况时间复杂度就是O(n)。

一般情况下，正常的时间复杂度就已经够我们用的了！除非在这三种情况下，时间复杂度有量级的变化，我们才会以这三种情况来区分！

咱再来了解一下更高级的玩意！均摊时间复杂度，这东西比我们上面说的那三种用到的更少了。

听起来好像和平均情况时间复杂度有点像，但是不太一样。就比如ArrayList，我们知道ArrayList底层是数组实现了，数组是有固定大小的设为n，正常情况下我们的插入数据的时间复杂度是O(1) 。

如果我们自己实现了一个ArrayList,在扩容时没有调用System.arraycopy()，而且自己new一个新的数组，大小为之前的2倍，并且用for来拷贝的话(不推荐，效率比System.arraycopy()低，只是为了说明均摊时间复杂度!)。

所以扩容的时候我们需要搬迁以前的n个数据的到新的数组上，这一次操作的时间复杂度就是O(n),然后之后一段时间内我们插入的时间复杂度又是O(1)。就只要往复又到扩容然后正常插入。。。。。循环。

我们总结下这种规律，在O(n）插入之后都伴随着n次的O(1)插入，那我们把n平均的分到每次O(1)插入上，那均摊下来是不是几乎所有的插入的时间复杂度都是O(1)了呢？这就是均摊时间复杂度，一般的均摊时间复杂度都等于最好情况时间复杂度！

空间复杂度

空间复杂度的全称是渐进空间复杂度(asymptotic space complexity)，表示算法的存储空间和数据规模的增长关系。

同样咱们先看一段代码

1 int i= 1; 2 int[] a = new int[n];

其实和时间复杂度分析是一样的，第一行代码申请了一个存储变量i，第二行申请了n个大小的int类型数组，因为第一行是常量，所以忽略，只看第二行，所以得出空间复杂度就是O(n)。

而且常见的空间复杂就是O(1), O(n), O(n²)，想对数阶的都很少遇到，而且具体分析的也比时间复杂度简单多啦！

总结

理解了这两种复杂度分析等于我们掌握了代码中的“时间”和“空间”能力！有点厉害哈哈哈。

---

如果有错误欢迎指正！

个人公众号: yes的练级攻略

,