数据结构——时间复杂度

数据结构笔记目录：

1. 绪论、时间复杂度
2. 线性表
3. 树
4. 图
5. 查找
6. 排序

---

0. 基本概念

0.1 数据类型

值+操作的集合

• 原子类型
• 结构类型
• 抽象数据类型(ADT)：可用于定义一个完整数据类型 、 数据结构

ADT

一个数学模型及定义在该模型上的一组操作

ADT{
	数据对象：<数据对象的定义> D
	数据关系：<数据关系的定义> S
	基本操作：<基本操作的定义> P
}
1
2
3
4
5

0.2 数据结构

存在一种或多种特定关系(逻辑结构)的数据元素集合

• 逻辑结构 独立于 存储结构

四种逻辑结构

• 集合
• 线性结构
• 树形结构
• 网状结构

两种存储结构

• 顺序存储
• 链式存储
• (哈希)
• (索引)

0.3 算法

特定问题的求解步骤

特性

• 有穷性
  • 程序 $\ne$ 算法
    • 程序不一定有穷：死循环，操作系统
• 确定性
• 可行性
• 输入
• (至少一个)输出

目标

• 正确
• 可读
• 健壮
• 高效低存储

时间复杂度的简单计算方法

参考数据结构实现的黑书

1. 时间复杂度

1.1 概念

算法的渐进时间复杂度，简称时间复杂度

事前分析

1. 算法采用的策略和方案
2. 编译产生代码质量
3. 问题的输入规模
4. 机器执行指令的速度

将核心操作的次数与输入规模关联

1.1.1 函数渐进增长

给定两个函数 $f(n)$ 和 $g(n)$ ,如果存在一个整数 $N$ 使得对于所有 $n>N$ , $f(n)$ 总是比 $g(n)$ 大，那么称 $f(n)$ 的渐进增长快于 $g(n)$

• 算法函数中的常数、系数可以忽略
• 算法函数中最高次幂越小，算法效率越高

1.1.2 大O记法

语句总的执行次数 $T(n)$ 是关于问题规模 $n$ 的函数，进而分析 $T(n)$ 随着 $n$ 的变化情况并确定 $T(n)$ 的量级。记为 $T(n)=O(f(n))$

表示随着问题规模 $n$ 的增大，算法执行时间的增长率和 $f(n)$ 的增长率相同

• $f(n)$ 表示问题规模 n 的某个函数

• 执行次数 $⟺$ 执行时间

规则

• 用1代替运行时间中的所有常数、系数
• 在修改后的次数中，只保留高阶项

1-100求和

# 累加
int main(){
	int sum = 0;//执行一次
	int n = 100;//执行一次
	for(int i = 0; i < n;++i){//判断语句执行n+1次
		sum += i;//执行n次数
	}	

	printf("sum=%d",sum);
}
# 执行 2n+3 次
# 大O记法 O(n)
# -------------------------------------------
# 高斯公式
void main(){
	int sum = 0;//执行1次
	int n = 100;//执行1次
	sum = (n+1)n/2;//执行1次
	printf("sum=%d",sum);
}
# 执行3次
# 大O记法 O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

最坏情况

直接查找

int search(int num){
	int arr[] = [11,10,8,9,7,22,23,0];
	
	for(int i = 0;i < arr.length;++i){
		if(num == arr[i])
			return i;
	}

	return -1;
}
1
2
3
4
5
6
7
8
9
10

最好情况:

• 查找的第一个数字就是期望数字—— $O(1)$

最坏情况:

• 查找的最后一个数字，才是期望数字——$O(n)$

平均情况:

• 任何数字查找的平均代价为 ——$O(n)$

1.1.3 时间复杂度排序

$O(1)<O(logn)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$

1.2 简单时间复杂度分析

1.2.1 非函数调用

1. 线性阶

   非嵌套线性阶，随输入规模的扩大，呈 线性增长

   int sum = 0;//执行一次
   int n = 100;//执行一次
   for(int i = 0; i <= n;++i){//执行n+1次
   	sum += i;//执行n次数
   }
   1
   2
   3
   4
   5

2. 平方阶

   二重循环嵌套

   int sum = 0;
   int n = 100;
   for(int i = 1;i <= n;++i){//执行 n+1 次
   	for (j = 1;j <= n;++j){//执行 n*(n+1) 次
   		sum += i;//执行 n^2 次
   	}
   }
   1
   2
   3
   4
   5
   6
   7

3. 立方阶

   三重循环嵌套

4. 对数阶

   对数阶，由于输入规模n的增大，不管底数多少，增长率都相同，所以忽略底数

   int i=1,n=100;
   while(i < n){
   	i = i*2;
   }
   1
   2
   3
   4

   循环次数：$x=log\ast 2n$
   时间复杂度：$O(logn)$

5. 常数阶

1.2.3 函数调用

void main(){
    int n = 100;
    for(int i = 0;i < n;++i){
	    show(i);	// O(n)
    }
}

void show(int i){
    printf("%d",i);
}
1
2
3
4
5
6
7
8
9
10

void main(){
	int n = 100;
	for(int i = 0;i < n;++i){
		show(i);	//O(n^2)
	}
}

void show(int i){
	for(int j = 0;j < i;++j){		
		printf("%d",i);
	}	
}
1
2
3
4
5
6
7
8
9
10
11
12

1.3 计算方法

1.3.0 常规

• for 循环
• 一次 for 循环至多是该 for 循环包含的 内语句运行次数 乘 迭代次数
• 嵌套的 for 循环
• 从里到外分析循环
• 顺序语句
• 各语句运行时间求和
• if/else 语句
• 两执行函数中运行时间长的

1.3.1 循环主体中的变量参与循环条件的判断

找出主体语句中与 $T(n)$ 成正比的循环变量，将之代入条件运算

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

• 执行次数 $t$ ，有 $2^t\le n$ ,得 $T(n)=O(log\ast 2n)$

int y = 5;
while((y+1)*(y+1)<=n){
	y = y+1;
}
1
2
3
4

• 执行次数 $t=y-5$ ,有 $y=t+5$,代入得 $t<\sqrt{n}-6$,即 T(n) = O($\sqrt{n}$)

运算时间中的对数

• 如果一个算法用时间 $O(1)$ 将问题的大小削减为原来的一部分，那么该算法就是$O(logN)$
• 如果用常数时间把问题减少一个常数，那么这种算法就是 $O(N)$

折半查找

int BinarySearch(const ElementType A[],ElementType X,int N){
	int Low,Mid,High;
	Low = 0,High = N-1;
	while(Low <= High){
		Mid = (Low+High)/2;
		if(A[Mid] < X){
			Low = Mid + 1;
		}else{
			if(A[Mid] > X){
				High = Mid-1;
			else
				return Mid; //Found
		}
	}
	return NotFound; //NotFound is defined as -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

分析：提供了 $O(logN)$ 以内的查找操作

欧几里得算法

定理：如果 $M>N$ ,则 KaTeX parse error: Undefined control sequence: \mbox at position 3: M \̲m̲b̲o̲x̲{ mod N} < \fra…

unsigned int Gcd(unsigned int M,unsigned int N){
	unSigned int Rem;
	while(N > 0){
		Rem = M % N;
		M = N;
		N = Rem;
	}
	return M;
}
1
2
3
4
5
6
7
8
9

幂运算 $O(logn)$

long int Pow(long int X,unsigned int N){
	if(N == 0)
		return 1;
	if(N == 1)
		return X;
	if(isEven(N))
		return Pow(X*X,N/2);
	else 
		return Pow(X*X,N/2) * X;
}
1
2
3
4
5
6
7
8
9
10

1.3.2 循环主体中的变量与循环条件无关

采用 归纳法 或 累计循环次数

多层循环从内到外分析，忽略单步语句、条件判断语句，只关注主体语句的执行次数

递归程序——分治策略

递归程序四条准则

• 基准情形：有结束条件
• 不断推进：每次调用都朝向基准情形推进
• 设计法则：假设所有的递归调用都能进行
• 合成效益法则：避免重复计算

“分治”策略

• ”分“：将大问题大致分为两大致相等的 幂次阶 子问题，用递归求解
• “治”：将两个子问题的解合并到一起并可能再做些少量的附加工作（幂次阶），得到整个问题的解

主方法 ：大小为 $n$ 的原问题分成若干个大小为 $\frac{n}{b}$ 的子问题，其中 $a$ 个子问题需要求解，而 $c{n}^k$ 是合并各个子问题需要的工作量。此时问题可表示为：
T ( N ) = { c n = 1 a T ( N b ) + c n k n > 1 T(N)={cn=1aT(Nb)+cnkn>1

T(N)={caT(bN​)+cnk​n=1n>1​

则其时间复杂度可相应的表示为：

T ( N ) = { O ( n l o g b a ) a > b k O ( n k l o g b n ) a = b k O ( n k ) a < b k T(N)={O(nlogba)a>bkO(nklogbn)a=bkO(nk)a<bk

T(N)=⎩ ⎨ ⎧​O(nlogb​a)O(nklogb​n)O(nk)​a>bka=bka<bk​

推导

已知

{ T ( 1 ) = 1 T ( N ) = 2 T ( N 2 ) + O ( N ) {T(1)=1T(N)=2T(N2)+O(N)

{T(1)=1T(N)=2T(2N​)+O(N)​

1. 等号右边连续代入递归关系
T ( N ) = 2 T ( N 2 ) + N = 2 [ 2 T ( N 4 ) + N 2 ] + N = 2 { 2 [ 2 T ( N 8 ) + N 4 ] + N 2 } + N = . . . = 2 k T ( N 2 k ) + k N T(N)=2T(N2)+N=2[2T(N4)+N2]+N=2{2[2T(N8)+N4]+N2}+N=...=2kT(N2k)+kN

T(N)​=2T(2N​)+N=2[2T(4N​)+2N​]+N=2{2[2T(8N​)+4N​]+2N​}+N=...=2kT(2kN​)+kN​

由 $k=logN$ 得

$$T(n)=NT(1)+NlogN=Nlog(N)+N$$

2. 叠缩求和

用 N 去除递归关系中的两边，不断替换

T ( N ) N = T ( N 2 ) N 2 + 1 T ( N 2 ) N 2 = T ( N 4 ) N 4 + 1 T ( N 4 ) N 4 = T ( N 8 ) N 8 + 1 ⋮ ⋮ T ( 2 ) 2 = T ( 1 ) 1 + 1 T(N)N=T(N2)N2+1T(N2)N2=T(N4)N4+1T(N4)N4=T(N8)N8+1⋮⋮T(2)2=T(1)1+1

NT(N)​2N​T(2N​)​4N​T(4N​)​⋮⋮2T(2)​​=2N​T(2N​)​+1=4N​T(4N​)​+1=8N​T(8N​)​+1=1T(1)​+1​​

将等号左边的所有相相加等于右边所有项的和，结果为

T ( N ) N = T ( 1 ) 1 + l o g N = N l o g ( N ) + N T(N)N=T(1)1+logN=Nlog(N)+N

NT(N)​​=1T(1)​+logN=Nlog(N)+N​

1.4 常见算法时间复杂度总结

1.5 最大子序列和问题的解

1.5.1 遍历所有子串，对子串的子序列依次求和

int MaxSubSequenceSum(const int A[],int N){
	int ThisSum,MaxSum,i,j,k;
	MaxSum = 0;
	for(i = 0;i < N;++i){
		for(j = i;j < N;++j){//遍历所有子串
			ThisSum = 0;
			for(k = i;k <= j;++k)//当前子串的所有子序列求和
				ThisSum += A[k];
				if(ThisSum > MaxSum)
					MaxSum = ThisSum;	
		}
	}
	return MaxSum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

∑ i = 0 N − 1 ∑ j = i N − 1 ∑ k = i j 1 ∑ k = i j 1 = j − i + 1 ∑ j = i N − 1 j − i + 1 = ( N − i + 1 ) ( N − i ) 2 ∑ i = 0 N − 1 ( N − i + 1 ) ( N − i ) 2 = ∑ i = 1 N ( N − i + 1 ) ( N − i ) 2 = 1 2 ∑ i = 1 N i 2 − ( N + 3 2 ) ∑ i = 1 N i + 1 2 ( N 2 + 3 N + 2 ) ∑ i = 1 N 1 = N 3 + 3 N 2 + 2 N 6 N−1∑i=0N−1∑j=ij∑k=i1j∑k=i1=j−i+1N−1∑j=ij−i+1=(N−i+1)(N−i)2N−1∑i=0(N−i+1)(N−i)2=N∑i=1(N−i+1)(N−i)2=12N∑i=1i2−(N+32)N∑i=1i+12(N2+3N+2)N∑i=11=N3+3N2+2N6

i=0∑N−1​j=i∑N−1​k=i∑j​1k=i∑j​1j=i∑N−1​j−i+1i=0∑N−1​2(N−i+1)(N−i)​​=j−i+1=2(N−i+1)(N−i)​=i=1∑N​2(N−i+1)(N−i)​=21​i=1∑N​i2−(N+23​)i=1∑N​i+21​(N2+3N+2)i=1∑N​1=6N3+3N2+2N​​

时间复杂度为 $O(N^3)$

1.5.2 记录中间累加量

$$\sum _{k=i}^j{A}_k=A_j+\sum _{k=i}^{j-1}{A}_k$$

int MaxSubSequenceSum(const int A[],int N){
	int ThisSum,MaxSum,i,j,k;
	
	MaxSum = 0;
	for(i = 0;i < N;++i){
		ThisSum = 0;
		for(j = i;j < N;++j){//遍历所有子串
			ThisSum += A[k];

			if(ThisSum > MaxSum){
				MaxSum = ThisSum;
			}				
	}
	return MaxSum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度为 $O(N^2)$

1.5.3 分治法

将序列分成大致相等的两部分。

最大子序列和可能在三处出现：

• 数据的左半部分；
• 递归求解
• 数据的右半部分；
• 递归求解
• 中间部分
• 分别求出前、后部分的最大和，相加中间部分最大和

int MaxSubSum(const int A[],int Left,int Right){
	int MaxLeftSum,MaxRightSum;
	int MaxLeftBorderSum,MaxRightBorderSum;
	int LeftBorderSum,RightBorderSum;
	int Center,i;

	if(Left == Right){//只有一个元素
		if(A[Left] > 0)//该元素非负即为最大和
			return A[Left];
		else{
			return 0;
		}
	}
	
	Center = (Left+Right) / 2;
	MaxLeftSum = MaxSubSum(A,Left,Center);
	MaxRightSum = MaxSubSum(A,Center,Right);

	MaxLeftBorderSum = 0,LeftBorderSum = 0;
	for(i = Center;i >= Left;i--){
		LeftBorderSum += A[i];
		if(LeftBorderSum > MaxLeftBorderSum)
			MaxLeftBorderSum = LeftBorderSum;
	}

	MaxRightBorderSum = 0,RightBorderSum = 0;
	for(i = Center;i >= Left;i--){
		RightBorderSum += A[i];
		if(RightBorderSum > MaxRightBorderSum)
			MaxRightBorderSum = RightBorderSum;
	}

	return Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum);
}

int MaxSubSequenceSum(Const A[],int N){
	return MaxSubSum(A,0,N-1);
}
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

{ T ( 1 ) = 1 T ( N ) = 2 T ( N / 2 ) + O ( N ) {T(1)=1T(N)=2T(N/2)+O(N)

{T(1)=1T(N)=2T(N/2)+O(N)​

时间复杂度为 $O(NlogN)$

分治法 时间复杂度一般都是若干个代价为 $logN$ 的子问题与一个处理函数的代价和

1.5.4 最简

int MaxSubSequenceSum(const int A[],int N){
	int ThisSum,MaxSum,j;	
	ThisSum = MaxSum = 0;
		for(j = 0;j < N;++j){
			ThisSum += A[k];

			if(ThisSum > MaxSum){
				MaxSum = ThisSum;
			}else if(ThisSum < 0){
				ThisSum = 0;
			}				
	}
	return MaxSum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度为 $O(N)$

空间复杂度

算法所需的辅助空间数量级

• 运行过程中变量占用的空间 辅助数组
• 递归工作栈 递归深度

原地工作

算法所需的辅助空间为常量