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

🌈个人主页：聆风吟
🔥系列专栏：图解数据结构、算法模板
🔖少年有梦不应止于心动，更要付诸行动。

文章目录

• 一. ⛳️上期回顾
• 二. ⛳️常见时间复杂度计算举例
• • 1️⃣实例一
  • 2️⃣实例二
  • 3️⃣实例三
  • 4️⃣实例四
  • 5️⃣实例五
  • 6️⃣实例六
  • 7️⃣实例七
  • 8️⃣实例八
• 三. ⛳️常见空间复杂度计算举例
• • 1️⃣实例一
  • 2️⃣实例二
  • 3️⃣实例三
• 📝全文总结

一. ⛳️上期回顾

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

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

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

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

1️⃣实例一

// 计算Func1的时间复杂度？
void Func1(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基本操作执行了2N+10次，根据大O阶的推导方法很容易得出：Func1的时间复杂度为O(N)。

2️⃣实例二

// 计算Func2的时间复杂度？
void Func2(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);
}

解析：实例二基本操作执行了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 < 100; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

解析：实例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 < end; ++i)
		{
			if (a[i - 1] > 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 <= 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;
}

解析：本题是二分查找函数，每次查找将会将范围缩放一半。因此实例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 < 3)
		return 1;

	return Fib(N - 1) + Fib(N - 2);
}

解析：本题是一个双递归。实例8通过计算分析发现基本操作递归了2ⁿ，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 < end; ++i)
		{
			if (a[i - 1] > 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 <= n; ++i)
	{
		fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
	}
	return fibArray;
}

解析：实例2动态开辟了N+1个空间，根据大O阶的推导方法很容易得出，Fibonacci空间复杂度为 O(N)。

3️⃣实例三

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

	return Fac(N - 1) * N;
}

解析：实例3递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)。

📝全文总结

     本文通过大量实例讲解常见时间复杂和空间复杂度计算，希望通过这些例子的讲解能够帮助你在以后的学习中能够更加灵活、精确的计算出一个程序的复杂度，方便我们更快的寻找解决一个问题的最优的算法。

     今天的干货分享到这里就结束啦！如果觉得文章还可以的话，希望能给个三连支持一下，聆风吟的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的最大动力！