数据结构与算法之美学习笔记（一）复杂度分析

1.为什么需要复杂度分析

（1）测试结构非常依赖测试环境
（2）测试结果受数据规模的影响很大

2.时间复杂度分析

（1）只关注循环执行次数最多一段代码
一般我们在分析一个算法、一段代码的时间复杂度时，只需要关注循环次数最多的那一段，因为时间复杂度的计算通常忽略公式的常量、低阶和系数，只需要统计最大阶的量级就可以了。

int print(int n,int m) {
	int a[2][5] = {1,2,3,4,5,6,7,8,9,10};
	int b[5] = {1,2,3,4,5};
	for(int i=0;i<n;i++,cout<<endl) {
		for(int j=0;j<m;j++,cout<<' '){
			cout<<a[i][j];
		}
	}
	for(int i=0;i<n;i++,cout<<' ') {
		cout<<b[i];
	}
	cout<<endl;
	cout<<n<<' '<<m;
	return 0;
}

如在以上代码中循环次数最多的代码是遍历a数组的一段二重循环，因此该段代码的时间复杂的就是O(n^2)
(2)加法法则：总复杂度等于量级最大的那段代码的复杂度
(3)乘法法则：嵌套代码的复杂度等于嵌套内外代码的复杂度的乘积

int sum(int a[],int n) {
	int tot = 0;
	for(int i=0;i<n;i++){
		tot+=a[i];
	}
	return a[i];
}

int sum_all(int a[][m],int n,int m){
	int tot = 0;
	for(int i=0;i<n;i++) {
		tot+=sum(a[i],m);
	}
	return tot;
}

如以上代码，一个函数的循环中，调用了另外一个函数，我们首先分析出第一个函数sum的时间复杂度是O(m),然后在sum_all函数中，循环体的时间复杂度是O(n),基于乘法原则，最后的总时间复杂度为O(n*m)

3.常见时间复杂度

（1）常量阶O(1)
（2）对数阶O(logn)
（3）线性阶O(n)
（4）线性对数阶O(nlogn)
（5）幂次阶O(n^2),O(n3),O(n^k)
（6）指数阶O(2^n)
（7）阶乘阶O(n!)

4.空间复杂度分析

空间复杂度通常是分析代码段执行过程中所占用的空间量级

int fun(int n){
	int a[] = new int [n]; 
}

如在以上代码段中，定义了一个大小为n的一维数组，因此该代码段的空间复杂的就是O(n)

5.最好、最坏情况时间复杂度

（1）最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度
（2）最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度

6.平均时间复杂度

将代码段中的所有可能情况*概率的和加起来除以所有情况的总数得到的加权平均值（期望）就是算法的平均时间复杂度

7.均摊时间复杂度

将一组操作中，耗时多的那次操作，均摊到剩余耗时时间少的操作身上，最后得到的就是均摊时间复杂度