进入数据结构的世界

数据结构和算法的概述

  • 一、什么是数据结构
  • 二、什么是算法
  • 三、如何去学习数据结构和算法
  • 四、算法的时间复杂度和空间复杂度
    • 4.1 算法效率
    • 4.2 大O的渐进表示法
    • 4.3 时间复杂度
    • 4.4 空间复杂度
    • 4.5 常见复杂度对比

一、什么是数据结构

数据结构是计算机存储、组织数据的方式。(相互之间存在一种或多种特定关系的数据元素的集合)

二、什么是算法

算法就是一系列的计算步骤,用来吧输入数据转换成输出结果。(算法就是有良好的计算过程,把一个或一组的值输入,并产出一个或一组的值输出)

三、如何去学习数据结构和算法

现在的公司对学生的代码能力越来越高,数据结构和算法的题目越来越难。算法的能力在短期内是不能够快速提升的,需要进行算法训练的积累。校招的时候,笔试很难,为了能够找到工作,还需要对数据结构和算法早早的准备,多去训练算法能力。
数据结构和算法对于初学者来说很难。但 是,古话说的好,世上无难事,只怕有心人。不管数据结构和算法有多难,我们都要硬着头皮去学。我相信,只要多学多练,学习数据结构和算法就会越来越简单。

四、算法的时间复杂度和空间复杂度

时间空间这两个维度能够衡量算法的好坏,

4.1 算法效率

算法在编写成可执行程序后,运行程序需要耗费空间资源时间资源。因此,衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,这就是时间复杂度空间复杂度

时间复杂度主要是衡量算法的运行快慢,而空间复杂度主要是衡量一个算法运行时所需要的额外空间。(计算机发展的早期,计算机存储的容量很小,我们对空间复杂度很在乎。但是经过计算机行业的快速发展,计算机存储的容量已经达到了很高的地步。所以我们今天已经不需要特别在关注算法的空间复杂度)

4.2 大O的渐进表示法

大O符号(Big O notation):用于描述函数渐进行为的数学符号
大O的渐进表示法的推导方法:

1、用常数1取代运行时间中所以的加法常数。
2、在运行次数函数中,只保留最高阶项。
3、如果最高价项存在且不是1,则去除与这个项相乘的常数,得到的结果就是大O阶。

算法的时间复杂度存在最好、平均和最坏情况:

最好情况:任意输入规模的最大运行次数(上界)
平均情况:任意输入规模的期望运行次数
最坏情况:任意输入规模的最小运行次数(下界)

例如:在一个长度为N的数组中搜索一个数据x

最好情况:1次找到
平均情况:N/2次找到
最坏情况:N次找到

实际中,我们关注的都是算法的最坏情况所以,数组中搜索数据的时间复杂度为O(N)

4.3 时间复杂度

时间复杂度的定义:
一个算法执行所消耗的时间,从理论上说,是不能够算出来得,只有把程序放在机器上跑,才能够知道消耗的时间。一个算法所花费的时间与其中语句的执行次数成正比,算法的基本操作的执行次数,就是算法的时间复杂度。
案例1:

找到基本语句与问题规模n的数学表达式,算出该算法的时间复杂度。

//计算++count语句执行的次数
#include <stdio.h>
int main()
{int n = 0;scanf("%d", &n);int count = 0;for (int i = 0; i < n; i++){for (int j = 0; j < n; j++)++count;}for (int i = 0; i < 2 * n; i++){++count;}int m = 10;while (m--){++count;}printf("%d\n", count);return 0;
}

基本操作次数:
F(n)=n^2+2*n+10

  • n=10 F(n)=130
  • n=100 F(n)=10210
  • n=1000 F(n)=1002010

用大O的渐进表示法,时间复杂度为O(N^2)

  • n=10 F(n)=100
  • n=100 F(n)=10000
  • n=1000 F(n)=1000000

实际中我们计算时间复杂度时,并不一定计算精准的时间复杂度,而只需要大概执行次数,这里我们使用大O的渐进表示法。

通过上面我们可以发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。
案例2:

计算Fun2的时间复杂度
void Fun2()
{int N;scanf("%d", &N);int count = 0;for (int i = 0; i < 2 * N; i++){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

Fun2的时间复杂度为:
F(N)=2*N+10
大O的渐进表示法:时间复杂度为O(N)
案例3:

//计算Fun3的时间复杂度
void Fun3()
{int N, M;scanf("%d%d", &N, &M);int count = 0;for (int i = 0; i < N; i++){++count;}for (int j = 0; j < M; j++){++count;}printf("%d\n", count);
}

Fun2的时间复杂度为:
F(N)=N+M
大O的渐进表示法:时间复杂度为O(N)
案例4:

//二分查找的思想
void Fun4()
{int m = 0;int arr[10] = { 1,2,4,6,8,11,55,66,77,88};int n;printf("请输入要查找的数:\n");scanf("%d", &n);int begin = 0;int end = 9;while (begin <= end){int mid = begin + (end - begin)/2;if (arr[mid] < n)begin = mid + 1;else if (arr[mid] > n)end = mid - 1;else{printf("找到了\n");printf("%d", arr[mid]);m = 1;break;}}if(m==0)printf("没找到\n");
}

区间数据个数:
N
N/2
N/2/2
…………
N/2/2/2……/2=1

最坏的情况,查找区间缩放只剩一个值时,就是坏得,
假设查找x次,2^x=N,所以x=logN。

大O的渐进表示法:时间复杂度为O(logN).

案例5:

//斐波那契递归的复杂度
#include <stdio.h>
int Fun5(size_t n)
{if (n < 3)return 1;return Fun5(n - 2) + Fun5(n - 1);}
int main()
{int n = 7;int sum=Fun5(n);printf("%d\n", sum);return 0;
}

打印结果:
在这里插入图片描述
递归展开图:
在这里插入图片描述
1次(2^ 0)
2次(2^ 1)
4次(2^ 2)
8次(2^ 3)
……
2^(N-1)次
通过函数递归图分析基本操作递归了2 ^N-1次,
大O的渐进表示法:时间复杂度为O (2 ^N)。

4.4 空间复杂度

空间复杂度的定义:
一个算法在运行过程中临时占用存储空间大小的量度。(空间复杂度算的是变量的个数)
注意:
函数运行时所需要的栈空间(存储函数、局部变量、一些寄存器信息等)在编译期间就已经确定好了,因此,空间复杂度主要就是函数在运行的时候申请的额外空间来确定的。
案例1:

//计算BubbleSort函数的空间复杂度
void BubbleSort(int* a, int n)
{assert(a);for (int end = n; end > 0; end--){int exchange = 0;for (int i = 1; i < n; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}//不需要循环了if (exchange == 0)break;}
}

可以看出使用了常数个额外空间,所以空间复杂度为O(1)
案例2:

//看返回斐波那契数列的前n项,计算Fibonac的空间复杂度
int* Fibonac(int n)
{if (n == 0)return NULL;int* fibar = (int*)malloc(sizeof(int) * (n + 1));fibar[0] = 0;fibar[1] = 1;for (int i = 2; i <= n; i++){fibar[i] = fibar[i - 1] + fibar[i - 2];}return fibar[i];
}

动态开辟了n+1个空间,大O的渐进表示法为O(N);

4.5 常见复杂度对比

在这里插入图片描述

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/139790.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

java框架-Springboot3-基础特性+核心原理

文章目录 java框架-Springboot3-基础特性核心原理profiles外部化配置生命周期监听事件触发时机事件驱动开发SPISpringboot容器启动过程自定义starter java框架-Springboot3-基础特性核心原理 profiles 外部化配置 生命周期监听 事件触发时机 事件驱动开发 Component public c…

Hana SQL Format 的希望

以前一直吐槽Hana Sql 无法进行代码格式化&#xff0c;没有abap code的pretty print功能&#xff0c;对运维和理解代码来说都很不方便。这个情况在abap cleaner里得到改善。 现阶段他们abap的美化做的比原始的pretty print还要好&#xff0c;我基本已经不用pretty print&#x…

获取文件上次访问时间

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl Java源码 public void testGetFileTime() {try {String string "E://test.txt";File file new File(string);Path path file.toPath();BasicFileAttributes ba…

TypeScript- 对于对象键名(包括函数键值)不确定的接口,可以使用字符串索引的形式

AXIOS树配置项 有一个需求&#xff0c;通过JSON数据&#xff0c;第一层是对应的页面对象&#xff08;比如是用户页面&#xff09;&#xff0c;第二层是该页面的API请求名&#xff08;比如用户的增删改查&#xff09;&#xff0c;第三层是该API的配置信息&#xff08;比如&…

系统安装(一)CentOS 7 本地安装

CentOS与Ubuntu并称为Linux最著名的两个发行版&#xff0c;但由于笔者主要从事深度学习图像算法工作&#xff0c;Ubuntu作为谷歌和多数依赖库的亲儿子占据着最高生态位。但最近接手的一个项目里&#xff0c;甲方指定需要在CentOS7上运行项目代码&#xff0c;笔者被迫小小cos了一…

scikit-learn机器学习算法封装

K近邻算法 K-最近邻&#xff08;KNN&#xff09;是一种有监督的机器学习算法&#xff0c;可用于解决分类和回归问题。它基于一个非常简单的想法&#xff0c;数据点的值由它周围的数据点决定。考虑的数据点数量由k值确定。因此&#xff0c;k值是算法的核心。 我们现在已经知道。…

mac安装chromedriver驱动详细步骤

1.查看浏览器版本 2.下载驱动 3.安装驱动 4.MacOS无法打开“chromedriver”&#xff0c;因为无法验证开发者 1.查看浏览器版本 在这里插入图片描述 2.下载驱动 下载驱动地址&#xff1a;链接: http://chromedriver.storage.googleapis.com/index.html. 下载和浏览器版本一致的…

解决因为修改SELINUX配置文件出错导致Faild to load SELinux poilcy无法进入CentOS7系统的问题

一、问题 最近学习Kubernetes&#xff0c;需要设置永久关闭SELINUX,结果修改错了一个SELINUX配置参数&#xff0c;关机重新启动后导致无法进入CentOS7系统&#xff0c;卡在启动进度条界面。 二、解决 多次重启后&#xff0c;在启动日志中发现 Faild to load SELinux poilcy…

Windows专业版的Docker下载、安装与启用Kubenetes、访问Kubernetes Dashboard

到Docker 官网https://www.docker.com/ 下载windows操作系统对应的docker软件安装 Docker Desktop Installer-Win.exe 2023-09版本是4.23 下载后双击安装 重启windows后&#xff0c;继续安装 接受服务继续安装 解决碰到的Docker Engine stopped 打开 控制面板》程序》启用或关…

基于微服务的第二课堂管理系统(素质拓展学分管理平台)SpringCloud、SpringBoot 分布式,微服务

基于微服务的第二课堂管理系统 一款真正的企业级开发项目&#xff0c;采用标准的企业规范开发&#xff0c;有项目介绍视频和源码&#xff0c;需要学习的同学可以拿去学习&#xff0c;这是一款真正可以写在简历上的校招项目&#xff0c;能够真正学到东西的一个项目&#xff0c;话…

SpringBoot开发实战(微课视频版)

ISBN: 978-7-302-52819-7 编著&#xff1a;吴胜 页数&#xff1a;311页 阅读时间&#xff1a;2023-06-24 推荐指数&#xff1a;★★★★☆ 本文介绍SpringBoot 2.0.5 、JDK 1.8&#xff0c;虽然现在已经不维护了&#xff0c;但是大体的流程还是对口的&#xff0c; 而且书里面讲…

左神高阶进阶班4 (尼姆博弈问题、k伪进制、递归到动态规划、优先级结合的递归套路、子串的递归套路,子序列的递归套路,动态规划的压缩技巧)

目录 【案例1 尼姆博弈问题】 【题目描述】 【思路解析】 【代码实现】 【案例2 k伪进制问题】 【题目描述】 【思路解析】 【代码实现】 【案例3 最大路径和】 【题目描述】 【思路解析】 【代码实现】 【案例4 优先级的递归套路】 【题目描述】 【思路解析】…

黑马JVM总结(二十三)

&#xff08;1&#xff09;字节码指令-init 方法体内有一些字节&#xff0c;对应着将来要由java虚拟机执行方法内的代码&#xff0c;构造方法里5个字节代码&#xff0c;main方法里有9个字节的代码 java虚拟机呢内部有一个解释器&#xff0c;这个解释器呢可以识别平台无关的字…

整合车辆出险报告Api接口,轻松管理车险理赔!

随着车辆保有量的不断增加&#xff0c;车辆出险的情况也越来越普遍。对于车主来说&#xff0c;如何高效地管理车险理赔&#xff0c;处理保险事故是非常重要的。这时候我们就可以借助整合车辆出险报告API接口&#xff0c;实现快速定位理赔信息&#xff0c;轻松管理车险理赔。 一…

MongoDB(一) windows 和 linux 之 Ubuntu 安装

数据库分类 一、关系型数据库&#xff08;RDBMS&#xff09; mysql 、Oracle、DB2、SQL Server 关系数据库中全都是表 二、非关系型数据库&#xff08;NO SQL&#xff09; MongoDB、Redis 键值对数据库 文档数据库MongoDB 下载 mongoDB https://www.mongodb.com/try/downloa…

自动化测试的定位及一些思考

大家对自动化的理解&#xff0c;首先是想到Web UI自动化&#xff0c;这就为什么我一说自动化&#xff0c;公司一般就会有很多人反对&#xff0c;因为自动化的成本实在太高了&#xff0c;其实自动化是分为三个层面的&#xff08;UI层自动化、接口自动化、单元测试&#xff09;&a…

【论文写作】符号:矩阵、向量的乘法、内积、点积等

【论文写作】符号&#xff1a;矩阵、向量乘法、内积、点积等 文章目录 【论文写作】符号&#xff1a;矩阵、向量乘法、内积、点积等1. 矩阵乘法1.1 矩阵乘积1.2 矩阵哈德玛乘积1.3 矩阵克罗内克积 2. 向量乘法2.1 向量点积、内积2.2 向量Hadamard积2.3 向量外积2.4 向量叉积 1.…

[论文笔记]Prefix Tuning

引言 今天带来微调LLM的第二篇论文笔记Prefix-Tuning。 作者提出了用于自然语言生成任务的prefix-tuning(前缀微调)的方法,固定语言模型的参数而优化一些连续的任务相关的向量,称为prefix。受到了语言模型提示词的启发,允许后续的token序列注意到这些prefix,当成虚拟toke…

Go的error接口

从本书的开始&#xff0c;我们就已经创建和使用过神秘的预定义error类型&#xff0c;而且没有解释它究竟是什么。实际上它就是interface类型&#xff0c;这个类型有一个返回错误信息的单一方法&#xff1a; type error interface { Error() string } 创建一个error最简单的方…

高效查询大量快递信息,轻松掌握技巧

在如今快节奏的生活中&#xff0c;快递已经成为我们日常不可或缺的一部分。然而&#xff0c;对于一些忙碌的人来说&#xff0c;单个查询每一个快递单号可能会浪费太多时间。因此&#xff0c;我们需要一款可以帮助我们批量查询快递的软件。 在市场上&#xff0c;有很多款专门用于…