本文为自己的学习笔记，仅供自我学习，学习资料极客时间的王争的《算法与数据结构之美》。
一.基础概念
时间复杂度表示程序运行速度的快慢。空间复杂度表示程序运行所占用的程序的大小。
二.大O复杂度表示法
现在让我们来估算一下上方的程序的复杂度。
从CPU的角度上面来看，每行代码都执行了三个操作：读数据-运算-写数据。我们这里只是初步估算一下，我们假设每行代码执行时间一样，都为unit_time。
由此第二和第三行代码分别也就需要1个unit_time时间。第4和5行代码都运行了n遍。所以第4行代码和第5行代码需要2n*unit_time时间。故执行总时间就为：(2n +2)*unit_time。故：代码执行时间与执行次数成正比。
接下来我们程序计算下一个程序的总执行时间。
经过计算，上面这段代码的总执行时间为：T(n) = (2n^2+2n+3)*unit_time。分别为2，3，4行代码的3个unit_time时间+5，6行的执行时间2n*unit_time时间+7，8行代代码执行了n^2遍。所以需要2n^2个unit_time执行时间。我们可以把代码执行时间与执行次数成正比这个规律组成总结下方成一个公式。
T(n)：总执行时间 n表示数据规模的大小。f(n)表示每行代码执行速度的总和。公司中的O表示代码执行时间与执行次数成正比。故第一个例子可以表达为T(n) = O(2n+2)，第二个例子中的 T(n) =O(2n^2+2n+3）这就是大O时间复杂度表示法。大O时间复杂度并不是直接表示代码真正的执行时间而是表示代码执行时间随数据规模增长的变化趋势。又名渐进时间复杂度，简称时间复杂度。
当n很大时低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。因此上2段代码的时间复杂度为T(n) = O(n)； T(n) = O(n^2)。
分析时间复杂度有三个比较实用的方法。
1.只关注循环执行次数最多的一段代码。
2.加法法则：总复杂度等于量级最大的那段代码的复杂度。
以上代码可以分为三部分，分别是求sum_1,sum2,sum3我们可以分析每一部分的时间复杂度，然后把它们放到一块儿，再取一个量级最大的最为整段代码的复杂度。我们分析一下第二段代码和第三段代码的时间复杂度。答案是O(n)和O(n^2)。故整段代码的复杂度为O(n^2)。
3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。
假设T1(n) = O(n)，T2(n) = O(n2)，则 T1(n)*T2(n) = O(n^3)。下面结合代码看一下。
我们单独看cal()函数。假设f()只是一个普通的操作，那第4-6行的时间复杂度就是T1(n)=O(n)。但f()函数本身不是一个简单的擦着，它的时间复杂度是T2(n) =O(n)，所以，整个cal()函数的时间复杂度就是T(n) = T1(n) * T2(n) = O(n*n) =O(n^2)。
几种常见时间复杂度实例分析。
对于上面复杂度量级，我们可以分为多项式量级和非多项式量级其中，非多项式量级只有两个：O(2^n) 和 O(n!)。
我们把时间复杂度为非多项式量级的算法问题叫作NP（Non-Deterministic Polynomial，非确定多项式)问题。
当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。因此，关于 NP 时间复杂度我就不展开讲了。我们主要来看几种常见的多项式时间复杂度。
1.O(1)
为常量级时间复杂度的表示方法，并不是指执行了一行代码。几遍有3行代码，它的时间复杂度是O(1），而不是 O(3)。
只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。
2.O(logn)、O(nlogn)
对数阶时间复杂度非常常见。
从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。还记得我们高中学过的等比数列吗？实际上，变量 i 的取值就是一个等比数列。如果我把它一个一个列出来，就应该是这个样子的：
所以，我们只要知道 x 值是多少，就知道这行代码执行的次数了。通过 2^x=n 求解 x 这个问题我们想高中应该就学过了，我就不多说了。x=log2n，所以，这段代码的时间复杂度就是O(log2n)。
现在，我把代码稍微改下，你再看看，这段代码的时间复杂度是多少？
根据我刚刚讲的思路，很简单就能看出来，这段代码的时间复杂度为O(log3n)。
实际上，不管是以 2 为底、以 3 为底，还是以 10 为底我们可以把所有对数阶的时间复杂度都记为 O(logn)。在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为O(logn)归并排序、快速排序的时间复杂度都是 O(nlogn)。
3. O(m+n)、O(m*n)
从代码中可以看出，m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以
我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时
间复杂度就是 O(m+n)。
空间复杂度分析
时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系，类比一下，
空间复杂度的全称就是渐进空间复杂度（asymptotic space complexity），表示算法的储存空间与数据规模之间的增长关系。
具体来分析下面这段代码。（这段代码有点"傻"，一般没人会这么写，只是为了方便解释。）
跟时间复杂度分析一样，我们可以看到，第2行代码中，我们申请了一个空间存储变量i，但是它设计哦常量阶的，跟数据规模n没有关系，我们可以忽略。第3行申请了一个为大小为n的int类型数组，除此之外，剩下来的代码都没有占用更多的空间，所以我们的整段代码的空间复杂度就是O(n)。
我们常见的空间复杂度就是 O(1),O(n),O(n^2),像O(logn),O(nlogn)这样的对数阶复杂度平时都用不到。有时候为了更好追求时间复杂度，可以适当的牺牲空间复杂度。
最好，最坏情况时间复杂度
不难看出来，这段代码要实现的功能是，在一个无序的数组中，查找变量x出现的位置。如果没有找到，就返回-1。不难看出这段代码的复杂度是O(n)，其中n代表数组的长度。我们在数组中查找了一个数据，并不需要每次把数组都遍历一遍，因为有可能中途找到就可以提前借宿循环了。但是这段代码是不够高效的，可以优化成以下这段代码。
看下我们优化之后的代码，这个时候我们来分析一下这段的代码的复杂度。
因为，要查找的变量x可能出现在数组的任意位置。如果数组中第一个元素正好是要查找的变量x，那就不需要遍历剩下的n-1个数据了，那时间复杂度就是O(1)。单如果数组中不存在变量x，那我们就需要把整个数组都进行遍历一遍，时间复杂度就成了O(n)。所以不同的情况下，这段代码的时间复杂度就是不一样的。
为了表示代码在不同情况下的不同时间复杂度，我们需要引入三个概念：最好情况时间复杂度，最坏情况时间复杂度和平均情况时间复杂度。
顾名思义，也就是最好的时候时间复杂度和最坏的时候的时间复杂度。
平均情况时间复杂度
平均情况时间复杂度。简称平均时间复杂度。那么应该怎么分析了，我接着上面的例子给大家分析一下。
要查找的变量X在数组中的位置，有n+1种情况：在数组的0~n-1位置中和不在数组中。我们把每种情况下，查找需要遍历的元素个数累加起来，然后再除以n+1，就可以得到需要遍历的元素个数的平均值即:
我们知道，时间复杂度大O标记法中，可以省略掉系数，低阶，常量，所以将上面那个公司简化之后，得到的平均时间复杂度就是O(n)。
这个结论虽然是正确的，但是计算过程是有点问题的。我们这边将出现的问题分析一下。首先我们刚讲的这n+1种情况，出现的概率并不是一样的。我们知道，要查找的变量x，要么在数组里，要么就不在数组里。我们假设这两种情况的概率是相等的切都为1/2。另外，要查找的数据出现在0~n-1这n个位置的概率也是一样的 ，为1/n，所以，根据概率乘法法则，要查找的数据出现在0~n-1中的任意位置的概率就是1/(2n)。因此时间复杂度的计算过程就变成了下面这样。
这个值在概率学中叫做加权平均值，也叫做期望值。平均时间复杂度的全称应该叫做加权平均时间复杂度或者期望时间复杂度。
引入概率之后，签名的那段代码的加权平均值为(3n+1)/4。用大O表示法来表示，去掉系数和常量，这段代码的加权评卷时间复杂度任然是O(n)。
均摊时间复杂度
老规矩，看下面为了举例写出来的代码。
首先我来解释一下这段代码。这段代码实现了一个往数组中插入数据的功能。当数组满了之后，也就是代码中的count == array.length时，我们用for循环遍历数组求和，并清空数组，将求和之后的sum值放在数组的第一个位置，然后再将新的数据插入。但如果数组一开始就有空闲控件，则直接将数据插入数组。
那么这段代码的时间复杂度是多少呢？你可以先用我们刚讲到的三种时间复杂度的分析方法来分析一下。最理想的情况下，数组中有空闲空间，我们只需要要将数据出入到数组为count的位置就可以了所以最好的时间复杂度为O(1)。最坏的情况下，数组中没有空闲控件了，我们需要先做一次数组的遍历求和，然后再将数据插入，所以最坏的情况时间复杂度为O(n)。
那么平均时间复杂度是多少呢？答案是O(1)。我们还是可以通过前面讲的概率论的方法来进行分析。
假设数组的长度是n，根据数据插入的位置的不同，我们可以分为n种强开，每种情况的时间复杂度是O(1)。除此之外，还有一种"额外"的情况，就是而我们在数组没有空闲控件时插入一个数据，这个时候的时间复杂度是O(n)。而却，这n+1种情况的发生的概率是一样，都是1/(n+1)。所以，根据加权平均的计算方法，我们求得的平均时间复杂度就是：
但是这个李自力的平均复杂度分析并不需要这么复杂，不需要引入概率论的知识。我们来对比一下这个insert()的例子和前面的那个find()的例子。首先，find()函数在极端的情况下，复杂度才为O(1)。但insert()在大部分情况下，时间复杂度都为O(1)。只有个别情况下，复杂度才较为高，为O(n)。这是insert()第一个区别于find()的地方。
我们再来看第二个不同的地方。对于insert()函数来说，O(1) 时间复杂度的插入和O(n)插入之后，紧跟着n-1个O(1)的插入操作，循环往复。
所以针对以上复杂度的分析，我们并不需要像之前讲平均复杂度分析方法那样，找出所以发生的情况及相应概率，然后再计算加权平均值。在此我们有一个简单的分析法叫做：摊还分析法。通过摊还分析法得到的时间复杂度我们取了一个名字叫做均摊时间复杂度。
继续看上面的那个例子，我们接着分析。每一次O(n)的插入操作，都会跟着n-1次O(1)的插入操作，所以把耗时多的那次操作摊到接下来的n-1次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是O(1)。这个就是均摊分析的大致思路。个人认为，均摊时间复杂度就是一种特殊的平均时间复杂度。
