【01课_初识算法与数据结构】

一、理解算法

1、算法的概念

算法,个人理解就是计算一段逻辑,最简化,最快速的方式、方法

每个函数,就包含了一定的算法,执行一定的计算逻辑

算法是一系列程序指令,用于解决特定的运算和逻辑问题

2、衡量算法好坏的标准

【数据结构】详解时间复杂度和空间复杂度的计算_时间复杂度怎么算-CSDN博客

有时会需要牺牲空间来换取时间,绝大多数情况下,时间复杂度是更重要的,宁可多分配一下空间,也要提升程序的运行速度

1)(渐进)时间复杂度:O

程序运行时间长短。执行的很慢肯定很难受。

时间复杂度是把程序的相对执行时间函数,简化成一个数量级,这个数量级可以是n,n^2,n^3等3个规则:1、如果运行时间是常数量级,则用常数1表示
2、只保留时间函数中的最高阶项
3、如果最高阶项存在,就可以省去最高阶项前面的系数再翻译上面的三个规则:1、用常数1取代运行时间中的所有加法常数。O(100)=> O(1)
2、在修改后的运行次数函数中,只保留最高阶项。O(N^2+N)=> O(N^2)
3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。O(2N^2)=> O(N^2)时间复杂度算的是执行次数,而不是具体的时间。并不是有多少个循环次数时间复杂度就是多少,得具体分析算法逻辑

例如:

1.1)T(n) =3,只有常数量级,转化的时间复杂度就是 T(n) =O(1)

1.2)T(n) =0.5n^2 + 0.5n,最高阶项是0.5n^2,则只保留最高阶0.5n^2,并省去系数0.5,转化的时间复杂度就是 T(n) =O(n^2)

1.3)T(n) =3n ,最高阶项是3n,就可以省去系数3,转化的时间复杂度就是 T(n) =O(n)

1.4)T(n) = 5logn,就可以省去系数5,转化的时间复杂度就是 T(n) =O(logn)

排序:O(1) < O(logn) < O(n) < O(n^2)

2)空间复杂度

程序临时占用存储空间大小,占用空间大,占用有限的计算机资源,其他事干不了了

空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,空间复杂度算的是变量的个数
2.1)常量空间

算法的存储空间大小固定,和输入规格没有直接关系,空间复杂度记为O(1)

有5个变量,相当于开辟了5个空间,这样一来:O(1),因为5是常数
2.2)线性空间

当算法分配的空间是线性集合,如列表,切集合大小和输入规模n成正比,空间复杂度记为O(n)

我们可以知道准确的空间复杂度有O(N+6) 但实际是O(N)其中malloc表达的含义是连续开辟了n+1的long long类型的数组。
2.3)二维空间

算法分配的空间是一个二维列表组合,且集合的长度和宽度斗鱼输入的规模n成正比,空间复杂度记为O(n^2)

2.4)递归空间

fun(n)>0 ,程序才会执行,达到函数结束条件,即 fun(n)<= 0,递归结束

O(n)

3、算法的应用

1)运算

2)查找

3)排序

4)最优决策

二、理解数据结构

1、数据结构的概念

数据结构是数据的组织、管理和存储格式,目的是更高效地访问和修改数据

2、数据结构的类型

1)线性结构

例如:数组、链表、这样的线性结构的物理结构,以及由他们衍生出来的线性结构的逻辑结构:栈、队列等

哈希表

1.1)关于数组
在python语言中,,没有直接使用数组的概念,而是使用列表和元组这两种集合,本质都是对数组的封装。列表是一个动态可扩展的数组、支持任意的增、删、改元素。列表在内存中的存储方式是顺序存储而元组是一个不可变的集合,一旦创建,就不再变化。我们大多用到的是列表对应数组这个概念。数组适合读操作多,写操作少的场景

列表读取 和 更新元素的时间复杂度都是O(n),  因为可以指定元素进行一次操作

数组的插入、删除元素的时间复杂度是O(n),因为涉及后续元素的移动操作

1.2)关于链表 
链表是一种在物理上非连续、非顺序的数据结构,由若干节点所组成。链表在内存中的存储方式是随机存储单向链表的每一个节点由两部分组成,一部分是存放数据的变量data,另一部分是指向下一个节点的指针next
链表的第一个节点是头结点,最后一个节点是尾节点,尾节点的next指针指向空与列表的可以随机读取元素不同,对于链表上的元素,我们只能根据前一个节点的指针才能找到下一个节点如果想让每个节点都能回溯到它的前置节点,可以使用双向链表,具有指向前置节点的prev指针

链表的元素的查找,时间复杂度是O(n),因为要从头节点开始一个个查找

只考虑链表的元素的更新,不考虑之前的查找操作,时间复杂度是O(1),因为只对那1个节点操作

只考虑链表的插入、删除操作,不考虑之前的查找操作,时间复杂度是O(1),因为只操作1个或者前后2个节点,都是常量

1.3)栈

类似羽毛球的桶,有开着的口和封闭的底部,元素只能先入后出,底部元素所在的位置叫做栈底,顶部元素所在的位置叫做栈顶。栈这种元素,既可用数组实现,也可用链表实现

栈的基本操作就是:入栈、出栈两种入栈:把新元素放入栈,只允许从栈顶一侧放入元素,新元素的位置会成为新的栈顶出栈:把元素从栈里取出,只有栈顶元素才能被取出,出栈元素的前一个元素的位置会成为新的栈顶列表的append方法相当于入栈,pop方法相当于出栈,列表来实现栈栈,适用于对历史的回溯,例如实现递归,可以回溯方法的调用链。最著名的应用场景是面包屑导航,让用户在浏览页面的时候,可以轻松回溯到上一级或者更上一级的页面

入栈和出栈都只影响一个元素,不涉及其他元素的移动,时间复杂度都是O(1)

1.4)队列

类似于单行的隧道,先驶入的车辆先出,后驶入的车辆后出,先入先出,必须按照驶入的顺讯进出

队列的操作:入队、出队队列的出口端叫做队头,是头部元素的位置
队列的入口端叫做队尾,是尾部元素的下一个位置(空着的)入队:只允许在队尾放入新的元素,新元素的下一个位置将会成为新的队尾
出队:只允许在队头一侧移出元素,出队元素的后一个位置将会成为新的队头队尾指针指向的位置永远空出一位,所以队列最大容量比数组长度小1循环队列,利用已出的队元素空出的空间,让队尾指针重新指回数组的首位,在物理存储空间上,队尾的位置也可以在队头之前队列的应用场景:队列的输出顺序和输入顺序相同,所以队列通常用于对历史的回放,也就是按照历史重演一遍例如在多线程中,争夺公平锁的等待队列,就是按照访问顺讯来决定线程在队列中的次序。再如:网络爬虫实现网站抓取时,也是把待抓取的网站URL存入队列中,再按照存入队列的顺序来依次抓取和解析的

入队和出队的时间复杂度,都是O(1)

特殊的队列1、双端队列综合了栈和队列的优点,可以先入先出,也可以先入后出。
从队头一端可以入队或出队,从队尾一端可以入队或出队2、优先队列并不遵循先入先出,而是谁的优先级高,谁先出队。
优先队列不属于线性结构了,是基于二叉堆来实现的。
1.5)哈希表 

哈希表也叫散列表,提供了键和值的映射关系,只要给出一个key,就可以高效查找到它匹配的value,时间复杂度接近O(1)。哈希表也叫散列表,本质上相当于一个数组。在python中,哈希表对应的集合叫做字典。

在面向对象语言中,每个对象都有属于自己的哈希值,无论对象自身的变量类型是什么,他们的哈希值都是一个整数型变量。

哈希表可以说是列表和链表的结合

java中的哈希表采用了链表法,也就是hashMap,python中采用的是开放寻址法,也就是字典,dic

哈希表是两个操作读:通过给定的key,在哈希表中查找对应的value.先用过哈希函数,把key转化成数组下标,找到数组下标对应的元素写:在哈希表插入新的键值对,不同的key通过哈希函数获得数组下标,然后在键值对这个实体里存入数组下标对应的位置哈希表通过哈希函数,实现key和数组下标的转换,通过开发寻址法和链表来解决哈希冲突

2)树

例如:二叉树、以及衍生出来的二叉堆

3)图

多对对的关联关系

4)其他数据结构

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

《⼆叉搜索树》

《⼆叉搜索树》 1. ⼆叉搜索树的概念2. ⼆叉搜索树的性能分析3 二叉树的功能说明及实现3.1 ⼆叉搜索树的插⼊3.2 ⼆叉搜索树的查找3.3 ⼆叉搜索树的删除 4二叉搜索树的实现代码5 ⼆叉搜索树key和key/value使⽤场景5.1 key搜索场景&#xff1a;5.2 key/value搜索场景&#xff1a…

stm32 踩坑笔记

串口问题&#xff1a; 问题&#xff1a;会改变接收缓冲的下一个字节 串口的初始化如下&#xff0c;位长度选择了9位。因为要奇偶校验&#xff0c;要选择9位。但是接收有用数据只用到1个字节。 问题原因&#xff1a; 所以串口接收时会把下一个数据更改

卫星授时服务器,单北斗授时服务器,北斗卫星时钟服务器

当前NTP授时服务器已经实现内部的元器件及芯片实现采用国产化&#xff0c;已经证明了国产产品已经摆脱需要依靠进口元器件及芯片才能实现的产品研发、也证明了大国崛起。下来我们来分析下国产化服务器具备的优势。 1、采用国产操作系统&#xff1a;使用国产化系统Linux更加可靠…

Windows11免密码自动登录

按winR&#xff0c;打开运行&#xff0c;输入Control Userpasswords2&#xff0c;打开用户账户。 打开该设置&#xff0c;取消选中该选项&#xff0c;点击应用&#xff0c;输入想要自动登录的账户和密码&#xff0c;即可开机后自动登录Windows。 若此界面无该选项&#xff0c;…

C++使用开源ConcurrentQueue库处理自定义业务数据类

ConcurrentQueue开源库介绍 ConcurrentQueue是一个高性能的、线程安全的并发队列库。它旨在提供高效、无锁的数据结构&#xff0c;适用于多线程环境中的数据交换。concurrentqueue 支持多个生产者和多个消费者&#xff0c;并且提供了多种配置选项来优化性能和内存使用。 Conc…

中仕公考:2025年省考可以开始准备了!

“各省公务员考试”&#xff0c;是选拔和招录公务员的一种重要方式。该考试由各省级主管部门统一安排&#xff0c;编制归属于各个省份。 考试时间 各省的考试时间有所不同&#xff0c;但通常省联考的时间一般安排在3-5月之间。 户籍限制 部分岗位对考生的户籍有限制&#x…

保姆级教程,免费短链平台

神行短链 开源代码: https://github.com/EASTCATV/openShortLink.git 保姆级教程,5分钟打造属于自己的短链 免费短链平台 免费使用 短链生成 免费使用 地址: short.godsdo.com short.godsdo.com 打包命令 sbt clean && sbt packagedocker run -d \ --name shot…

三十六、Python基础语法(JSON操作)

JSON&#xff08;JavaScript Object Notation&#xff09;是一种基于文本&#xff0c;轻量级的数据交换格式。它易于人阅读和编写&#xff0c;同时也易于机器解析和生成&#xff0c;在自动化测试中经常用来存放测试数据。 JSON的特点&#xff1a; 基于文本&#xff0c;不包含图…

linux基础-完结(详讲补充)

linux基础-完结 一、Linux目录介绍 二、基础命令详细讲解 1. ls&#xff08;列出目录内容&#xff09; 2. cd&#xff08;更改目录&#xff09; 3. clear&#xff08;清除终端屏幕&#xff09; 4. pwd(显示你当前所在的目录) 5. vim(文本编辑器) 6. touch&#xff08;创…

【SAP】关于权限的继承

关于权限的父role和子role的权限继承&#xff0c;既可以 从子role主动去父role那里“取”。从父role“推”到子role 我自己之前一直用的是方法1&#xff0c;但由于子role很多&#xff0c;一个一个手工维护花了不少时间。 后来得知有方法2&#xff0c;特此测试。 我准备了父R…

信息安全数学基础(46)域和Galois理论

域详述 定义&#xff1a; 域是一个包含加法、减法、乘法和除法&#xff08;除数不为零&#xff09;的代数结构&#xff0c;其中加法和乘法满足交换律、结合律&#xff0c;并且乘法对加法满足分配律。同时&#xff0c;域中的元素&#xff08;通常称为数&#xff09;在加法和乘法…

时序约束进阶五:Set_Max_Delay与Set_Min_Delay详解

目录 一、背景 二、Max/Min_delay约束 2.1 约束设置参数 2.2 约束说明 三、场景说明 3.1 路径分段 3.1.1 无效的约束对象 3.1.2 设计代码 3.2 有效的约束对象 3.3 datapath only 3.3.1 工程设计 3.3.2 datapath only报告 3.4 clock group约束优先级 3.4.1 MAX/MIN…

搭建实验仪器知识库:从产品手册到智慧资源的飞跃

在科研、教学及工业生产领域&#xff0c;实验仪器作为探索未知、验证理论、提升效率的重要工具&#xff0c;其重要性不言而喻。然而&#xff0c;随着技术的不断进步和仪器的日益复杂化&#xff0c;如何高效、准确地使用这些仪器成为了科研人员、技术人员及学生面临的共同挑战。…

OA项目 python + vue3

准备工作 创建django项目 在setting.py进行数据库的配置&#xff1a; DATABASES {default: {ENGINE: django.db.backends.mysql,NAME: , #数据库名字USER: , #连接的数据库的用户名PASSWORD: ,HOST: 127.0.0.1,PORT: 3306,} }安装app&#xff1a; rest_framwork: 关闭csrf…

婚礼纪 9.5.57 | 解锁plus权益的全能结婚助手,一键生成结婚请柬

婚礼纪是一款结婚服务全能助手&#xff0c;深受9000万新人信赖的一站式结婚服务平台。解锁plus权益后&#xff0c;用户可以享受部分VIP会员功能。应用提供了丰富的结婚筹备工具和服务&#xff0c;包括一键生成结婚请柬、婚礼策划、婚纱摄影、婚宴预订等。婚礼纪旨在为新人提供全…

树形结构数据

树形结构数据 树形结构数据是一种基础且强大的数据结构&#xff0c;广泛应用于计算机科学和软件开发的各个领域。它模拟了自然界中树的层级关系&#xff0c;通过节点和它们之间的连接来组织数据。在本文中&#xff0c;我们将深入探讨树形结构数据的概念、特点、类型以及它们在…

洛古---越狱问题【快速幂】

今天和大家讲一个洛古的算法题&#xff0c;我觉得还是比较有含金量的&#xff0c;今天给大家分享一下 题目描述 监狱有 &#x1d45b;n个房间&#xff0c;每个房间关押一个犯人&#xff0c;有 &#x1d45a; 种宗教&#xff0c;每个犯人会信仰其中一种。如果相邻房间的犯人的宗…

【论文笔记】Parameter-Efficient Transfer Learning for NLP

&#x1f34e;个人主页&#xff1a;小嗷犬的个人主页 &#x1f34a;个人网站&#xff1a;小嗷犬的技术小站 &#x1f96d;个人信条&#xff1a;为天地立心&#xff0c;为生民立命&#xff0c;为往圣继绝学&#xff0c;为万世开太平。 基本信息 标题: Parameter-Efficient Tran…

《PyTorch深度学习快速入门教程》学习笔记(第20周)

目录 摘要 Abstract 1. 池化层原理 2. 二维池化层 3. 二维最大池化 4. 填充、步幅与多个通道 5. 平均池化层 6. 理论总结 7. 池化层处理数据 8. 池化层处理图片 摘要 本周报的目的在于汇报《PyTorch深度学习快速入门教程》课程第六周的学习成果&#xff0c;主要聚焦于…

C# 实现对指定句柄的窗口进行键盘输入的实现

在C#中实现对指定句柄的窗口进行键盘操作&#xff0c;可以通过多种方式来实现。以下是一篇详细的指南&#xff0c;介绍如何在C#中实现这一功能。 1. 使用Windows API函数 在C#中&#xff0c;我们可以通过P/Invoke调用Windows API来实现对指定窗口的键盘操作。以下是一些关键的…