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

时光老头

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

时间复杂度

来咱们先看一段代码

  1      int count(int n){
  2         int sum = 0;
  3         for(int i = 1; i <= n; i++){
  4              sum = sum + i;     
  5         }
  6         return sum;
  7         }

虽然每行代码具体的执行时间是不一样的，但是我们就粗略的认为每一行代码执行的速度都为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)，简称时间复杂度，它实际上表明的只是代码的执行时间随数据规模增长的变化趋势，而不是代码执行的具体时间。

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

  1      int count(int n){
  2         int sum1 = 0;                                 //t
  3         int sum2 = 0;                                 //t    
  4         int squareN = n*n;                            //t
  5         for(int i = 1; i <= n; i++){                  //n*t
  6              sum1 = sum1 + i;                         //n*t
  7         }
  8         for(int i = 1; i <= squareN; i++){            //n²*t 
  9              sum2 = sum2 + i;                         //n²*t 
  10        }
  11         return sum1+ sum2;                            //t
  12       }

按照咱们上面说的提取出的大致总执行时间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其实就是我们运行的次数，你看看是这样的吧。所以,时间复杂度就是O()！

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

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

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

来上代码！

  1         int  find(int[] array,int x) {  
  2            int result = -1;
  3            int n = array.length;
  4            for(int i = 0 ;i < n; i++){
  5                    if(array[i] == x){
  6                          result = i;
  7                          break;
  8                      }
  9                }
  10            return result;     
  11        }                  

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

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

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

在按照我们之前说的省略一下常数，平均情况时间复杂度就是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²)，想对数阶的都很少遇到，而且具体分析的也比时间复杂度简单多啦！

总结

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

---

如果有错误欢迎指正！以下是我的个人公众号！请大家多多支持谢谢！