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语言数据结构与算法时间空间复杂度的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C语言简单实现快速排序

    快速排序是一种不稳定排序,它的时间复杂度为O(n·lgn),最坏情况为O(n2):空间复杂度为O(n·lgn). 这种排序方式是对于冒泡排序的一种改进,它采用分治模式,将一趟排序的数据分割成独立的两部分,其中一组数据的每个值都小于另一组.每一趟在进行分类的同时实现排序. 其中每一趟的模式通过设置key当基准元素,key的选择可以是数据的第一个,也可以是数据的最后一个.这里以每次选取数据的第一个为例: 具体代码实现: #include<stdio.h> #define N 6 int fun(i

  • C语言关于时间复杂度详解

    C语言关于时间复杂度详解

    目录 一.时间复杂度 1.什么是时间复杂度? 2.如何计算? 3.常见的时间复杂度: 二.空间复杂度 1.什么是空间复杂度? 2.如何计算? 总结 一.时间复杂度 1.什么是时间复杂度? 空间效率,时间效率(较为关注) 时间复杂度:算法中的操作执行次数,为算法的时间复杂度.(不是具体时间,而是执行次数) 2.如何计算? 时间复杂度 (1)是一个估算,看表达式中影响大的那一项,如N*N+2N+10中,N*N对整个式子影响最大,故其时间复杂度为N*N,用大O的渐近表示法O(N*N). (2)去掉时间

  • C语言数据结构时间复杂度及空间复杂度简要分析

    C语言数据结构时间复杂度及空间复杂度简要分析

    目录 一.时间复杂度和空间复杂度是什么? 1.1算法效率定义 1.2时间复杂度概念 1.3空间复杂度概念 二.如何计算常见算法的时间复杂度和空间复杂度 2.1时间复杂度计算 2.2空间复杂度计算 2.3快速推倒大O渐进表达法 三.一些特殊的情况 总结 一.时间复杂度和空间复杂度是什么? 1.1算法效率定义 算法效率分为两种,一种是时间效率--时间复杂度,另一种是空间效率--空间复杂度 1.2时间复杂度概念 时间复杂度,简言之就是你写一个代码,它解决一个问题上需要走多少步骤,需要花费多长时间.打个

  • 用C语言举例讲解数据结构中的算法复杂度结与顺序表

    用C语言举例讲解数据结构中的算法复杂度结与顺序表

    数据结构算法复杂度 1.影响算法效率的主要因素 (1)算法采用的策略和方法: (2)问题的输入规模: (3)编译器所产生的代码: (4)计算机执行速度. 2.时间复杂度 // 时间复杂度:2n + 5 long sum1(int n) { long ret = 0; \\1 int* array = (int*)malloc(n * sizeof(int)); \\1 int i = 0; \\1 for(i=0; i<n; i++) \\n { array[i] = i + 1; } for(

  • C语言数据结构与算法之时间空间复杂度入门

    C语言数据结构与算法之时间空间复杂度入门

    目录 数据结构与算法 什么是数据结构?什么是算法? 分析维度 大O的渐进表示法 常数阶 线性阶 对数阶 其他时间复杂度指标 空间复杂度 数据结构与算法 终于开始搞这块难啃的骨头了,走上这条漫漫长路之前要明白: 什么是数据结构?什么是算法? 是数据之间存在一种或多种特定关系的数据元素集合,为编写出一个“好”的程序,必须分析待处理对象的特性及各处理对象之间存在的关系,这也就是研究数据结构的意义所在为编写出一个“好”的程序,必须分析待处理对象的特性及各处理对象之间存在的关系这也就是研究数据结构的意义所

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

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

    目录 小感想 时间复杂度 空间复杂度 小感想 今天去看了看许多人今年去各个大厂面试的面经,确实如大体所说,各大公司越来越注重性能迭代,时代需要数据结构与算法这样的考试. 一个公司的成本主要来自于人力成本,但是上了规模写核心代码的人少了,成本就会来自于机器,资源,时间,抢占到这些就相当于无时无刻在减少客户流失.所以同样一段代码给两个人写,甲拿 8000,乙拿 25000,但是后者效率提高了50%,而这50%带来的收益远远超过了(25000-8000),这就是为什么许多大厂要给出如此吸引人的高薪资来

  • C语言数据结构通关时间复杂度和空间复杂度

    目录 1.时间复杂度: 1.常数阶 2.线性阶 3.对数阶 4.平方阶 2.算法空间复杂度 算法的时间复杂度和空间复杂度 1.时间复杂度: 首先,为什么会有这个概念的出现呢? 原来啊,在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级.算法的时间复杂度,也就是算法的时间量度,记作T(n) = O(f(n)).它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度,其中f(

  • C语言数据结构之算法的时间复杂度

    C语言数据结构之算法的时间复杂度

    目录 1.算法的复杂度 2.时间复杂度 2.1 时间复杂度的定义 2.2 大O的渐进表示法 3.常见时间复杂度计算举例 3.1 冒泡排序的时间复杂度 3.2 二分查找的时间复杂度 3.3 阶乘(递归)的时间复杂度 3.4菲波那切数列的时间复杂度 1.算法的复杂度 算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 .因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度. 时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的

  • C语言数据结构与算法之链表(一)

    C语言数据结构与算法之链表(一)

    目录 引言 链表的相关思考 链表结点结构 建立链表 实现插入操作 完整代码 引言 在存储一大波数的时候,我们通常使用的是数组,但是数组有时候又会显得不够灵活,比如下面这个例子: 有一串已经排序好的数 2,3,5,8,9 ,10 如果我们想要往数组中插入6 这个元素,需要把 8 以后的元素全部往后挪一位 这样操作显然很耗费时间,如果使用链表的话则会快很多.那么什么是链表呢?请看下图: 此时如果需要在8前面加入一个6,那么只需要向下图一样更改一下就可以了,而不用向像最开始那样把每个数向后挪. 链表的

  • C语言数据结构与算法之排序总结(二)

    C语言数据结构与算法之排序总结(二)

    目录 一.前言 二.选择类排序 1.简单选择排序 2.树形选择排序 3.堆选择排序 三.归并排序 四.分配类排序 1.多关键字排序 2.链式基数排序 五.总结归纳 一.前言 之前的排序总结(一)对插入类和交换类排序作了比较详细的总结,对于直接插入.希尔排序.冒泡排序.快速排序要求熟练掌握 这篇排序全面总结(二)主要介绍选择类排序中的简单.树形和堆排序,归并排序.分配类排序的基数排序 二.选择类排序 选择类:每次从待排序的无序序列中,选择一个最大或最小的数字,放到前面,数据元素为空时排序结束 1.

  • C语言数据结构与算法之排序总结(一)

    C语言数据结构与算法之排序总结(一)

    目录 一.前言 二.基本概念 1.排序 2.排序方法的稳定性 3.内部和外部排序 三.插入类排序 1.直接插入排序 2.折半插入排序 3.希尔排序 四.交换类排序 1.冒泡排序 2.快速排序 五.总结比较 一.前言 学习目标: 排序和查找密不可分,将待处理的数据按关键值大小有序排列后,查找更加快速准确 理解各种排序算法的定义和特点,并能将代码灵活运用 掌握各种排序方法时间复杂度与空间复杂度 理解排序稳定和不稳定的概念                 重点和难点: 希尔.快速.堆.归并排序这几种快

  • C语言数据结构与算法之图的遍历(二)

    C语言数据结构与算法之图的遍历(二)

    目录 前言  广度优先搜索过程 主要思想  代码实现   前言  在上一章的内容中我们使用了深度优先搜索来进行遍历,这一章我们选择使用广度优先搜索来完成这个图的遍历 --> 结果如下: 广度优先搜索过程 使用广度优先搜索来遍历这个图的过程如下. 首先以一个未被访问过的顶点作为起始顶点,比如以1号点作为起始顶点. 将1号点放到队列中,然后将与1号点相邻的未访问过的顶点 即 2,3,5号顶点依次放入队列中,如下图: 接下来将2号顶点相邻的未访问过的顶点4号放入到队列中.到此所有的顶点都访问过了,遍历

  • C语言数据结构与算法之图的遍历

    C语言数据结构与算法之图的遍历

    目录 引入  深度优先搜索 代码实现  完整代码   引入  在数据结构中常见的有深度优先搜索和广度优先搜索.为什么叫深度和广度呢?其实是针对图的遍历而言的,请看下面这个图: 图是由一些小圆点(称为顶点) 和 连接这些点的直线 (称为边)组成的. 例如上图就是由5个顶点(编号为 1,2,3,4,5) 和5条边(1-2,1-3,1-4,2-4)组成. 现在我们从1号顶点开始遍历这个图,遍历就是把图的每一个顶点都访问一次.使用深度优先搜索将会得到如下的结果. 图中每个顶点旁边的数表示这个顶点是第几个

  • C语言数据结构与算法之链表(二)

    C语言数据结构与算法之链表(二)

    目录 引入 模拟链表介绍 插入代码实现 代码实现   引入 在上一节的学习中我们介绍了C语言如何实现链表,但是,在这一章,我们将抛开令人头秃的指针和结构体,我们将另外使用一种数组来实现的方式,叫做模拟链表.让我们一起来看看. 模拟链表介绍 链表中的每一个结点都只有两个部分. 我们可以使用一个数组date来储存每序列中的每一个数.那每一个数右边的数是谁,这一点该如何解决呢?在上一章的内容中我们是使用指针来解决的,这里我们只需再用一个数组right来存放序列中每一个数右边的数是谁就可以了.具体要怎么

随机推荐