0x06-学习玩转数据结构-简单的复杂度分析

1、O(n)是什么

我们通常会说某一个算法它的时间复杂度是O(1)的或者O(n)的、O(lgn)的等等，那么这个O到底是怎么回事呢呢？简单的来说，这个O描述的就是算法的运行时间和输入数据之间的一个关系，注意我说是简单的来说，这不是O的一个严格定义，O拥有非常严格严谨的数学的定义。

O(n)是什么

2、何为时间复杂度

那么什么叫这个运行时间和输入数据之间的关系呢？我们可以看一个非常简单的代码，可以看这个代码叫做sum，其实就是对一个数组中的数字求和，他的输入数据就是一个数组，我把它叫做nums。那么这个逻辑非常简单，相信同学们都会初始化sum等于零，然后来一重复循环来遍历nums里的每一个数num，每便利到一个num ，sum都加等于num，之后我们返回sum就好了。那么通常我们说这样的一个算法式O(n)的，为什么是这么说呢？对于n是什么？我们是要有一个定义的，在这个算法中？我给它定义成是数组nums中的元素个数，我有了这个n的定义之后，我说这个算法是一个大O(n)的算法是什么意思呢？是指这个算法它的运行的时间的多少是和这个nums中元素的个数成线性关系的。那么这个线性关系就表现在我们的这个n是一次方，它不是O(n^{2)的，不是O(n}3)的，它是O(n)的。这个n所对应的幂是一次方，所以呢，我管它叫做线性关系。

3、为什么要用O(n)

这本身非常好理解，我们nums中的数字越多，那么相应的这个算法执行的就会更加的慢一点儿。不过既然我说是成线性关系，我干嘛要管它叫做O呢？为什么非说这个算法的时间复杂度是O(n)呢？这是因为实际上我们忽略了很多常数，那么同学们应该都知道，如果我说是线性的话，线性方程是这样的一个形式，这个时间t应该等于一个c1乘以n加c2，这样的一个表达式才叫线性的。具体的我们可以看，在这个算法中其实对于每一个数我都做了什么事情呢？那么首先在这个循环里，我要把这个数从这个nums那个数组中取出来，这是一件事情；其次我还要把sum这个数给取出来，然后呢，我要把sum这个数和njum这个数给加在一起，最终呢，我还要再把这个结果扔回给sum这个变量中。其实我对每一个数要做这么多的操作，那么这么多的操作，所花费的总时间就叫做c1。

为什么用O(n)

与此同时，对于我们整个这个算法，可以看我在开始前可能还要开一块儿int的空间sum，初始化赋给了sum。在整个算法运行结束以后我还要把这个sum返回去，这些过程就是这个c2。所以我们这个算法实现运行的时间是c1乘以n加c2的。但是在我们具体分析算法的时候，如果我们把c1是多少，c2是多少也都具体的分析出来，一方面是必要性不大的，另一方面更重要的是有些情况下可能也是不可能的。

4、简单复杂度分析

我们在分析时间复杂度的时候，是忽略掉这些常数的，那么忽略这些常数就意味着什么？就意味着，如果我有一个算法它的t等于二乘以n加2；有另外一个算法，它的t等于2000n+1万，这两个算法，在这个O的意义下都是O(n)的算法。它们都是线性时间的算法，也就是说我们这个算法它消耗的时间和我们输入数据的规模之间是成一个线性关系的。而如果有一个算法，他的时间t等于一乘以n乘以n，再加上一个0，大家不要看这个1很小，这个零也很小，但是他依然是一个O(n^{2)级别的算法。也就是说这个算法所消耗的时间和我们的这个数据规模是成一个平方关系的。从另外一个角度讲，同学们可以看下面的这两个时间，在O这个表示下，我们的这个第二个算法是大O(n)这个级别的，而第三个算法是O(n}2)这个级别的。也就是说我们的第三个算法，是比我们这个第二个算法性能要差的，因为他是n方级别的。

有人会说这好像不太合理，因为我们第二个算法这个前面的常数特别的大，而第三个算法前面常数特别的小。比如说我们代进去假设n等于十的话，可以想象我们就第二个算法2000×10再加上1个1万等于3万，而对于第三个算法呢，1×10再乘以10+0还等于100也就说第三个算法在n等于十的时候，明显要比我们第二个算法n等于十的时候要快。那么这个疑问呐其实是一个非常好的疑问，而且事实也正是如此，如果我们说一个算法是O(n)的，另外一个算法是O(n^{2)的，并不代表对于任意输入来说这个O(n)的算法都要快于O(n}2)的算法。具体的我们确实要看那个算法前面的常数，这个O的表示，它其实我们翻译成中文应该叫做渐进时间复杂度。那么，这个渐进表现在哪儿？表现在它实际上描述的是当n趋于无穷的时候，这两个算法谁快谁慢。那么再这样的定义下，同学们可以再来看一下，第二个算法和第三个算法，我非常简单，只要带入n等于3000，那么在这种情况下同学们可以简单的算一下，就很容易的算出来我们的第三个算法得到的这一个t就已经远远的大于第二个算法了。当然当n比3000还要大的时候我们这个O(n^{2)算法都是慢于这个O(n)算法的。当n趋近于无穷的情况下，其实3000还永远没有到无穷，但是n越大一个低阶算法的时间复杂度才更容易的被显现出来。也就是说，n越大我们越能清楚地看到这个O(n)级别的算法，他是远远的快于这个O(n}2)级别算法的。

5、O描述的是一种算法

在这里主要要理解的就是O描述的是一个算法，或者说是一个操作，它的一个渐进时间复杂度度。也就是说，我们这个算法或者这个操作，它所消耗的时间和输入数据的规模之间的一个关系。这里在多说一句，由于描述这个n趋向于无穷的情况下，我们这个算法的时间复杂度。所以如果比如说我们实际这个算法的时间，它和这个n如果是成个二次方关系的话，相应的有可能也有一个一次方的项，那么在这种情况下，我们的算法的时间复杂度，对于这个二n加加300n加10的情况依然叫做一个O(n^2)的算法。这个低阶下会被忽略掉，那么这个原因就是当n趋近于无穷的时候，这个低阶项起的作用太小了，在n无穷大的时候低阶项的大小是可以忽略不计的。那么有了这个基本的认识，现在呢，我们就可以简单的分析一下，我们之前一直在写的这个数组中各项操作相应的一个时间复杂度。

O描述的是一种算法

6、添加操作分析

先来看看，对于我们的这个动态数组添加这个操作时间复杂度怎么计算。那么首先咱俩回一下insertLast，这个方法向数组的末尾添加1个元素，其实是非常简单的，直接给我的那个data[size]的位置赋一个值就好了，这个时间复杂度我叫做O(1)的。O(1)这个时间复杂度就意味着，我们这个操作它所消耗的时间跟我们数据的规模是没有关系的那么，当我们分析数组的时间复杂度的时候，这个数据的规模是指我们当前数组有多少个元素叫做n。也就是说，不管我们当前数组里有多少个元素，insertLast都能在常数时间里完成，这就是O(1)这个时间复杂的意思。相应的insertFirst同学们想象一下，我们向数组头添加1个元素，我们就要把数组中的每一个元素全都向后移一个单位。所以这个时间复杂度肯定是O(n)的。稍微有点复杂的是insert(int index，int e)，这个操作就是指我要在index这个索引的位置插入一个元素，这个时间具体是多少，和我们取得这个index是多少是相关的。极端一点说的话，我们的index等于零的话，他的时间复杂度就和insertFirst一样，我们要向后挪n个元素。但是如果我们这个index等于size的话，它其实和insertLast是一样的，我们一个元素都不用挪，此时他是一个O(1)的时间复杂度，对于这个时间复杂度，我们怎么分析呢？我们的分析方法其实是这样的，由于这个index可以取从0到size这么多种可能，那么我们假设在具体的调用这个操作的时候，取到这么多种可能中的每一个取值它的概率是相等的，也就是我们要一些概率论的知识。在这种情况下，我们就可以求出这个操作，它消耗的那个时间的期望是多少，那么对于这个具体的计算了，响应的数学其实也超出了我的这个课程的范围，不过可能很多同学在本科的时候都学过概率论基础知识，如果有兴趣的话，那也不妨计算一下，按照我刚才所说的这个背景，相应的这个操作它的时间复杂度的期望是多少。

添加操作分析

可以简单的理解成我们每一次调insert的时候，平均来看，有的时候这个index超前一些这种情况下的，我们向后挪的元素就会多一些，整体这个操作就会慢一些。那么有些情况我们index大一些，那么我们需要向后挪的元素就少一些，我们整个操作就会快一些。平均而言，我们要向后挪二分之一n个元素，所以跟这种情况下来，我可以说他的时间复杂度是O(n/2)的。对于这个二分之一，其实是一个常数，我之间说过我们O这个符号要把常数给忽略掉，所以他依然是一个O(n)这个级别的算法。那么这种分析问题的方式，同学们了解即可，不管怎样这个添加操作，我们综合来看他是一个O(n)级别的算法。这这里可能有同学又会说了明明这个insertLast，它是一个O(1)级别的算法，你为什么又说整体它是一个O(n)级别的算法呢？明明在极端的情况下，我每一次调用都调用insertLast它就是一个O(1)的算法呀。那么在算法复杂度分析上，通常我们关注的是最坏的情况，最糟糕的情况，在这里同学要注意的。

在这里我们分析添加操作的时候，同学们不要忘了，我们在做动态数组的时候，一旦我们的这个添加操作遇到了我们的数组已经满了情况下，我们还要进行resize操作。resize这个操作它的时间复杂度显然是O(n)的，我们要把原来的n个元素全都复制一遍，不管怎样，综上所述的动态数组来说，添加操作时间复杂度是O(n)级别的。

7、删除操作分析

有了这样的一个分析，我们再来看删除操作就非常简单了。对于removeLast删除操作来说，显然是一个O(1)级别的操作，removeFirst是O(n)时间复杂度的操作，remove(int index, int e)的操作，可以感性的来想平均的情况下，它的时间度还是O(n)的。综合来看，删除操作的时间复杂度是O(n)的。不过，我们在删除操作中也会进行resize，resize的过程也是一个O(n)的时间复杂度，所以总体来说，我们删除操作的时间复杂度也是O(n)级别的。

删除操作

8、修改操作分析

修改操作非常简单，在动态数组中，只要你知道你要修改的这个元素，它对应的索引是什么？我们直接用set（int e， int index）就好了，这个时间复杂度是O(1)级别的，这是数组最大的优势，用专业点的术语说叫做支持随机访问。我只要知道我要访问的这个索引是谁？我一下子就能访问到它。如果你不知道你要访问的这个索引，其实本质上，你就需要进行一遍搜索，我把它归结到查询操作中。在查询操作中，如果我知道，我要查的那个元素，它的index索引是谁？我用get方法O(1)的时间怎能拿到它。但是，如果我不知道这个所以的话，那么有两个方法，一个是contains看数组中是否包含某个元素，另外一个find看我们这个数组中这个元素对应的索引是多少。对于这两个操作都是O(n)级别的操作，我们需要把整个数组中的内容从头到尾遍历一遍来找到相应的内容，那么我们的查找操作就会根据我们是否知道，我们要查找的那个元素的索引分成是O(1)级别的操作，或者是O(n)级别的操作。分析到这里，我们就看出来了，对于动态速度来说，增和删这两个操作都是O(n)级别的操作。改，如果我们已知索引的话就是O(1)级别的操作，如果我们未知索引的话就是O(n)级别的操作。查找是同样的，已知索引是O(1)，未知索引是O(n)。如此，我在这刚开始印象里就曾经说过，对于使用数组来说，我们最好使用的情况，是这个索引具有一定的语言情况下，那我们就可以轻松地用索引去检索数组中的内容，那么在性能上就有非常强的优势。

复杂度分析

9、总结

不过在这里其实还遗留了一个很重要的问题，就是关于这个增和删，那么可能有一些同学注意到啦。对于增和删上来说，如果我们只对最后一个元素操作的话，无论是insertLast还是removeLast，其实这两个操作都是O(1)级别的操作。可是我说它还是O(n)级别的操作，就是因为有resize，我们一旦要resize了，就需要把整个元素全都复制一遍，复制给一片新的空间，看起来这个resize好像是一个性能很差很到事情的这样一个操作，可是实际上是不是这样的？那么对于resize这个操作响应的分析，其实我们完全使用这种最坏情况的时间复杂度分析是不合理的。我们下一小节就将引入一种新的时间复杂度的分析所谓的均摊时间复杂度，通过下一小节的介绍，同学们就会看到其实这个resize，它所消耗的性当在整体上没有大家想象的那么的糟糕。

resize时间复杂度分析