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

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

时间复杂度

来看第一个：

long Func(n)
{
return n<2?n:Func(n-1)*n ;
}

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

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

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

再来

long Func(n)
{
return n<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>
long long*Func(n)
{
long long* Farr= malloc(sizeof(long long)*(n+1));
Farr[0] = 0;
if(n==0)  // 防止n=0时发生越界
{
return Farr;
}
Farr[1] = 1;
}

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

空间复杂度

说是空间复杂度，和空间也不沾关系，他计算的是大概定义的变量的个数，实际意义里面就算是结构体大不了你几十个字节嘛，也没必要去整烂活搞几万个字节出来。我小小 8个G，几十亿字节，你占用我几字节，几百字节，几千字节我压根儿不甩你，所以为什么不谈空间大小谈个数。

可能如今就只有嵌入式比较介意空间，因为嵌入式通常是在一些设备上面，举个栗子就是我们常见的智能居家AI，一个吸尘器机器人会用到的探测器算法，内存条占用多了机器咋安是吧，不是内存贵是空间有限

我们就拿刚刚的阶乘来说，从n开始，会建立一个栈帧，每调用一次递归就要创建一个栈帧，每个栈帧里面空间是常数个，调用了n次，那么空间复杂度就是常数×n为O(N)。

关于“C语言数据结构与算法时间空间复杂度实例分析”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识，可以关注亿速云行业资讯频道，小编每天都会为大家更新不同的知识点。