【数据结构】时间复杂度和空间复杂度

前言
算法的时间复杂度和空间复杂度是两个核心概念，用来评估算法的效率。时间复杂度是指执行算法所需要的计算工作量，它决定了程序运行的速度。空间复杂度是指执行算法需要消耗多少内存空间。

---

一、时间复杂度

1.1 时间复杂度的概念

时间复杂度是衡量一个算法运行时间长短的指标，它反映了程序执行的步骤与输入数据之间的关系。在计算时间复杂度时，我们通常关注算法运行时间随输入数据规模增长的变化趋势，而不是具体的执行时间。这是因为具体的执行时间受到很多因素的影响，如硬件性能、操作系统、编程语言等，而时间复杂度则是一个更加抽象的概念，它是算法本身效率的体现。

时间复杂度通常用大O表示法来描述。这种表示法会忽略掉常数因子和低阶项，只关注最高阶项，因为在输入规模很大时，最高阶项对算法运行时间的影响最为显著。下面是一些常见的时间复杂度类别：

• O(1)：常数复杂度，算法的执行时间不随输入数据的大小变化而变化。
• O(log n)：对数复杂度，算法的执行时间是输入数据大小的对数函数，通常见于二分查找。
• O(n)：线性复杂度，算法的执行时间与输入数据的大小成正比，例如简单查找。
• O(n log n)：线性对数复杂度，常见于快速排序和归并排序。
• O(n^2)：平方复杂度，通常见于简单的双层循环算法，如冒泡排序。
• O(n^3)：立方复杂度，通常见于三层嵌套循环算法。
• O(2^n)：指数复杂度，算法的执行时间随数据规模的增加而呈指数增长，例如递归计算斐波那契数列。
• O(n!)：阶乘复杂度，随着n的增加，执行时间的增加速度非常快，通常见于解决旅行商问题的算法。

1.2 计算时间复杂度

如何计算时间复杂度？

1. 确定算法的基本操作：基本操作是算法中的一个明确的最小操作单位，通常是最频繁执行的操作。
2. 分析基本操作的执行次数：计算基本操作在整个算法中执行的总次数，这个数量可能依赖于输入的数据规模。
3. 用大O表示法表达执行次数：将基本操作的执行次数用大O表示法表示出来。

// 请计算一下Func1中++count语句总共执行了多少次？
void Func1(int N){	
	int count = 0;
	for (int i = 0; i < N; ++i){
		for (int j = 0; j < N; ++j){
			++count;
		}
	}

	for (int k = 0; k < 2 * N; ++k){
		++count;
	}
	
	int M = 10;
	while (M--){
		++count;
	}

	printf("%d\n", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

基本操作是 ++count；语句

Func1 执行的基本操作次数 ： $F(n)=N^2+2\ast N+10$

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，即取对时间影响最大的一项， 那么它的时间复杂度为O(n^2)。

---

最坏情况与平均情况
当谈论时间复杂度时，我们经常关注最坏情况的复杂度，因为这保证了算法在任何情况下的性能上限。然而，平均情况复杂度也很重要，它反映了算法在随机输入下的预期性能。

通过时间复杂度，我们可以对不同的算法进行效率上的比较，并选择适合当前问题和数据规模的最优算法。在实际应用中，理解和计算时间复杂度是非常重要的，它帮助我们识别

---

1.3 计算时间复杂度案例

实例1：

// 计算Func2的时间复杂度？
void Func2(int N){
	
	int count = 0;
	for (int k = 0; k < 2 * N; ++k){
		++count;
	}
	
	int M = 10;
	while (M--){
		++count;
	}
	printf("%d\n", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

实例2：

// 计算Func3的时间复杂度？
void Func3(int N, int M){
	int count = 0;
	for (int k = 0; k < M; ++k){
		++count;
	}
	
	for (int k = 0; k < N; ++k){
		++count;
	}
	
	printf("%d\n", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

实例3：

// 计算Func4的时间复杂度？
void Func4(int N){
	
	int count = 0;
	for (int k = 0; k < 100; ++k){
		++count;
	}
	
	printf("%d\n", count);
}
1
2
3
4
5
6
7
8
9
10

---

实例4：

// 计算strchr的时间复杂度？
const char * strchr ( const char * str, int character );
1
2

---

实例5;

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n){
	assert(a);
	for (size_t end = n; end > 0; --end){
		int exchange = 0;
		
		for (size_t i = 1; i < end; ++i){
			
			if (a[i - 1] > a[i]){
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		
		if (exchange == 0)
			break;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

实例6：

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x){
	assert(a);
	int begin = 0;
	int end = n - 1;
	
	while (begin <= end){
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid - 1;
		else
			return mid;
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

实例7：

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N){
	if (0 == N)
		return 1;

	return Fac(N - 1) * N;
}
1
2
3
4
5
6
7

---

实例8：

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N){
	if (N < 3)
		return 1;

	return Fib(N - 1) + Fib(N - 2);
}
1
2
3
4
5
6
7

---

答案：

1. 实例1基本操作执行了2N+10次，通过推导大O阶方法知道，时间复杂度为 O(N)
2. 实例2基本操作执行了M+N次，有两个未知数M和N，时间复杂度为 O(N+M)
3. 实例3基本操作执行了10次，通过推导大O阶方法，时间复杂度为 O(1)
4. 实例4基本操作执行最好1次，最坏N次，时间复杂度一般看最坏，时间复杂度为 O(N)
5. 实例5基本操作执行最好N次，最坏执行了(N*(N+1)/2次，通过推导大O阶方法+时间复杂度一般看最坏，时间复杂度为 O(N^2)
6. 实例6基本操作执行最好1次，最坏O(logN)次，时间复杂度为 O(logN) ps：logN在算法分析中表示是底数为2，对数为N。有些地方会写成lgN。
7. 实例7通过计算分析发现基本操作递归了N次，时间复杂度为O(N)。
8. 实例8通过计算分析发现基本操作递归了2^N次，时间复杂度为O(2^N)。

---

二、空间复杂度

2.1 空间复杂度概念

空间复杂度是衡量算法在执行过程中对物理存储空间的需求量。它是一个函数，表示为算法输入数据的规模n的函数。空间复杂度分析告诉我们，对于给定的输入规模，算法需要多少内存空间才能顺利执行。

需要注意的是，在编程中，单个语句本身不直接“占用”内存，但它可能会导致程序在执行时使用内存。例如，变量声明、对象创建或函数调用这类语句会在内存中分配空间以存储变量、对象或开启新的函数执行上下文。

编译后的程序代码也需要存储空间，但这通常不计入空间复杂度分析，因为空间复杂度关注的是算法执行时的存储需求，尤其是相对于输入数据规模的增长情况。在空间复杂度分析中，我们关注的是算法运行过程中动态分配的内存空间，比如变量、数据结构的存储需求，以及调用栈对于递归函数的需求。

以下是空间复杂度的几个关键点：

1. 固定空间：这部分空间不随问题规模变化，例如变量和常量所占用的空间。
2. 变量空间：这包括动态分配的空间和递归栈空间，它会随着问题规模的变化而变化。
3. 总空间需求：算法总的空间需求是固定空间和变量空间的总和。

---

2.2 计算空间复杂度

计算空间复杂度通常遵循以下步骤：

1. 确定算法的输入规模：输入规模通常指的是输入参数的数量级，例如数组、列表或字符串的长度。

2. 识别数据结构：考虑算法中使用的所有数据结构，如数组、栈、队列、哈希表、对象等，以及它们占用的空间。

3. 计算递归部分的空间：如果算法使用递归，需要考虑递归调用栈占用的空间。每一次递归调用都可能增加额外的空间消耗。

4. 总结空间需求：将所有变量、数据结构和递归空间需求加起来，得到总的空间需求。

5. 应用大O表示法：在大O表示法中，我们只关心变化最快的项。常数项和低阶项通常被忽略。

举例：

// 计算斐波那契递归Fib的空间复杂度？
long long Fib(size_t N){
	if (N < 3)
		return 1;

	return Fib(N - 1) + Fib(N - 2);
}
1
2
3
4
5
6
7

斐波那契递归的时间复杂度是O(2^N)，或许你会认为其空间复杂度也为O(2^N)，但实际上空间复杂度为O(N)。这涉及到函数的调用和销毁。

函数的调用：涉及向调用栈推送一个新的帧，这个帧包含了函数的参数、局部变量和返回地址。当函数被调用时，计算机会记录函数在哪里被调用，并且在函数执行完成后，能够返回到正确的位置继续执行代码。

函数销毁：(函数的返回)，发生在函数完成它的任务后。这时，函数的帧会从调用栈中弹出，控制权回到函数被调用的地方。如果有返回值，它会被传递回父函数。这个过程释放了在调用栈上为函数分配的空间，包括局部变量和函数参数。如果函数是递归调用的，每次返回都会销毁栈上的当前帧，直到回到最初的调用点。

程序首先会一直调用左边的部分，直到调用到Fid(2)，然后函数销毁，返回起点（Fid(2)+Fid(1)），然后调用Fid(1)，依此类推，直到回到Fid(n)。从Fid(n)到Fid(2)，调用深度为n-1，也就是说最多的一次会直接调n-1个函数，所以空间复杂度是O(N)。

---

2.3 计算空间复杂度案例

案例1：

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n){
	assert(a);
	for (size_t end = n; end > 0; --end){
		int exchange = 0;
		for (size_t i = 1; i < end; ++i){
			if (a[i - 1] > a[i]){
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

案例2：

// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n){
	if (n == 0)
		return NULL;

	long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
	fibArray[0] = 0;
	fibArray[1] = 1;
	for (int i = 2; i <= n; ++i){
		fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
	}
	return fibArray;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

案例3：

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N){
	if (N == 0)
		return 1;

	return Fac(N - 1) * N;
}
1
2
3
4
5
6
7

---

答案：

1. 实例1使用了常数个额外空间，所以空间复杂度为 O(1)
2. 实例2动态开辟了N个空间，空间复杂度为 O(N)
3. 实例3递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)

---

三、OJ轮转数组（空间换取时间案例）

这个题有多种思路：

1. 暴力法：对于 k 次，每次将数组旋转 1 个元素。每次旋转的时间复杂度是 O(n)，所以总时间复杂度是 O(kn)。在原数组上直接操作，不使用额外的数组，则空间复杂度为 O(1)
2. 额外数组法：使用额外的数组来放置正确的元素。这种方法的时间复杂度是 O(n)，因为每个元素都移动了一次。创建一个与原数组同样大小的新数组来存放旋转后的结果。因此，空间复杂度为 O(n)，其中 n 是数组的长度。
3. 反转法：这种方法涉及三次反转数组的操作。
   首先反转整个数组。
   然后反转前 k 个元素。
   最后反转剩下的 n-k 个元素。
   每次反转的时间复杂度是 O(n)，但是因为我们只做了固定的三次反转，所以总时间复杂度仍然是 O(n)。在原数组上进行反转，因此空间复杂度为 O(1)。

暴力法是最容易想到的，但其时间复杂度高，其次是额外数组法，最难想到的是反转法。

额外数组法：

//额外数组法
void rotate(int* nums, int numsSize, int k){
    int* new_nums = (int*)malloc(numsSize * sizeof(int));  // 创建新数组
    for (int i = 0; i < numsSize; ++i) {
     new_nums[(i + k) % numsSize] = nums[i];  // 计算新位置并复制
    }
    for (int i = 0; i < numsSize; ++i) {
     nums[i] = new_nums[i];  // 将新数组复制回原数组
    }
    free(new_nums);  // 释放新数组的内存
}
1
2
3
4
5
6
7
8
9
10
11

---

反转法：

// 函数用于反转数组的一部分
void reverse(int* nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

// 函数用于旋转数组
void rotate(int* nums, int numsSize, int k) {
    // k可能大于数组长度，所以用取余运算确定真正的旋转步数
    k = k % numsSize; 
    
    // 如果k为0，说明不需要旋转
    if (k == 0) return;
    
    // 反转整个数组
    reverse(nums, 0, numsSize - 1);
    // 反转前k个元素
    reverse(nums, 0, k - 1);
    // 反转剩余元素
    reverse(nums, k, numsSize - 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

---

如果你喜欢这篇文章，点赞👍+评论+关注⭐️哦！
欢迎大家提出疑问，以及不同的见解。