【数据结构】时间复杂度-C语言版（一）-阿里云开发者社区

到了期待的数据结构板块了，数据结构、算法、时间复杂度、空间复杂度概念，如何计算时间复杂度和空间复杂度呢？一起来看看吧。

数据结构

是计算机存储、组织数据的方式，是相互之间存在一种或多种特定关系的数据元素的集合。

算法

是定义良好的计算过程，取一个或一组的值为输入，并产生出一个或一组值作为输出。可以认为是一系列的计算步骤，用来将输入数据转化成输出结果。

时间复杂度

算法效率分为两种：时间效率(时间复杂度)和空间效率(空间复杂度) ，时间复杂度衡量算法运行速度，空间复杂度衡量算法需要的额外空间。现在计算机存储容量大，已经不再需要关注空间复杂度。时间复杂度算的不是时间，是操作执行的次数。

大O的渐进表示法

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

2.在修改后的运行次数函数中，只保留最高阶项

3.如果最高阶项存在且不为1，则去除这个项目相乘的常数，得到的结果就是大O阶。

时间复杂度的计算

举例1：

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include<stdio.h>
3. void Func3(int N, int M)
4. {
5.  int count = 0;
6. 
7.  int k = 0;
8.  for (k = 0; k < M; k++)
9.  {
10.     ++count;
11.   }
12. 
13.   for (k = 0; k < N; k++)
14.   {
15.     count++;
16.   }
17. 
18.   printf("%d\n", count);
19. }

时间复杂度为O(M+N)，不能确定谁对结果的影响大，所以M和N都要留下来。如果已经明确N>>M，那么时间复杂度为O(N)。

举例2：

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include<stdio.h>
3. void Func4(int N)
4. {
5.  int count = 0;
6.  for (int k = 0; k < 100; k++)
7.  {
8.    ++count;
9.  }
10. 
11.   printf("%d\n", count);
12. }

for循环了100次，即常数次，时间复杂度为O(1)。

举例3：

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include<stdio.h>
3. const char* strchr(const char* str, int character)
4. {
5.  while (*str != '\0')
6.  {
7.    if (*str == character)
8.    {
9.      return str;
10.     }
11.     str++;
12.   }
13.   return str;
14. }

假设字符串的长度是N，那么最好的情况是字符串第一个字符就是要查找的字符，时间复杂度为O(1)，最坏的情况是字符串最后一个字符是要查找的字符，时间复杂度为O(N)。虽然平均情况是查找N/2次，但是默认时间复杂度是看最坏的，即O(N)。

举例4：

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include<stdio.h>
3. #include<assert.h>
4. void Swap(int *p1, int *p2) 
5. {
6.  int temp = *p1;
7.  *p1 = *p2;
8.  *p2 = temp;
9. }
10. 
11. void BubbleSort(int* a,int n)
12. {
13.   assert(a);
14.   int end = 0;
15.   for (end = n; end > 0; --end)
16.   {
17.     int exchange = 0;
18.     for (int i = 1; i < end; i++)
19.     {
20.       if (a[i - 1] > a[i])
21.       {
22.         Swap(&a[i - 1], &a[i]);
23.         exchange = 1;
24.       }
25.     }
26. 
27.     if (exchange == 0)
28.     {
29.       break;
30.     }
31.   }
32. }

冒泡算法按照最坏的情况分析，即假如数组按照从大到小的顺序排列，那么第一个元素找到最终位置需要比较N-1次，第二个元素找到最终位置需要N-2次，·······，最后一个元素找到最终位置需要1次，平均计算次数为(N-1)+(N-2)+······+1=N*(N-1)/2。按照大O渐进表示法第2条，时间复杂度为O(N^2)。

递归算法时间复杂度的计算

递归算法时间复杂度=递归次数*每次递归函数中次数

举例1：

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

计算递归函数调用的次数：

每次调用Factorial函数，只执行return这一句，因此每次递归函数中次数=1，还需计算递归次数:

第一次递归，需计算F(N)

第二次递归，需计算F(N-1)

……

最后一次递归，需计算F(1)

一共计算了N次，因此时间复杂度=N*1=O(N)。如果将递归函数体的代码改成for循环:

1. for(i = 0; i<N; i++)
2. {
3. }

时间复杂度=O(N*N)=O(N^2)。

举例2：

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

递归次数：

右边的计算会提前结束，有一部分会缺失，因此在满的情况下，计算次数=2^0+2^1+2^2+……+2^(N-2)+2^(N-1)=2^N-1。那么缺的情况下计算次数=2^N-1-常数(右边缺的)，时间复杂度为O(2^N)。

时间复杂度应用

1.力扣网-消失的数字

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

分析：3种思路：

(1)冒泡排序或快排对数组先排序，找出第一个元素值不等于该元素下标的元素。(O(N^2)或O(NlogN))

思路(1)代码:

1. //冒泡排序
2. #define  _CRT_SECURE_NO_WARNINGS  1
3. #include<stdio.h>
4. void BubbleSort(int* nums, int numSize)
5. {
6.  int i = 0;
7.  for (i = 0; i < numSize-1; i++)
8.  {
9.    int j = 0;
10.     for (j = 0; j < numSize-i-1; j++)
11.     {
12.       if (nums[j] > nums[j+1])
13.       {
14.         int temp = nums[j];
15.         nums[j] = nums[j+1];
16.         nums[j + 1] = temp;
17.       }
18.     }
19.   }
20. }
21. int missingNumber(int* nums, int numSize)
22. {
23.   BubbleSort(nums, numSize);
24. 
25.   int i = 0;
26.   for (i = 0; i < numSize; i++)
27.   {
28.     if (nums[i] != i)
29.     {
30.       return i;
31.     }
32.   }
33.   return -1;
34. }
35. int main()
36. {
37.   int arr[5] = { 5,2,4,1,0 };
38.   int ret = missingNumber(arr, 5);
39.   printf("%d\n", ret);//3
40.   return 0;
41. }

1. //快排
2. #define  _CRT_SECURE_NO_WARNINGS  1
3. #include<stdio.h>
4. int cmp(const void* e1, const void* e2)
5. {
6.  return *(int*)e1 - *(int*)e2;
7. }
8. int missingNumber(int* nums, int numSize)
9. {
10.   qsort(nums, numSize, sizeof(nums[0]), cmp);
11. 
12.   int i = 0;
13.   for (i = 0; i < numSize; i++)
14.   {
15.     if (nums[i] != i)
16.     {
17.       return i;
18.     }
19.   }
20.     return -1;
21. }
22. 
23. int main()
24. {
25.   int arr[5] = { 5,2,4,1,0 };
26.   int ret = missingNumber(arr, 5);
27.   printf("%d\n", ret);//3
28.   return 0;
29. }

(2)计算0~n的和S1，再计算数组所有元素的和S2，S1-S2。(O(N))

思路(2)代码

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include<stdio.h>
3. int missingNumber(int* nums, int numSize)
4. {
5.  int i = 0;
6.  int sumOfNums = 0;
7.  int sumOfIndex = 0;
8.  for (i = 0; i < numSize; i++)
9.  {
10.     sumOfNums += nums[i];
11.   }
12.   for (i = 0; i < numSize + 1; i++)
13.   {
14.     sumOfIndex += i;
15.   }
16.   return sumOfIndex - sumOfNums;
17. }
18. 
19. int main()
20. {
21.   int arr[5] = { 5,2,4,1,0 };
22.   int ret = missingNumber(arr, 5);
23.   printf("%d\n", ret);//3
24.   return 0;
25. }

(3)用0和数组中每一个元素顺序异或：0^a1^a2^……^an，之后再和每个下标顺序异或，结果就是缺失的数字。(O(N))

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include<stdio.h>
3. int missingNumber(int *nums,int numSize)
4. {
5.  int i = 0;
6.  int x = 0;
7.  for (i = 0; i < numSize; i++)
8.  {
9.    x ^= nums[i];
10.   }
11. 
12.   for (i = 0; i < numSize + 1; i++)
13.   {
14.     x ^= i;
15.   }
16.   return x;
17. }
18. 
19. int main()
20. {
21.   int arr[5] = { 5,2,4,1,0 };
22.   int ret = missingNumber(arr, 5);
23.   printf("%d\n", ret);//3
24.   return 0;
25. }

2.力扣网-只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

分析：

线性时间复杂度即时间复杂度为O(N)，不使用额外空间即空间复杂度为O(1)。根据题目，如果用0异或数组中的所有元素，那么出现两次的元素就被异或为0，剩下的那个元素就是只出现一次的数字。

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include<stdio.h>
3. int singleNumber(int* nums, int numsSize) {
4. int x = 0;
5. for (int i = 0; i < numsSize; i++)
6.     {
7.         x ^= nums[i];
8.     }
9. return x;
10. }
11. 
12. int main()
13. {
14.   int arr[5] = { 3,1,1,5,3 };
15. int len = sizeof(arr) / sizeof(arr[0]);
16. int ret = singleNumber(arr, len);
17. printf("%d", ret);//5
18.   return 0;
19. }

3.力扣网-数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

分析：

（1）如何将原数组分成两组--将0和数组所有元素异或的结果，将该结果从倒数第一位开始查找第j位为1为a组，第j位为0的为b组，如1(001),1(001),5(101)的倒数第二位都为0，如2(010)，2(010)，3(011)的倒数第二位都为1，基于此可将数组分为两组。

（2）结果x和y一定会分别进入a、b组，其他出现两次的数，要么进第一组，要么进第二组

（3）第一组和第二组数据就变成其他数出现2次，只有一个数出现1次

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include<stdio.h>
3. #include<stdlib.h>
4. 
5. 
6. int* singleNumbers(int* nums, int numsSize, int* returnSize)
7. {
8.     //将所有元素进行异或
9.     int ret = 0;
10.     int i = 0;
11.     for(i = 0;i<numsSize;i++)
12.     {
13.         ret ^= nums[i];
14.     }
15.     
16.     //找出第一个为1的j位
17.     int j = 0;
18.     for(j = 0;j<32;j++)
19.     {
20.         if((ret >> j) & 1)
21.         {
22.             break;
23.         }
24.     }
25. 
26.     //按照第j位为0或1将数组分在两组，并对两组元素分别异或
27.     int x = 0,y = 0,k = 0;
28.     for(k = 0;k<numsSize;k++)
29.     {
30.         if((nums[k] >> j) & 1)
31.         {
32.             x ^= nums[k];
33.         }
34.         else
35.         {
36.             y ^= nums[k];
37.         }
38.     }
39. 
40.     int *arr = (int *)malloc(sizeof(int)*2);
41.     *returnSize = 2;
42.     arr[0] = x;
43.     arr[1] = y;
44.     return arr;
45. }
46. 
47. int main()
48. {
49.     int array[6] = { 1,3,5,2,1,2 };
50.     int* p = array;
51.     p = singleNumbers(array, 6, p);
52.     for (int i = 0; i < 2; i++)
53.     {
54.         printf("%d ", *(p+i));
55.     }
56.     return 0;
57. }

4-力扣网-数组中数字出现的次数

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

分析：需要先统计32位中，第1位有多少1，第2位有多少1，第31位有多少1，让每一位的结果%3，找出余数为1的那些位，这些位的组合就是出现一次的数

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include<stdio.h>
3. #include<math.h>
4. 
5. int singleNumber(int* nums, int numsSize) {
6. 
7.     int i = 0, j = 0, bit = 0, ret = 0;
8.     for(j = 0; j < 32; j++)
9.     {
10.         bit = 0;
11.         for(i = 0; i < numsSize; i++)
12.         {
13.             bit += (nums[i]>>j)&1;  
14.         } 
15.         ret += ((bit % 3) <<j);
16.     }
17. 
18.     return ret;
19. }
20. 
21. int main()
22. {
23.     int arr[4] = { 3,6,6,6 };
24.     int len = sizeof(arr)/sizeof(arr[0]);
25.     int ret = singleNumber(arr,len);
26.     printf("%d", ret);
27.     return 0;
28. }

时间复杂度结束了，空间复杂度就要开始了~

【数据结构】时间复杂度-C语言版（一）

数据结构

算法

时间复杂度

大O的渐进表示法

时间复杂度的计算

递归算法时间复杂度的计算

时间复杂度应用

热门文章

最新文章

相关课程

相关电子书