【数据结构】励志大厂版·初阶（复习+刷题）：复杂度

前引：从此篇文章开始，小编带给大家的是数据结构初阶的刷题讲解 ，此类文章将简略的包含相关知识，详细的思路拆分讲解，分析每一题的难点、易错点，看见题目如何分析，以上就是小编预备的内容，对于数据结构巩固知识的伙伴们来说，可以一试，告别冗杂的知识点，如果伙伴们发现下面哪有有问题，欢迎在评论区指出哦！小编一定会进行修改的！正文开始~

目录

知识点速览

计算时间复杂度

第一题

第二题

第三题

第四题

第五题

第六题

第七题

第八题

计算空间复杂度

第一题

第二题

第三题

复杂度的实际应用

第一题

第二题

知识点速览

复杂度可以分为时间复杂度、空间复杂度，它们都是度量算法优劣的算级说明，通常是估算，采用大O渐进表示法，例如如O（N）

复杂度计算：

                     时间复杂度是计算执行次数（估算）；空间复杂度看（变量个数+额外开辟空间数）

复杂度种类：复杂度一般有最坏、最好、平均复杂度之分，我们一般取最坏结果

计算步骤：（1）先算出准确执行次数【时间复杂度】 /（变量个数（函数内）+额外空间数量）                        【空间复杂度】（2）再根据规则修改

时间复杂度、空间复杂度计算规则：

                                                     （1）用常数 1 取代运行时间中所有的加法常数（常数化1）

                                                     （2）只要高阶项，不用低阶项（取大舍小）

                                                     （3）不要高阶项系数（去系数）

计算时间复杂度

第一题
  1. void Func1(int N)
  2. {
  3. 	int count = 0;
  4. 	for (int i = 0; i < N; i++)
  5. 	{
  6. 		for (int j = 0; j < N; j++)
  7. 		{
  8. 			++count;
  9. 		}
  10. 	}
  11. 	for (int k = 0; k < 2 * N; k++)
  12. 	{
  13. 		++count;
  14. 	}
  15. 	int M = 0;
  16. 	while (M--)
  17. 	{
  18. 		++count;
  19. 	}
  20. 	printf("%d\n", count);
  21. }

按照上面的计算步骤：先算总的执行次数，可以算出准确次数为：N*N + 2N，再根据计算规则（取大舍小），最终得到它的时间复杂度用大O渐进表示法得到 O（N^2）

第二题
  1. void Func2(int N)
  2. {
  3. 	int count = 0;
  4.  
  5. 	for (int k = 0; k < 2 * N; k++)
  6. 	{
  7. 		++count;
  8. 	}
  9.  
  10. 	int M = 0;
  11. 	while (M--)
  12. 	{
  13. 		++count;
  14. 	}
  15.  
  16. 	printf("%d\n", count);
  17. }

根据计算步骤，得到总的执行次数为：2N，再根据计算规则（去系数），得到最后它的时间复杂度用大O渐进表示法表示为O（N）

第三题
  1. void Func3(int N,int M)
  2. {
  3. 	int count = 0;
  4.  
  5. 	for (int k = 0; k < N; ++k)
  6. 	{
  7. 		++count;
  8. 	}
  9.  
  10. 	for (int k = 0; k < M; ++k)
  11. 	{
  12. 		++count;
  13. 	}
  14. }

按照计算步骤，我们先算出准确的执行次数为N+M，这里出现一个问题，如果按照取大舍小，我们是无法判断的，因为M、N都是未知数

分析：如果M较大，那就舍弃N；如果M较小，那就舍弃M；如果M等于N，那就是2M或者2N

对于这种情况，我们是都不能舍弃的，只能都保存，因此最后的时间复杂度是O（M+N）

第四题
  1. void Func4(int N)
  2. {
  3. 	int count = 0;
  4.  
  5. 	for (int k = 0; k < 100; k++)
  6. 	{
  7. 		++count;
  8. 	}
  9.  
  10. 	printf("%d\n", count);
  11. }

根据计算步骤，我们先算出准确的执行次数为100次，再根据计算规则常数化1，得到最后的时间复杂度用大O渐进表示法表示为O（1）

第五题
  1. const char* strchr(const char* str, char character)
  2. {
  3. 	while (*str != '\0')
  4. 	{
  5. 		if (*str == character)
  6. 		{
  7. 			return str;
  8. 		}
  9. 		++str;
  10. 	}
  11. 	return NULL;
  12. }

首先根据计算步骤，我们需要先计算准确执行次数，这题同样有一个问题，就是不知道这个字符串的长度，所以我们需要分类：

最好情况：直接出循环，1次执行次数（总执行次数）

最坏情况：假设字符串长度N，它找到底才找到，也就是N次（总执行次数）

按照计算规则，选择最坏情况，时间复杂度表示为O（N）

第六题
  1. void BubbleSort(int* a, int n)
  2. {
  3. 	assert(a);
  4.  
  5. 	for (size_t end = n; end > 0; --end)
  6. 	{
  7. 		int exchange = 0;
  8.  
  9. 		for (size_t i = 1; i < end; ++i)
  10. 		{
  11. 			if (a[i - 1] > a[i])
  12. 			{
  13. 				Swap[&a[i - 1], &a[i]];
  14. 				exchange = 1;
  15. 			}
  16. 		}
  17. 		if (exchange == 0)
  18. 		{
  19. 			break;
  20. 		}
  21. 	}
  22. 	return;
  23. }

按照计算步骤，先算总的执行次数，通过代码我们看到，还是需要分类考虑

最好情况：进入外面的 for 循环一次，里面的循环需要走 end 次，总的执行次数就是 end+1 次

最坏情况：那就只能把循环走完了！总的执行次数也就是 end^2 次

再根据计算规则，取最坏情况，得到最后的时间复杂度为O（N^2）

易错点：首先小编也经历过这个雷区！经常以为双层for循环就是N^2了，一层for循环就是N次，但是需要避雷这个，具体情况需要具体分析，我们继续向下看！

第七题
  1. int BinarySearch(int* a, int n, int x)
  2. {
  3. 	assert(a);
  4.  
  5. 	int begin = 0;
  6. 	int end = n;
  7. 	while (begin < end)
  8. 	{
  9. 		int mid = begin + ((end - begin) >> 1);
  10. 		if (a[mid] < x)
  11. 		{
  12. 			begin = mid + 1;
  13. 		}
  14. 		else if (a[mid] > x)
  15. 		{
  16. 			end = mid;
  17. 		}
  18. 		else
  19. 			return mid;
  20. 	}
  21. 	return -1;
  22. }

首先我们先来计算它的总次数，根据这个代码情况，属于二分查找，还是需要分类

最好情况：那肯定就一次找到，总执行次数就是1次

最坏情况：对一组数据一直二分下去，要找的元素在数组最后一个被检查的位置

                 假设数组长度为N，每经过一次二分，剩余元素为N/2，经过 k 次后，剩余元素为N/                       （2^k）

                 最坏情况也就是当剩余元素为1时，即N/（2^k）=1

                 解得k=log N（注意log N在复杂度里面是等于㏒以2为底N的对数的）

按照计算规则，取最坏情况，得到最后的时间复杂度为 log N

第八题
  1. long long Factorial(size_t N)
  2. {
  3. 	return N < 2 ? N : Factorial(N - 1) * N;
  4. }

首先根据计算步骤，计算总的执行次数，我们发现这是一个三目操作符，我先来简答解释一下它的运算思路：

如果N<2，为真就得到结果N，如果为假就得到结果 Factorial（N-1）*N

因此我们发现这是一个计算前 n 项阶层的递归函数，下面我们来分析

最好情况：直接执行一次，即计算 1 的前 n 阶层

最坏情况：假设有N个数字，那么它的阶层就是N*（N-1）*（N-2）*（N-3）......，执行了N次

根据计算规则，保留最坏情况，得到最后的时间复杂度为O（N）

计算空间复杂度

第一题
  1. void BubbleSort(int* a, int n)
  2. {
  3. 	assert(a);
  4.  
  5. 	for (size_t end = n; end > 0; --end)
  6. 	{
  7. 		int exchange = 0;
  8.  
  9. 		for (size_t i = 1; i < end; ++i)
  10. 		{
  11. 			if (a[i - 1] > a[i])
  12. 			{
  13. 				Swap[&a[i - 1], &a[i]];
  14. 				exchange = 1;
  15. 			}
  16. 		}
  17. 		if (exchange == 0)
  18. 		{
  19. 			break;
  20. 		}
  21. 	}
  22. 	return;
  23. }

首先我们按照计算步骤，先算（变量个数+额外空间数），上面总共有3个变量，没有开辟额外的空间，因此准确计算得到数量为3

再按照复杂度的计算规则（常数化1），得到最后的空间复杂度为O（1）

第二题
  1. long long* Fibonacci(size_t n)
  2. {
  3. 	if (n == 0)
  4. 	{
  5. 		return NULL;
  6. 	}
  7.  
  8. 	long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
  9. }

首先我们按照计算步骤，先算（变量数+额外空间数），这个函数没有变量，但是它额外开辟了（n+1）的空间个数，因此总的数量就是 0+（n+1）= N+1

根据计算规则（舍大取小），得到最后的空间复杂度为O（N）

第三题
  1. long long Factorial(size_t N)
  2. {
  3. 	return N < 2 ? N : Factorial(N - 1) * N;
  4. }

这是一个计算 N 的阶层积的函数，比如N*（N-1）*（N-2）*（N-3）*........

每次递归都需要开辟函数栈帧空间，这里是从N-1开始调用递归函数的，因此是N-1个额外空间，没有其它变量，所以得到总的数量是0+（N-1）= N-1

根据计算规则（舍大取小），得到最后的空间复杂度为O（N）

复杂度的实际应用

话不多说我们通过两道例题来看看复杂度的实际应用

第一题

上面我们看到它的要求是时间复杂度不能超过O（N），这就是复杂度在实际的应用，题目可能会规定一定的时间复杂度、空间复杂度，下面我们开始解决这个问题！

（1）最简单的方法就是：计算 0~N 的数字之和，再减去题目中已有的数字，这样我们就找到了             那个缺失的数字，大家不能理解的话欢迎在评论区留言啊！下面我们来实现代码：

  1. int missingNumber(int* nums, int numsSize)
  2. {
  3. 	int sum = 0;
  4. 	//求和
  5. 	for (int i = 0; i <= numsSize; i++)
  6. 	{
  7. 		sum += i;
  8. 	}
  9. 	//求差
  10. 	for (int i = 0; i < numsSize; i++)
  11. 	{
  12. 		sum -= nums[i];
  13. 	}
  14.  
  15. 	return sum;
  16. }

（2）算法解法：我们先来了解一个运算符^ ,它比较的是二进制位，相同为0，相异为1，例如：

 3的二进制是：00000000 00000000 00000000 00000011

 1的二进制是：00000000 00000000 00000000 00000001

  1^2^3的二进制是：00000000 00000000 00000000 00000011

将1^2^3的二进制分别与3、2的二进制去异或，这样我们就得到了中间的2的二进制

算法实现：我们把0~N的数字去分别异或，然后再将异或得到的结果与题目中数组的每个元素异或，那样就找到了少的那个数字（一般用0去开始异或，因为0与任何数异或都为那个数字）

  1. int missingNumber(int* nums, int numsSize)
  2. {
  3. 	//0与任何数异或都为那个数，不会产生影响
  4. 	int n = 0;
  5. 	//分别异或0~N的数字
  6. 	for (int i = 0; i <= numsSize; i++)
  7. 	{
  8. 		n ^= i;
  9. 	}
  10. 	//再与0~N-1的数字异或，得到差值
  11. 	for (int i = 0; i < numsSize; i++)
  12. 	{
  13. 		n ^= nums[i];
  14. 	}
  15.  
  16. 	return n;
  17. }
第二题

首先我们我们来说一下几种解法：

（1）暴力解法：一次旋转一位数字，通过移动其余元素达到目标，但是效率上无法通过 

（2）间接解法：将后k个元素拷贝到另外一个数组，再将前n-k个元素拷贝过来，再进行整体拷                                 贝，但是这样就不是原地了，也无法达到更高的进阶要求

（3）算法解法：我们先将数组的前n-k个元素旋转交换位置，再将后k个元素旋转位置，再整体旋                             转交换位置，拿时间换取空间。例如下面这样：

  1. void Exchange(int* p1, int* p2)
  2. {
  3. 	int num = *p1;
  4. 	*p1 = *p2;
  5. 	*p2 = num;
  6. }
  7. int* missNumber(int* nums, int numsSize)
  8. {
  9. 	//旋转前numsSize-k个元素
  10. 	int i = 0;
  11. 	int j = numsSize - k - 1;
  12. 	while (i < j)
  13. 	{
  14. 		Exchange(&nums[i], &nums[j]);
  15. 		i++;
  16. 		j--;
  17. 	}
  18. 	//旋转后k个元素
  19. 	i = numsSize - k - 1;
  20. 	j = numsSize - 1;
  21. 	while (i < j)
  22. 	{
  23. 		Exchange(&nums[i], &nums[j]);
  24. 		i++;
  25. 		j--;
  26. 	}
  27. 	//旋转整体
  28. 	i = 0;
  29. 	j = numsSize - 1;
  30. 	while (i < j)
  31. 	{
  32. 		Exchange(&nums[i], &nums[j]);
  33. 		i++;
  34. 		j--;
  35. 	}
  36. 	return nums;
  37. }

注：本文转载自blog.csdn.net的雾非雾の迷惘的文章"https://blog.csdn.net/Dovis5884/article/details/147079334"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！