C语言数据结构与算法时间空间复杂度实例分析

魁首哥

作者

C语言数据结构与算法时间空间复杂度实例分析

这篇文章主要介绍“C语言数据结构与算法时间空间复杂度实例分析”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“C语言数据结构与算法时间空间复杂度实例分析”文章能帮助大家解决问题。

时间复杂度

来看第一个：

longFunc(n){returnn<2?n:Func(n-1)*n;}

我们求递归阶乘Func的时间复杂度，说里面 n 最后要到1，我们可以认为递归了多少次就他就计算了多少次，我们稍加思索就可以看出他的时间复杂度是 O(N)。严格来说，递归算法怎么计算呢？

是递归次数 × 每次递归的函数的次数

这个每次递归函数的次数是个什么鬼呢？我们的三目操作符在递归中每次会走一次，也就是这个函数会出现一次，就是所谓的常数次嘛 O(1)，递归了n次，自然就是O(N)了。如果我再在前面加上个 while(n–)，又是一个执行n次的循环，相当于是在嵌套循环了，这是复杂度就是里外都O(N)，为O(N^2)。

再来

longFunc(n){returnn<2?n:Func(n-1)+(n-2);}

这是斐波那契的递归数列，乍一看和上面的阶乘没太大区别，还是在算他递归了多少次，但是这下可没那么好算了捏。这时我们可以拿起笔画一画多半就有个谱了

最后结果一定会让n走到 1，这个是总数的 n ，2^n的 n 只是一个参数，会发现每一层都会满足等比数列关系，有 2的（n-1）次方的累加 = 2的n次方 - 1，这里1可以忽略就是2的n次方。

但是！完了吗？我们格局打开

这里的-1,是要每一层都是满的才满足，但是实际上不满，我们 n，n-1，n-2……最后是1没毛病；我们到其他路线上，n-2，n-3，n-4……压根儿到不了最后一行，在他头上提早结束，后面的同理，也就是说我们整个流程图在后面会有一大坨空白部分，没有调用次数捏。但是！就算缺吧，这些漏网份子依然相对于整体而言非常的小，影响不大，估算角度他依然是2^n。

其实际图像应该是个三角形：

格局继续打开

那么如果是2的n次方，那么你将见证一个计算时间复杂度的极端，要知道算法中二分查找是非常快的，要在10亿对象中找一个只需要 log2^1000000000,即30秒左右。

但是上面的斐波那契运行起来可谓慢的令人发指，我在之前在学习C语言递归时就在vs2019上试过，当n = 10时，1000次，小儿科秒出；n = 30时，十亿次，很快啊，看来CPU是有备而来，n = 50时，可以说久了去了,整个程序没有卡死胜似卡死。

看看咱CPU运行速度是多少赫兹可以换算运行速度，一般民用配置高一点点的能达到一秒十亿次计算，别看n只是涨了一点点，电脑寿命够长就给n整个80，你的寿命够长就可以给n整个100。

我们使用递归搞斐波那契会有许多重复，我们改进一下：

#include<stdio.h>#include<malloc.h>longlong*Func(n){longlong*Farr=malloc(sizeof(longlong)*(n+1));Farr[0]=0;if(n==0)//防止n=0时发生越界{returnFarr;}Farr[1]=1;}

这个算法就是有前面就能推后面，再看看时间复杂度是O(N)，这个优化简直就是质的优化，这个思想就是以空间换时间，开了一个数组，都用了空间，但是性能更快了。