OK,在我们学习数据结构之前我们来先了解一个概念——-时间复杂度和空间复杂度还有抽象数据类型

开发者请注意,如果不感兴趣请不要看本篇文章,因为这都是理论性质的东西,只适合那些考试党

时间复杂度

时间复杂度,也称渐进时间复杂度,T(n)=O(f(n))

image-20251225233723152

随着问题规模n的增大,算法执行时间和增长率和f(n)增长率成正比

说人话就是:

时间复杂度 = 干活要花多少“时间”

举个例子

劳埃德给阿尼亚买了很多花生零食并嘱咐阿尼亚一次只能吃一袋,但是阿尼亚会选择吃完后继续偷吃,可不可以吃完一袋花生取决于阿尼亚酱的咀嚼速度,假如阿尼亚每次吃一个花生的速度和吞一整袋花生的速度一样,则称之为时间复杂度低,但是如果阿尼亚嘴里每增加一个花生,导致咀嚼的速度下降,结果直到黄昏回家被发现了也没吃完,这就是时间复杂度高

低复杂度 O(1)：
“无论劳埃德买1袋还是10袋花生，阿尼亚狂风吸入，所以黄昏回家前一定不被发现”

高复杂度 O(n²)：
“阿尼亚嘴里每多塞一颗1颗，咀嚼速度就慢一半，结果吃到第10颗时，单颗就要嚼好几分钟, 完了 ,那个间谍老爹回家了,来不及藏花生包装袋了 !!!”

​ img

我们可以用一个图来描述

​ image-20251225105702011

当然我们也可以用一些题目来解释,这样更直观

1
2
3
4
5
6
7
8
9
10
11
//计算频率
//for(int i=1;i<=n;i++){//频率为n+1
//	for(int j=1;j<=n;j++){//频率为n*(n+1)
//		c[i][j]=0;//频率为n*n
//		for(int k=1;k<=n;k++){//频率为n*n*(n+1)
//			c[i][j]=c[i][j]+a[i][k]+b[k][j];//频率为n*n*n
//		}
//	}
//}
//f(n)=n+1+n*(n+1)+n*n+n*n*(n+1)+n*n*n
//即f(n)=2*n*n*n+3*n*n+2n+1  则T(n)=O(n[3])

以下公式用a()括起来的表示排序数字,用n[]括起来的表示次幂
若f(n)=a(m)n[m]+a(m-1)n[m-1]+….+a(1)n+a(0) 是一个m次多项式
则T(n)=O(n[m])在计算算法时间复杂度时,可以忽略所有低次幂和最高次幂的系数
这样可以简化算法分析也体现出增长率的含义

image-20251225233758454

根据时间复杂度可以分为如下几种(虽然没什么鸟用)

  • 最好时间复杂度:算法在最好情况下的时间复杂度
  • 最坏时间复杂度:算法在最坏情况下的时间复杂度
  • 平均时间复杂度:算法在所有可能的情况下,按照输入实例乙等概率出现时,算法计量的加权平均值对算法时间复杂度的度量,通常只讨论算法在最坏情况下的时间复杂度,即分析在最坏情况下算法执行时间的上界

实际上如果算法执行时间,不随问题n的增长而增长,那么算法当中的语句频率就是某个常数,比如 1

1
2
3
4
5
6
7
8
9
10
11
12
//例如:
//x++;
//s=0;
//f(n)=1+1=2
//T(n)=O(1)

//例如:
//for(int i=0;i<10000;i++){
//	x++;
//	s=0;
//}
//T(n)=O(1)

如果随着问题n的增长而增长的话就是n次幂或者n的对数阶层什么的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//例如:
//for(int i=0;i<n;i++){
//	x++;
//	s=0;
//}
//f(n)=(n+1)+n+n=3n+1
//T(n)=O(n)

//例如:
//x=0;
//y=0;
//for(int k=0;k<=n;k++){
//	x++;
//}
//for(int i=1;i<=n;i++){
//	for(int j=1;j<=n;j++){
//		y++;
//	}
//}
//f(n)=1+1+(n+1)+n+(n+1)+n(n+1)+n*n=2*n*n+4n+4
//T(n)=O(n[2])


//例如:
//x=1;   //1
//for(int i=1;i<=n;i++){	//n
//	
//	for(int j=1;j<=i;j++){	// n(n+1)/2
//		
//		for(int k=0;k<=j;k++){	//[n(n+1)(n+2)]/6
//			x++;
//		}
//	}
//}
//T(n)=O(n[3])


//例如:
//for(int i=1;i<=n;i=i*2){
//	x++;
//	s=0;
//}
//x循环次数为2[t-1]
//2[t-1]>n
//log(2)2[t-1]>log(2)n
//t-1>log(2)n
//t>log(2)n+1
//T(n)=log(2)n+1=O(log(2)n)

​ 计算时间复杂度-01

这里还有有一些没什么实际用途的题目

1
2
3
4
5
6
7
8
9
10
11
12
//例如:设n是描述问题规模的非负整数,下面程序片段的时间复杂度是__A__。
//x=2;
//while(x<n/2)
//		x=2*x;
//
//A.O(log(2)n)   B.O(n)   C.O(nlog(2)n)	  D.O(n[2])
//x的循环次数为2[t+1]
//2[t+1]=n/2
//2[t+2]=n
//log(2)2[t+2]=log(2)n
//t+2=log(2)n
//T(n)=log(2)n-2=O(log(2)n)

​

​ 计算时间复杂度-02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//例如:下列函数的时间复杂度是
//int fun(int n){
//	int i=0,sum=0;
//	while(sum<n){
//		sum += ++i;
//		return i;
//	}
//}
//A.O(logn)   B.O(n[1/2])   C.O(n)   D.O(nlogn)
//
//t(t+1)/2=n
//t(t+1)=2n
//t[2]+t=2n
//t[2]=2n
//t=(2n)[1/2]
//T(n)=O(n[1/2])=O(n[1/2])

​ 计算时间复杂度-03

1
2
3
4
5
6
7
8
9
//例如:设n是描述问题规模的非负整数,下列程序的时间复杂度是__B__
//x=0;
//while(n>=(x+1)(x+1))
//		x=x+1;
//A.O(logn)   B.O(n[1/2])   C.O(n)   D.O(n[2])
//n<(x+1)[2]
//n[1/2]<x+1
//n[1/2]-1<x
//T(n)=O(n[1/2])=O(n[1/2])
计算时间复杂度-04 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//例如:下列程序的时间复杂度是__B__
//int sum=0;
//for(int i=1;i<n;i*=2){
//	for(int j=1;j<i;j++){
//		sum++;
//	}
//}
//A.O(logn)   B.O(n)   C.O(nlogn)   D.O(n[2])
//外层循环
//2[t-1]=n
//log(2)2[t-1]=log(2)n
//t-1=log(2)n
//t=log(2)n+1
//内层循环
//1+2+4+....+2[t-1]
//=1+2+4+....+2[log(2[n+1-1])]
//=1+2+4+....+2[log(2[n])]
//=1*(1-2[log(2[n])])/(1-2)
//=n-1
//T(n)=n-1=O(n)

空间复杂度

空间复杂度主要用来描述某个算法对应的程序想在计算机上执行,除了用来存储代码和输入数据的内存空间外,还需要额外的空间

说白了就是 空间复杂度 就是占多少“地方 / 内存”

翻译成 人话就是:

空间复杂度 = 为了做这件事，你额外用了多少“盒子 / 本子 / 内存”

公式就是

​ image-20251225233822668

抽象数据类型ADT(Abstract Data Type)

定义如下:

ADT是一种编程概念,用于定义数据的类型及其操作,而不涉及具体实现细节。
它提供了一种将数据的逻辑表示与物理实现分离的方法,从而使程序更具可维护性和可扩展性
在C语言中,ADT通常通过结构体和函数的结合来实现。结构体用于定义数据的类型，而函数用于操作这些数据。
通过这种方式，程序员可以隐藏数据的内部结构，仅暴露出操作数据的接口。

如果在Unity中用过接口的小伙伴一定老熟悉这玩意了—–即抽象

例如把要实现个功能封装到类中,外界只需要使用这个命名空间里的类的的方法即可

虽然很多人表示抽象会降低代码的质量,但是在很多框架里抽象是离不开的

这里我们举一个例子——比如设计一个计算复数的功能并封装到函数里

ADT

不过这个本质上只是一种设计概念,开发中用的比较多,我们这里只是讲数据结构就不说了