到了期待的数据结构板块了，数据结构、算法、时间复杂度、空间复杂度概念，如何计算时间复杂度和空间复杂度呢？一起来看看吧。
数据结构
是计算机存储、组织数据的方式，是相互之间存在一种或多种特定关系的数据元素的集合。
算法
是定义良好的计算过程，取一个或一组的值为输入，并产生出一个或一组值作为输出。可以认为是一系列的计算步骤，用来将输入数据转化成输出结果。
时间复杂度
算法效率分为两种：时间效率(时间复杂度)和空间效率(空间复杂度) ，时间复杂度衡量算法运行速度，空间复杂度衡量算法需要的额外空间。现在计算机存储容量大，已经不再需要关注空间复杂度。时间复杂度算的不是时间，是操作执行的次数。
大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. }
时间复杂度结束了，空间复杂度就要开始了~
