【图解数据结构】深度解析时间复杂度与空间复杂度的典型问题

02-27 阅读 0评论

$【图解数据结构】深度解析时间复杂度与空间复杂度的典型问题,【图解数据结构】深度解析时间复杂度与空间复杂度的典型问题,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,方法,第2张$

（图片来源网络，侵删）

🌈个人主页：聆风吟

🔥系列专栏：图解数据结构、算法模板

🔖少年有梦不应止于心动，更要付诸行动。

文章目录

一. ⛳️上期回顾
二. ⛳️常见时间复杂度计算举例

1️⃣实例一
2️⃣实例二
3️⃣实例三
4️⃣实例四
5️⃣实例五
6️⃣实例六
7️⃣实例七
8️⃣实例八
三. ⛳️常见空间复杂度计算举例

1️⃣实例一
2️⃣实例二
3️⃣实例三

📝全文总结

一. ⛳️上期回顾

上篇文章我们主要学习了：

算法的定义：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
算法的特性：有穷性、确定性、可行性、输入、输出。
算法的设计要求：正确性、可读性、健壮性、高效率和低存储量需求。
算法的度量方法：事后统计方法、事前分析估算方法。
推导大O阶
时间复杂度
空间复杂度

你对以上的内容是否还能够全部回忆起来呢？如果你对某部分还有欠缺，请跳转该篇文章《深入剖析时间复杂度与空间复杂度的奥秘》进行复习，再配合着下面习题对时间复杂度和空间复杂度进行巩固。

二. ⛳️常见时间复杂度计算举例

1️⃣实例一

// 计算Func1的时间复杂度？
void Func1(int N)
{
	int count = 0;
	for (int k = 0; k  
解析：实例1基本操作执行了2N+10次，根据大O阶的推导方法很容易得出：Func1的时间复杂度为O(N)。
（图片来源网络，侵删）

 
2️⃣实例二 
// 计算Func2的时间复杂度？
void Func2(int N, int M)
{
	int count = 0;
	for (int k = 0; k  
解析：实例二基本操作执行了M+N次，根据大O阶的推导方法得出：

如果题目没有表明 M 和 N 的大小，Func2的时间复杂度为O(M + N)；
如果题目明确表明 M 远大于 N ，则 N 的变化对时间复杂度的影响不大，Func2的时间复杂度为O(M)；
如果题目明确表明 N 远大于 M ，则 M 的变化对时间复杂度的影响不大，Func2的时间复杂度为O(N)。

如果题目明确表明 M 和 N 一样大，则O(M + N)等价于O(2M)或O(2N)，Func2的时间复杂度为O(M) 或 O(N) ；

3️⃣实例三

// 计算Func3的时间复杂度？
void Func3(int N)
{
	int count = 0;
	for (int k = 0; k  
解析：实例3基本操作执行了100次，根据大O阶的推导方法很容易得出：Func3的时间复杂度为O(1)。 

4️⃣实例四 
// 计算strchr的时间复杂度？
const char * strchr ( const char * str, int character );
 
解析：首先我们先来介绍一下库函数strchr作用：在str指向的字符数组中查找是否包含字符characte。因此实例4的基本操作执行最好1次，最坏N次。根据时间复杂度一般看最坏，strchr的时间复杂度为O(N)。 

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  a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}
 
解析：本题是冒泡排序函数，冒泡排序的思想是：假设数组中有 n 个元素，第一趟执行将会执行 n-1 次交换，将一个元素排好序。第二趟将会执行 n-2 次交换，将将一个元素排好序…依次类推。排好所有元素需要执行 n-1 次，每趟交换的次数分别为(n - 1)，(n-2)，(n-3)，… ，(2)，(1)。由此可知，实例5基本操作执行最好n-1次（即数组已经排好序，只需要执行一趟排序判断数组是否已经有序），最坏执行了( n*(n-1) )/2次（即将所有趟交换的次数相加，可以直接使用等差数列求和），通过推导大O阶方法+时间复杂度一般看最坏，BubbleSort的时间复杂度为O(N^2)。 

6️⃣实例六 
// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	// [begin, end]：begin和end是左闭右闭区间，因此有=号
	while (begin 
		int mid = begin + ((end - begin) > 1);
		if (a[mid]  x)
			end = mid - 1;
		else
			return mid;
	}
	return -1;
}
 
解析：本题是二分查找函数，每次查找将会将范围缩放一半。因此实例6基本操作执行最好1次，最坏O(logN)次。根据时间复杂度一般看最坏，BinarySearch时间复杂度为 O(logN) 。
 

7️⃣实例七 
// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1) * N;
}
 
解析：本题是一个简单的递归调用， 实例7通过计算分析发现基本操作递归了N次，时间复杂度为O(N)。

 
8️⃣实例八 
// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
	if (N  
解析：本题是一个双递归。实例8通过计算分析发现基本操作递归了2n，Fib的时间复杂度为O(2^n)。
 

三. ⛳️常见空间复杂度计算举例 
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  a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}
 
解析： 实例1使用了常数个额外空间，分别是[ end，exchange，i ]。根据大O阶的推导方法很容易得出，BubbleSort空间复杂度为 O(1) 

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 
		fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
	}
	return fibArray;
}

	if (N == 0)
		return 1;
	return Fac(N - 1) * N;
}