二.时间和空间复杂度
1.时间复杂度
在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。
通常把算法中的基本操作重复执行的频度称为算法的时间复杂度。算法中的基本操作一般是指算法中最深层循环内的语句（赋值、判断、四则运算等基础操作）。我们可以把时间频度记为T(n)，它与算法中语句的执行次数成正比。其中的n被称为问题的规模，大多数情况下为输入的数据量。
对于每一段代码，都可以转化为常数或与n相关的函数表达式，记做f(n) 。如果我们把每一段代码的花费的时间加起来就能够得到一个刻画时间复杂度的表达式，在合并后保留量级最大的部分即可确定时间复杂度，记做O(f(n)) ，其中的O就是代表数量级。
常见的时间复杂度有（由低到高）：O(1)、O( log 2 n \log _{2} n log2n)、O(n)、O( n log
2 n n\log _{2} n nlog2n)、O( n 2 n^{2} n2)、O( n 3 n^{3} n3)、O( 2 n
2^{n} 2n)、O(n!)。
四个时间复杂度
同一段代码在不同输入的情况下，可能存在时间复杂度量级不一样的情况，所以有以下四种不同的时间复杂度。
最好情况时间复杂度（best case time complexity）；
最坏情况时间复杂度（worst case time complexity）；
平均情况时间复杂度（average case time complexity）；
均摊时间复杂度（amortized time complexity）。
1、最好、最坏、平均情况时间复杂度
// n表示数组array的长度 int find(int *array, int n, int x) { int i = 0; int pos = -1; for ( ; i < n; ++i) { if (array[i] == x) { pos = i; break; } } return pos; }
这是一个find()函数，这段代码的作用是查找参数x在数组array中的位置，如果没有就返回-1。
最好情况时间复杂度：
在最理想的情况下，代码的时间复杂度。本例中，如果数组中的第一个元素就是要查找的变量，则时间复杂度为O(1)。
最坏情况时间复杂度：
在最糟糕的情况下，代码的时间复杂度。本例中，如果数组中没有变量x，则需要遍历数组中的每一个元素，则时间复杂度为O(n)。
平均情况时间复杂度：
最好、最坏情况时间复杂度表示的都是代码在极端情况下的时间复杂度，发生的概率并不大，所以平均情况时间复杂度用于表示平均情况下的时间复杂度。
本例中，首先，变量x分为在数组中和不在数组中两种情况，假设两种情况的概率相同为；其次，要查找的变量出现在数组0 ~ n-1共n个位置的概率是一样的，都为；最后，根据概率论的知识，变量x出现在0 ~ n-1这n个位置的概率都为，变量不在数组中的概率为。
根据概率论中的加权平均值，也叫期望值的计算放法（每一种情况下的时间复杂度乘以其发生的概率）得出平均时间复杂度的值：
用大O表示法表示，则平均时间复杂度为O(n)，所以平均时间复杂度又叫加权平均时间复杂度，或者期望时间复杂度。
一般情况下，我们并不会区分这三种时间复杂度，只使用其中一种即可。当同一代码块在不同情况下的时间复杂度有量级上的差距，才会区分这三种复杂度。
2、均摊时间复杂度
由上述可知，一般情况下，并不区分最好、最坏、平均情况时间复杂度，平均情况时间复杂度也只有在某些特殊的情况下才会使用，而均摊时间复杂度的应用场景比平均复杂度更特殊，更有限。
// array表示一个长度为n的数组 // 代码中的array.length就等于n int *array = new int[n]; int count = 0; void insert(int val) { if (count == array.length) { int sum = 0; for (int i = 0; i < array.length; ++i) { sum = sum + array[i]; } array[0] = sum; count = 1; } array[count] = val; ++count; }
这是一个insert()函数，实现往数组中插入一个数据的功能，如果数组满了的话，即当count == array.length时，遍历数组求和，并把数据放到数组第一个位置，然后再把新的数据插入。
本段代码的时间复杂度分析：
最好情况时间复杂度：数组未满，有空闲的位置时为O(1)；
最坏情况时间复杂度：数组已满，需要遍历求和时为O(n)；
平均情况时间复杂度：分为数组未满和已满两种情况，未满时的插入有n种情况，每种情况的时间复杂度为O(1)，已满时的时间复杂度度为O(n)，所以共n+1种可能，这n+1种可能的概率相同都是，所以平均情况时间复杂度为：
2）、均摊时间复杂度
本例中的insert()函数区别于之前的find()函数：find()函数在极端情况下，时间复杂度为O(1)，而insert()函数在大多数情况下时间复杂度都为O(1)；find()函数时间复杂度的多种情况并没有任何规律。而insert()函数O(n)之后，必有n-1个O(1)，循环往复。
针对这种特殊的场景，可以采用一种特殊的时间复杂度分析方法：摊还分析法，得出的是均摊时间复杂度。
分析方法：
因为时间复杂度有规律的在O(n) -> n-1个O(1)之间循环，所以把耗时最多的那次操作（O(n)），均摊到耗时最少的n-1次操作（O(1)），这样，每一组操作的时间复杂度都是O(1)，即均摊时间复杂度为O(1)。
应用场景：
均摊时间复杂度就是一种特殊的平均情况时间复杂度，没有必要过度区分。当大部分情况下的时间复杂度较低，而只有极少数情况下的时间复杂度较高，且这些情况的出现有固定的时序性规律时，使用均摊时间复杂度。这时，尝试将较高复杂度操作的耗时均摊到较低复杂度的操作上，这就叫摊还分析法。
一般能应用摊还分析法的场景，均摊时间复杂度就等于最好情况时间复杂度
2.空间复杂度
程序从开始执行到结束所需要的内存容量，也就是整个过程中最大需要占用多少的空间。为了评估算法本身，输入数据所占用的空间不会考虑，通常更关注算法运行时需要额外定义多少临时变量或多少存储结构。如：如果需要借助一个临时变量来进行两个元素的交换，则空间复杂度为O(1)。
时间复杂度
最坏的情况
最坏的情况就是完整的遍历了整个集合，也并未找到目标的key，此时循环被完整的执行，循环执行次数与n相关，所以时间复杂度为O(n) 。
最好的情况
最好的情况就是第一次就找到了元素，此时的时间复杂度为常数级O(1) 。
平均情况
综合两种情况，顺序查找的时间复杂度为O(n) ，属于查找较慢的算法。
3. 空间复杂度
由于算法不会改变原有的元素集合，只需要一个额外的变量控制索引变化，所以空间复杂度为常数级：O(1) 。
空间复杂度涉及的空间类型有：
输入空间： 存储输入数据所需的空间大小；
暂存空间： 算法运行过程中，存储所有中间变量和对象等数据所需的空间大小；
输出空间： 算法运行返回时，存储输出数据所需的空间大小；
通常情况下，空间复杂度指在输入数据大小为 N 时，算法运行所使用的「暂存空间」+「输出空间」的总体大小。
而根据不同来源，算法使用的内存空间分为三类：
指令空间：
编译后，程序指令所使用的内存空间。
数据空间：
算法中的各项变量使用的空间，包括：声明的常量、变量、动态数组、动态对象等使用的内存空间。
struct Node { int val; Node *next; Node(int x) : val(x), next(NULL) {} }; void algorithm(int N) { int num = N; // 变量 int nums[N]; // 动态数组 Node* node = new Node(N); // 动态对象 }
栈帧空间：
程序调用函数是基于栈实现的，函数在调用期间，占用常量大小的栈帧空间，直至返回后释放。如以下代码所示，在循环中调用函数，每轮调用 test() 返回后，栈帧空间已被释放，因此空间复杂度仍为 O(1)。
int test() { return 0; } void algorithm(int N) { for (int i = 0; i < N; i++) { test(); } }
算法中，栈帧空间的累计常出现于递归调用。如以下代码所示，通过递归调用，会同时存在 N 个未返回的函数 algorithm() ，此时累计使用 O(N) 大小的栈帧空间。
int algorithm(int N) { if (N <= 1) return 1; return algorithm(N - 1) + 1; }
根据从小到大排列，常见的算法空间复杂度有：
O(1) < O(logN) < O(N) < O(N^2) < O(2^N)
只做简单概念简读；具体可查看 博客
