前记

　　众所周知，数据结构和算法是编程当中的内功，只有把内功修炼深厚，才能应对各种招式的变化。如果每天做一些机械性质的增删改查，那是注定在编程道路上走不远的，因此，从本篇开始，进行数据结构和算法的学习，并以笔记的形式进行知识点的总结。

基本复杂度分析

　　复杂度分析是算法学习的精髓，可以说掌握了复杂度分析，算法学习就成功了一半。而最常用的复杂度表示方法就是大O表示法，这是表示代码执行时间或所占空间随数据规模增长的变化趋势的一种方法。当n很大时，你可以把它想象成100000，而公式中的低阶、常量、系数三部分并不影响增长趋势，所以都可以忽略，我们只需保留一个最大量级就可以了。

时间复杂度分析

　　1 只关注循环执行次数最多的一段代码。
　　2 加法法则：总的时间复杂度等于量级最大的那段代码的时间复杂度。即抽象公式：T(n)=T1(n)+T2(n)=Max(O(f(n)),O(g(n)))。
　　3 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。
　　常见的复杂度有O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)、O(2^n)、O(n!)，其中O(2^n)和O(n!)为非多项式量级。
　　O(logn)比较难以分析，借用以下例子加以理解：

i = 1;
while(i <= n){
	i = i * 2;
}

可以看出i从1开始，每次循环就乘以2，当大于n时，循环结束，因此可以看出这是一个等比数列：2^0,2^1,2^2,2^3……2^k = n，其中k代表执行的次数，即k=logn（以2为底，用大O表示的话可以省略底数）。
　　另外，还有一种非寻常的情况，即代码的复杂度由两个数据的规模来决定，如下：

int cal(int m, int n) {
	int sum_1 = 0;
	int i = 1;
	for (; i < m; ++i) {
		sum_1 = sum_1 + i;
	}
	int sum_2 = 0;
	int j = 1;
	for (; j < n; ++j) {
		sum_2 = sum_2 + j;
	}
	return sum_1 + sum_2;
}

可以看出，m和n表示两个数据规模，我们无法事先评估,m和n谁的量级大，所以复杂度就是O(m+n)。

空间复杂度分析

　　空间复杂度一般比较简单，能够通过肉眼看出来，例如下面代码：

void print(int n) {
	int i = 0;
	int[] a = new int[n];
	for (i; i <n; ++i) {
		a[i] = i * i;
	}
	for (i = n-1; i >= 0; --i) {
		print out a[i]
	}
}

　　可以看到，申请了一个大小为n的int类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是O(n)。

最好、最坏时间复杂度

　　顾名思义，最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度。同理，最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。看代码：

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;
}

　　上述代码中，在一个数组中查找x，如果x是第一个数，则最快，而如果x不存在数组中，则要遍历n次，因此，最好复杂度O(1)，最坏复杂度O(n)。

平均情况时间复杂度

　　还是上述代码，为了方便你理解，我们假设在数组中与不在数组中的概率都为1/2。另外，要查找的数据出现在0～n-1这n个位置的概率也是一样的，为1/n。所以，根据概率乘法法则，要查找的数据出现在0～n-1中任意位置的概率就是1/(2n)。因此平均时间复杂度的计算过程为：1/2n+2/2n+……+n/2n+n/2=(3n+1)/4。这个值就是加权平均值，用大O法表示即：O(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;
}

　　这段代码实现了一个往数组中插入数据的功能。当数组满了之后，也就是代码中的 count == array.length 时，我们用for循环遍历数组求和，并清空数组，将求和之后的sum值放到数组的第一个位置，然后再将新的数据插入。但如果数组一开始就有空闲空间，则直接将数据插入数组。
　　最理想的情况下，数组中有空闲空间，我们只需要将数据插入到数组下标为count的位置就可以了，所以最好情况时间复杂度为O(1)。最坏的情况下，数组中没有空闲空间了，我们需要先做一次数组的遍历求和，然后再将数据插入，所以最坏情况时间复杂度为O(n)。
　　假设数组的长度是n，根据数据插入的位置的不同，我们可以分为n种情况，每种情况的时间复杂度是O(1)。除此之外，还有一种“额外”的情况，就是在数组没有空闲空间时插入一个数据，这个时候的时间复杂度是O(n)。而且，这n+1种情况发生的概率一样，都是1/(n+1)。所以，根据加权平均的计算方法，我们求得的平均时间复杂度就是：1/(n+1)+1/(n+1)+……+n/(n+1)=O(1)。
　　每一次O(n)的插入操作，都会跟着n-1次O(1)的插入操作，所以把耗时多的那次操作均摊到接下来的n-1次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是O(1)。这就是均摊分析的大致思路。
　　对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系（即有规律），这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。