数据结构与算法笔记day01： 复杂度分析：如何分析、统计算法的
从广义上讲，数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。
数据结构是为算法服务的，算法要作用在特定的数据结构之上。
数据结构和算法解决的是如何更省、更快的存储和处理数据的问题，因此，我们就需要一个考量效率和资源消耗的方法，这就是复杂度分析方法。
下面是数据结构和算法的一个完整架构：
但是我们并不用全部掌握，很多高级的数据结构与算法在平常的开发中很少会用到。我们学习要会找重点。
老师总结了20个最常用的、最基础的数据结构与算法：
10个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树。
10个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。
数据结构和算法本身解决的两个问题：
“快”——如何让代码运行得更快；
“省”——如何让代码更省存储空间。
时间复杂度分析
例子：
我们假设每个语句的执行时间是unit_time，第2、3、4行代码，每行都需要1个unit_time的执行时间，第5、6行代码循环执行了n遍，需要2n*unit_time的执行时间，第7、8行代码循环执行了n^2遍，所以需要2n^2*unit_time的执行时间，所以整段代码总的执行时间T(n)=(2n^2+2n+3)*unit_time。
尽管我们不知道unit_time的具体指，但是我们得到一个重要的规律，那就是，所有代码的执行时间T(n)与每行代码的执行次数成正比。
因此，在算时间复杂度的时候，我们把这个规律总结成了大O时间复杂度。大O时间复杂度并不具体表示代码真正的执行时间（事实上知道这个执行时间也没啥用），而是表示代码执行时间随数据规模增长的变化趋势，所以也叫渐进时间复杂度，简称时间复杂度。
注意：公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略，我们只用记录一个最大量级就可以了。
所以用大O表示法表示刚刚那段代码的时间复杂度，就可以记为：T(n)=O(n^2)。
举个例子：
这段代码分为三部分，分别是求sum_1、sum_2、sum_3。
第一段代码循环执行了100次，是一个常量的执行时间，跟n的规模无关。
注意哦，就算它循环10000000次，只要是一个已知的数，就是常量的执行时间，当n无限大的时候，它就可以忽略。尽管代码的执行时间会有很大影响，但回到事件复杂度的概念来说，它表示的是一个算法执行效率与数据规模增长的变化趋势，所以不管常量执行时间多大，我们都可以忽略掉，因为它本身对增长趋势并没有影响。
第二段代码循环执行了n次。
第三段代码循环执行了n^2次。
所以，我们取其中最大的量级，整段代码的时间复杂度为O(n^2)。
对于复杂度量级，我们可以粗略地分为两类：多项式量级和非多项式量级。
非多项式量级只有两个：O(2^n)和O(n!)。
当数据规模n越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长，所以，非多项式时间复杂度的算法其实是非常低效的算法。
因此，我们主要来看一下几种常见的多项式时间复杂度：
1)O(1)
O(1)只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码，如下面代码有3行，它的时间复杂度也是O(1)而不是O(3)：
只要代码的执行时间不随n的增大而增长，这样代码的时间复杂度我们都记作O(1)。又或者说，一般情况下，只要算法中不存在循环语句、递归语句，几遍有成千上完行的代码，其时间复杂度也是O(1)。
2)O(logn)、O(nlogn)
举个例子：
实际上，变量i的取值就是一个等比数列：
所以，我们只要知道x值是多少，就知道这行代码执行的次数了。由2^x=n得，x=log(2)n（log以2为底的n）。
我们把这段代码中的*2变成*3：
根据刚刚的思路，它的执行次数是x=log(3)n。
因为在采用大O标记复杂度的时候，可以忽略洗漱，所以在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一标识为O(logn)。
如果一段代码的时间复杂度是O(logn)，我们循环执行n遍，那么它的时间复杂度就是O(nlogn)。
3)O(m+n)、O(m*n)
例子：
m和n表示的是两个数据规模，我们无法事先评估m和n谁的量级大，所以在表示复杂度的时候，不能简单的利用加法法则省略掉其中一个，因此，上面代码的时间复杂度就是O(m+n)。
空间复杂度分析
时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系，类比一下，空间复杂度的全程就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
例子：
i是常量阶的，跟数据规模n没有关系，所以忽略。另外申请了一个大小为n的int类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是O(n)。
常用的空间复杂度：O(1)、O(n)、O(n^2)，空间复杂度比时间复杂度分析要简单许多。
总结：
复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法执行效率越低。
常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)。
接下来继续讲四个复杂度分析方面的知识点：最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度、均摊时间复杂度。
最好、最坏情况时间复杂度
例子：
如果要查找的变量x正好是数组的第一个元素，就不需要继续遍历剩下的n-1个数据了，这时时间复杂度为O(1)，这个时候对应的时间复杂度就是最好情况时间复杂度。但是如果数组中不存在变量x，那我们就需要把整个数组都遍历一遍，时间复杂度就成了O(n)，这种最糟糕情况下对应的时间复杂度就是最坏情况时间复杂度。
最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度。
最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度。
平均情况时间复杂度
最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度，发生概率并不大，我们引入另一个概念：平均情况时间复杂度，更好的表示平均情况下的复杂度。
变量x在数组中和不在数组中的概率都是1/2，若在数组中，则要查找的数据出现在0~n-1这n个位置中的概率也是一样的，为1/n，所以，根据概率乘法法则，要查找的数据出现在0~n-1中任意位置的概率就是1/(2n)，然后进一步算出这段代码的加权平均值为(3n+1)/4，用大O表示法来表示，去掉系数和常量，这段代码的加权平均时间复杂度仍然是O(n)。
大多数情况下，我们并不需要区分最好、最坏、平均三种复杂度，平均复杂度只有在某些特殊情况下才会用到，而接下来要讲的均摊时间复杂度应用的场景则比它更特殊、更有限。
均摊时间复杂度
例子：
这段代码实现了往一个数组中插入数据的功能，数组满了之后，用for循环遍历求和，并清空数组，将sum值放到数组第一个位置，再将新的数据插入。但是如果数组一开始就有空闲空间，则直接将数据插入数组。
显而易见，它的最好情况时间复杂度为O(1)，最坏情况时间复杂度为O(n)。
那它的平均时间复杂度是什么呢？
和前面那个例子的算法并不一样，因为它和前面的例子有些差别：
1)find()只有在极端情况下，复杂度才为O(1)，而insert()在大多数情况下，复杂度都为O(1)，只有个别情况下才是O(n)。
2)insert()函数中，O(1)和O(n)复杂度的出现频率是非常规律的，而且有一定的前后时序关系，一般都是一个O(n)插入自后，紧跟着n-1个O(1)的插入操作，循环往复。
针对这种特殊场景，我们不能像前面那样简单的计算它们的平均值，而是引入一种更加简单的分析方法：摊还分析法，通过这个分析方法得到的时间复杂度，我们叫均摊时间复杂度。
回到例子中，每一次O(n)的插入操作，都会跟着n-1次的O(1)的插入操作，所以把耗时多的那次操作均摊到接下来的n-1次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是O(1).
总结一下，均摊时间复杂度：对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能够将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上，而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。
