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

发布于:2023-01-20 ⋅ 阅读:(14) ⋅ 点赞:(0) ⋅ 评论:(0)

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(n2),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.均摊时间复杂度

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