《数据结构》时间复杂度和空间复杂度（一）超硬核八千字

——————————————————时间复杂度和空间复杂度—————————————————————

1.时间复杂度和空间复杂度

在学习数据结构和算法之前，每一个初学者第一步要熟练掌握的就是时间复杂度和空间复杂度，它是用来计算一个算法的运行效率的（算法效率）。

比如说大家喝粥，如果用勺子的话效率更高，但是你用筷子效率就太低了😜😜😜

怎样才能让我们更快更好的喝到粥呢？所以就有了算法效率。

1.1算法效率

🎤 算法效率可以分为两种：一是时间效率，二是空间效率。时间效率就是我们所熟知的时间复杂度，而空间效率就是空间复杂度。顾名思义，时间复杂度是用来衡量一个算法的运行速度，空间复杂度就是衡量一个算法需要的额外空间。

1.1.1时间复杂度

🎤 因为每个计算机怎么可能相同，比如你下铺用的是3080，而你的1060😣😣😣, 很显然不能用运行时间来衡量，那么到底什么是时间复杂度呢。即：算法中的基本操作的执行次数，为算法的时间复杂度，也就是说一个代码的理论执行次数。

1.1.2空间复杂度

🎤对于程序来说，运行过程中都会不等的占用许多空间，如程序本身的空间；输入输出的数据；动态申请的空间等，对算法的空间复杂度影响最大的，往往是程序运行过程中所申请的临时存储空间，即：空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度

2.时间复杂度和空间复杂度的计算

🎤既然我们了解了什么是时间复杂度和空间复杂度，那么它们都是如何计算的呢😧😧😧？下面列举出一些常见的例子，这两个的计算都是用大写O表示的（大O：是用来描述函数渐进行为的数学符号）

2.1时间复杂度的计算

🎤如下：请问Func1基本执行了多少次？

voidFunc1(int N){int count =0;for(int i =0; i < N ;++ i){for(int j =0; j < N ;++ j){++count;}}for(int k =0; k <2* N ;++ k){++count;}int M =10;while(M--){++count;}printf("%d\n", count);}

🎤Func1的执行操作次数是两个for循环嵌套和一个单独for循环和一个while循环组成，他的操作次数就是F(N)=N²+2N+10，当N为10时，F(N)=130;当N为100时，F(N)=10210;当N=1000时，F(N)=1002010，但是在实际中我们并不需要计算的如此精确，，只需要大致执行次数就行，用😎大O的渐进表示法😎来表示，先来介绍一下大O阶方法如下：*

推导大O阶方法：

• 用常数1取代运行时间中的所有加法常数；
• 在修改后的运行次数函数中，只保留最高阶项；
• 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

🎤使用大O阶方法后，估算上面这个Func1的时间复杂度就为：O(N²)；

• 若N=10，F(N)=100;
• 若N=100，F(N)=10000;
• 若N=1000，F(N)=1000000.

用上面的方法之后，去掉了对结果影响不大的值后，简洁明了的表示出了执行次数，但是有些算法的时间复杂度存在最好，最坏和平均情况，如下：在数组长度为N的数组里找一个元素K😁😁😁

for(i =0; i < N; i++)//N数组的长度{if(arr[i]== K)//K要查找的元素{printf("找到了\n");return;}
    i++;}printf("没找到\n");

• 最好情况：😁1次找到；最坏情况：😔N次找到；平均情况：😕N/2次找到。

🎤在实际中，我们一般关注最坏的那种结果，就是时间复杂度，所以上面那个数组查找元素的**时间复杂度就是O(N)**。下面2.2.4会详细讲

2.2常见时间复杂度的计算

• 2.2.1 计算Func2的时间复杂度？

voidFunc2(int N){int count =0;for(int k =0; k <2* N ;++ k){++count;}int M =10;while(M--){++count;}printf("%d\n", count);}

这次执行了一个for循环和一个while循环，执行次数为2N+10，根据推导大O阶方法，Func2的时间复杂度为O(N)

• 2.2.2 计算Func3的时间复杂度？

voidFunc3(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);}

这次执行了两个for循环，但不是嵌套for循环，而且题意中也没有说M极大或者N极大，所以执行次数为M+N次，所以Func3的时间复杂度为O(M+N)

• 2.2.3 计算Func4的时间复杂度？

voidFunc4(int N){int count =0;for(int k =0; k <100;++ k){++count;}printf("%d\n", count);}

这里的N很明显没有用上，随着N的增大，执行次数与它无关，不管这里的k循环多少次，100次还是10000次，只要是常数字，都用1代替（推导大O阶的第一条）， 所以Func4的时间复杂度为O(1)

• 2.2.4 计算strchr的时间复杂度？ 这是一个遍历字符串的程序，在字符串中找你需要找的字符的程序

constchar*strchr(constchar* str,char character ){while(*str !='\0'){if(*str == character)return str;++str;}returnNULL;}

解释如下图：

为什么考虑最坏的？

🎤最坏情况可以告诉我们算法性能的上限，分析一个算法的最坏情况可以保证在任何情况下此算法的表现都不会比最坏情况差

则 strchr的时间复杂度为O(N)

• 2.2.5 计算BubbleSort的时间复杂度？ 这个是冒泡排序，基本思想：

voidBubbleSort(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;}}

> BubbleSort的时间复杂度是O(N²)

• 2.2.6 计算BinarySearch的时间复杂度？

intBinarySearch(int* a,int n,int x){assert(a);int begin =0;int end = n;while(begin < end){int mid = begin +((end-begin)>>1);if(a[mid]< x)
     begin = mid+1;elseif(a[mid]> x)
     end = mid;elsereturn mid;}return-1;}

🎤这是一个二分查找的算法，它的基本思想是：
二分查找也被称为折半查找，是一种高效的查找方法，前提数组是有序的，思想是将n个元素分成大致相等的两部分，取a [n/2]与x做比较，如果x=a [n/2],则找到x,算法中止；如果x<a [n/2],则只要在数组a的左半部分继续搜索x,如果x>a [n/2],则只要在数组a的右半部搜索x（可以理解为一张纸先找中间然后折叠）。

BinarySearch的时间复杂度为 log以2为底N的对数，即：O(logN)

• 2.2.7 计算阶乘递归Factorial的时间复杂度？

longlongFactorial(size_t N){return N <2? N :Factorial(N-1)*N;}

🎤这是一个递归（自己调用自己）求阶乘问题，基本思想如下图

递归调用了N次，每次递归计算三次——时间复杂度为O(1)，整体就是O(N)，所以Factorial的时间复杂度是O(N)

2.2综上所述常见的时间复杂度以及对比：
🎤 常见：O(N) —— O(N²) —— O(1) —— O(logN)
🎤 对比：如下图

😎😎😎

2.4时间复杂度的计算

由上面1.1.2简单理解为空间复杂度就是计算变量的个数，同样使用😎大O的渐进表示法😎

话不多说直接上例子😆😆😆

• 2.4.1 计算BubbleSort的空间复杂度？

voidBubbleSort(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;}}

🎤 与2.2.5一样，都是冒泡排序，既然知道了空间复杂度就是求变量个数，这个代码一眼望去就是五个（int exchange = 0；size_t end = n；size_t i = 1；int a；int n），由大O阶的方法1可知时间复杂度O(1)，这里可能就有同学问了：“这是循环呀，为什么空间一直是一个呢？”，这里就牵扯到了一个重点*时间是累计的，空间不累计，虽然循环走了N次，但是使用的还是一块空间

BubbleSort的空间复杂度即为O(1)

• 2.4.2 计算Fibonacci的空间复杂度？

longlong*Fibonacci(size_t n){if(n==0)returnNULL;longlong* fibArray =(longlong*)malloc((n+1)*sizeof(longlong));
          fibArray[0]=0;
     fibArray[1]=1;for(int i =2; i <= n ;++i){
           fibArray[i ]= fibArray[ i -1]+ fibArray [i -2];}return fibArray ;}

🎤这个代码中的变量一眼望去就有五个，但是被大家忽略了malloc这个动态内存开辟，它开辟了N+1，精准空间复杂度就显然是O(N+6)个，但是由大O阶方法2可得随着N的增大，这个常数6对整体结果影响不大，

所以空间复杂度是O(N)

• 2.4.3 计算阶乘递归Factorial的空间复杂度？

longlongFactorial(size_t N){return N <2? N :Factorial(N-1)*N;}

**🎤这个还是一个阶乘，与上面求时间复杂度2.2.7是一模一样的，不懂递归的可以重新回去看看。递归调用了N层，每次递归调用就要开辟一个栈帧，每个栈帧使用了常数个空间——O(1)，整体就是O(N)*（注意：递归调用时建立栈帧，返回时销毁，空间复杂度就是O(1)，但是空间复杂度是计算最大时，最坏时的大小）*

所以时间复杂度是O(N)

总结

时间复杂度和空间复杂度的作用大家可想而知，比如参加某些算法比赛，某些公司的笔试题，数据结构的入门必学。本人呢会持续更新《数据结构》，大家如果觉得解元写的不错可以三连哦😘😘😘也祝大家前程似锦，光芒万丈☀️☀️☀️