C语言数据结构与算法时间空间复杂度基础实践

2024-04-02 19:55

短信预约 -IT技能 免费直播动态提醒

小感想

今天去看了看许多人今年去各个大厂面试的面经，确实如大体所说，各大公司越来越注重性能迭代，时代需要数据结构与算法这样的考试。

一个公司的成本主要来自于人力成本，但是上了规模写核心代码的人少了，成本就会来自于机器，资源，时间，抢占到这些就相当于无时无刻在减少客户流失。所以同样一段代码给两个人写，甲拿 8000，乙拿 25000，但是后者效率提高了50%，而这50%带来的收益远远超过了（25000-8000），这就是为什么许多大厂要给出如此吸引人的高薪资来招贤纳士。

说回来要省时间省资源就无法规避掉算法，所以说总会有那么一天咱还是得要直面恐惧。

时间复杂度

上一篇搞定了复杂度的相关概念，现在就可以直接上阵实战一手了，为什么要专门搞一个计算实践，因为不仅是工作，学校考试啊复杂度也是和算法直接挂钩的趁瓷器活没来赶紧磨磨咱的金刚钻。

来看第一个：

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)，这个优化简直就是质的优化，这个思想就是以空间换时间，开了一个数组，都用了空间，但是性能更快了。