C语言数据结构与算法时间空间复杂度基础实践
小感想
今天去看了看许多人今年去各个大厂面试的面经,确实如大体所说,各大公司越来越注重性能迭代,时代需要数据结构与算法这样的考试。
一个公司的成本主要来自于人力成本,但是上了规模写核心代码的人少了,成本就会来自于机器,资源,时间,抢占到这些就相当于无时无刻在减少客户流失。所以同样一段代码给两个人写,甲拿 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),这个优化简直就是质的优化,这个思想就是以空间换时间,开了一个数组,都用了空间,但是性能更快了。
空间复杂度
说是空间复杂度,和空间也不沾关系,他计算的是大概定义的变量的个数,实际意义里面就算是结构体大不了你几十个字节嘛,也没必要去整烂活搞几万个字节出来。我小小 8个G,几十亿字节,你占用我几字节,几百字节,几千字节我压根儿不甩你,所以为什么不谈空间大小谈个数。
可能如今就只有嵌入式比较介意空间,因为嵌入式通常是在一些设备上面,举个栗子就是我们常见的智能居家AI,一个吸尘器机器人会用到的探测器算法,内存条占用多了机器咋安是吧,不是内存贵是空间有限
我们就拿刚刚的阶乘来说,从n开始,会建立一个栈帧,每调用一次递归就要创建一个栈帧,每个栈帧里面空间是常数个,调用了n次,那么空间复杂度就是常数×n为O(N)。
今天就先到这里吧,摸了家人们。
以上就是C语言数据结构与算法时间空间复杂度基础实践的详细内容,更多关于C语言数据结构与算法时间空间复杂度的资料请关注猪先飞其它相关文章!
原文出处:https://blog.csdn.net/qq_61500888/article/details/121629715
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要是介绍了.net C# 实现任意List的全组合算法实现代码,需要的朋友可以参考下...2020-06-25
同时兼容JS和C#的RSA加密解密算法详解(对web提交的数据加密传输)
这篇文章主要给大家介绍了关于同时兼容JS和C#的RSA加密解密算法,通过该算法可以对web提交的数据进行加密传输,文中通过图文及示例代码介绍的非常详细,需要的朋友们可以参考借鉴,下面来一起看看吧。...2020-06-25图文详解Heap Sort堆排序算法及JavaScript的代码实现
这篇文章以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下...2016-05-05- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C#常用数据结构和算法,这里我们总结了一些知识点,可以帮助大家理解这些概念。...2020-06-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25