【数据结构】初探时间与空间复杂度：算法评估与优化的基础

🚩纸上得来终觉浅， 绝知此事要躬行。
🌟主页：June-Frost
🚀专栏：数据结构

🔥该文章主要了解算法的时间复杂度与空间复杂度等相关知识。

📗时间复杂度和空间复杂度是计算机科学中用来评估算法效率的两个重要概念。它们分别描述了算法在执行时间和额外内存使用方面的需求，帮助我们了解算法在处理输入数据时所需的资源。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

🌏 时间复杂度

 在计算机科学中，算法的时间复杂度是一个函数，用于度量算法执行时间的指标。因为一个算法所花费的时间与其中语句的执行次数成正比例，所以可以认为在算法中的基本操作的执行次数，为算法的时间复杂度。
 计算时间复杂度时,其实并不一定要计算精确的执行次数,只需要大概执行次数即可。

✨表示方式为大O的渐进表示法，记作T(n) = O(f(n))，其中T(n)表示算法执行时间，f(n)表示问题规模n的函数。具体来说，当n趋近于无穷大时，算法执行时间的增长趋势与f(n)的增长趋势相同的最高阶项即为该算法的时间复杂度。
✨推导方式：

• 用常数1取代运行时间中的所有加法常数。
• 运行次数函数中，只保留最高阶项。
• 只关注数量级，而忽略常数因子，即去掉系数。

🔭 一些例子

①

void exampleAlgorithm(int N)
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			printf("This is O(n^2) operation.\n");
		}
	}

	for (int k = 0; k < 2 * N; k++)
	{
		printf("This is O(n) operation.\n");
	}

	for (int M = 5; M > 0; M--)
	{
		printf("This is O(1) operation.\n");
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

 这个例子的函数表达式为 F(N) = N² +2*N + 5，随着N的不断增加，N² 对最终结果具有决定性的作用，所以N²就是它的量级，运用大O的渐进表示法就可以表示为O(N²) 。

②

void exampleAlgorithm(int N)
{

	for (int k = 0; k < 2 * N; k++)
	{
		printf("This is O(n) operation.\n");
	}

	for (int M = 5; M > 0; M--)
	{
		printf("This is O(1) operation.\n");
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

 如果没有了嵌套，这个函数的表达式就变成了 F(N) = 2*N + 5，这样随着N的增加，有决定性效果的就是2 * N，但是为了简化复杂度的表示，并突出算法随输入数据规模增长的趋势，又因为系数对于这种增长趋势的影响较小，所以一般需要去除系数，时间复杂度为O(N) 。

③

void exampleAlgorithm()
{

	for (int M = 1000; M > 0; M--)
	{
		printf("This is O(1) operation.\n");
	}

}
1
2
3
4
5
6
7
8
9

 如果只有常数阶，那么就可以直接表示为O(1) 。

⚠注意：

📙通过上面这些例子，我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数，但是有些算法的时间复杂度存在最好、平均和最坏情况，在实际中一般关注的是算法的最坏运行情况。

④冒泡排序：

void bubble_sort(int* arr, int sz)
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int flag = 1; //标记
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				flag = 0;
				int temp = 0;
				temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
			}
		}
		if (flag == 1)//如果等于1表示数组数据已经有序
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

 对于冒泡排序，最好的情况就是本身有序，只需遍历比较一遍数组即可，这时的时间复杂度为O(N)，最坏的情况就是逆序，排好第一个数据需要比较N-1次，排好第二个数据需要比较N-2次，…，排好倒数第二个数据需要比较1次，最后一个数据不需要比较，将次数相加就是 [N*(N-1)] / 2，量级为N²，时间复杂度就是O(N²)，最终的时间复杂度需要取最坏情况，即O(N²)。

⑤二分查找

int BinarySearch(int* arr, int sz, int k)
{
	int left = 0;
	int right = sz - 1;
	while (left <= right)
	{
		int mid = (right + left) / 2;
		if (arr[mid] < k)
		{
			left = mid + 1;//调整范围
		}
		else if (arr[mid] > k)
		{
			right = mid - 1;//调整范围
		}
		else
		{
			return mid;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

📘最好的情况是第一次查找就找到了，为O(1)。
📙最坏的情况为数据在边缘或者数组中没有要查找的数据:

 一般将 log₂N 简写为logN ，所以时间复杂度为 O(logN)。

⑥ 阶乘

long long Factorial(size_t N)
{
	if (N == 0)
		return 1;
	return Factorial(N - 1) * N;
}
1
2
3
4
5
6

 调用函数需要创建栈帧，传入参数后，会调用Factorial(N) ,再调用Factorial(N-1)，不断调用，直到调用到Factorial(0)，共调用了N+1次，每次调用的时间复杂度为O(1)，所以最终的时间复杂度为O(N) 。

⑦ 斐波那契数

long long Fibonacci(size_t N)
{
	if (N <= 2)
		return 1;

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

 将 2⁰ 一直加到 2^(n-2) ,算法的量级为2ⁿ，虽然实际上右边的分支会缺少一部分，但是不会影响到这个量级。

---

🌎 空间复杂度

 空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度算的是变量的个数，计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

⚠注意：

📙函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

① 冒泡排序

 冒泡排序属于原地排序，在排序过程中并没有使用额外的空间来帮助排序，那些用来循环的变量，可以看作常数阶，所以冒泡排序的空间复杂度为O(1) 。

②阶乘

long long Factorial(size_t N)
{
	if (N == 0)
		return 1;
	return Factorial(N - 1) * N;
}
1
2
3
4
5
6

 阶乘可以看作额外开辟了N个栈帧，每个栈帧空间内部没有额外创建空间，即每个栈帧空间为O(1)，最终的空间复杂度为O(N) 。

③斐波那契数

long long Fibonacci(size_t N)
{
	if (N <= 2)
		return 1;

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

 栈帧空间是可以复用的,所以通常用计算算法所占用的内存空间的最大值来评估算法的空间复杂度，只需要知道在递归中会最大开辟多少栈帧空间就可以进行计算，这个算法最多开辟栈帧数量的量级为N，每个栈帧空间为O(1)，所以最终的空间复杂度为O(N)。

---

❤️ 结语

 文章到这里就结束了，如果对你有帮助，你的点赞将会是我的最大动力，如果大家有什么问题或者不同的见解，欢迎大家的留言~