【全面突击数据结构与算法001】绪论篇,数据结构的基本概念

🍁前言

👑:👉CSDN丨博客园

🏆:👉在下周周ovoの社区

💎全栏:👉数据结构与算法专栏

PS:本篇文章主要综合了【王道数据结构与算法】与我的个人笔记与理解,如果文章有任何错误欢迎各位大佬的指出

快期末考试了,复习一波,冲冲冲

文章目录

🍁前言

🍁一、基本概念和术语

💎1.1、数据

💎1.2、数据元素、数据项

💎1.3、数据对象、数据类型、数据结构

​编辑

🍁二、数据结构的三要素

💎2.1、数据的逻辑结构

💎2.2、数据的存储结构

💎2.3、数据的运算

🍁三、 算法和算法的评价

💎3.1、算法的基本概念

​编辑

💎3.2、算法效率的度量

⚡3.2.1、时间复杂度

​编辑

⚡3.2.2、空间复杂度


🍁一、基本概念和术语

💎1.1、数据

数据是指事实、信息或知识等在计算机中的表现形式,是一种离散的、数字化的描述。数据通常以二进制形式存储在计算机的内存或硬盘中,它们可以被计算机程序读取、处理和操作,从而实现各种功能和应用。在计算机科学中,数据是非常重要的基础概念,其在各种应用领域中都有广泛的应用。

💎1.2、数据元素、数据项

数据元素是指数据的基本单位,通常是指一个整体。而数据项则是数据元素中的一个个体,通常是数据元素中最小的单元。因此,数据元素由若干个数据项组成。

例如:

以一个学生信息的数据结构为例,一个学生的信息就是一个数据元素,它包含了学生的姓名、学号、年龄等多个数据项,每个数据项分别表示学生的不同属性。因此,可以说数据项是数据元素的组成部分,而数据元素则是数据项的集合。

💎1.3、数据对象、数据类型、数据结构

数据对象:是指计算机中用来表示某种事物的实体,可以是具体的实物或抽象的概念。在计算机中,数据对象通常以数据元素的形式出现,一个数据对象由若干个数据元素组成。在一个学生信息管理系统中,一个学生就是一个数据对象,包含了学生的姓名、学号、年龄等多个属性,每个属性都可以看作是一个数据元素。

数据类型:数据类型是对数据对象的一种分类,是计算机科学中一个重要的概念。不同类型的数据对象在计算机内部需要不同的存储方式和处理方法。例如,整数、浮点数、字符串等都是不同的数据类型。

数据结构:是指计算机中存储和组织数据的方式,是一种数据类型的具体实现。数据结构可以通过不同的方式来表示数据对象,包括数组、链表、树等。不同的数据结构在计算机内部的存储方式和操作方法也不同,可以根据实际需要来选择合适的数据结构。

🍁二、数据结构的三要素

💎2.1、数据的逻辑结构

数据的逻辑结构指的是数据元素之间的关系,是数据在逻辑上的组织方式。它与数据的物理结构是不同的,物理结构指的是数据在计算机内部的存储方式。

常见的数据逻辑结构包括:

1. 线性结构:数据元素之间呈线性关系,每个数据元素只有一个直接前驱和一个直接后继。例如,线性表、栈、队列等数据结构都是线性结构。

2. 非线性结构:数据元素之间呈非线性关系,每个数据元素可能有多个直接前驱或直接后继。例如,树、图等数据结构都是非线性结构。

3. 集合结构:数据元素之间没有任何关系,它们之间是独立的。例如,数组就是一种集合结构。

4. 文件结构:数据元素之间存在某种关联关系,通常是通过某个共同的特征来关联。例如,数据库中的关系型数据就是一种文件结构。

5、树形结构:结构中的数据元素存在一对多的情况

6.图形结构或网状结构:结构中的数据元素存在多对多的情况

在实际应用中,根据问题的特点和需求,选择合适的数据逻辑结构是非常重要的,它能够直接影响数据处理的效率和正确性。

💎2.2、数据的存储结构

数据的存储结构是指在计算机内部,数据在存储介质中的具体存储方式,可以分为以下几种常见的存储结构:

1. 顺序存储结构:数据元素按照其逻辑顺序在存储介质上连续存储,可以通过元素在存储介质上的物理位置来访问元素。顺序存储结构通常用于存储连续的数据,如数组和线性表等。

2. 链式存储结构:数据元素在存储介质上不连续,每个元素保存着下一个元素的地址,通过遍历链表中的元素来访问链表。链式存储结构通常用于存储不连续的数据,如链表、树和图等。

3. 索引存储结构:数据元素分别存储在存储介质的不同位置,通过索引表来访问这些元素,索引表中保存着每个元素在存储介质中的位置。索引存储结构通常用于数据元素较大或数据元素的数量较大的情况。

4. 散列存储结构数据元素存储在散列表中,每个元素对应一个关键字,通过哈希函数将关键字映射为元素在散列表中的地址,从而实现对元素的访问。散列存储结构通常用于实现快速的数据查找和插入操作,如哈希表等。

💎2.3、数据的运算

数据的运算是指对数据进行的各种操作,包括查找、排序、插入、删除、修改等。不同的数据结构支持不同的数据运算,数据运算也是数据结构的最终目的之一。

以下是常见的几种数据运算:

1. 查找:在数据集合中查找指定元素的位置或者判断该元素是否存在。常见的查找算法有线性查找、二分查找、哈希查找等。

2. 排序:将数据集合按照一定的规则排序,使其按照某种顺序排列。常见的排序算法有冒泡排序、快速排序、归并排序等。

3. 插入:将一个元素插入到数据集合中的指定位置。常见的插入算法有直接插入排序、折半插入排序、希尔排序等。

4. 删除:将数据集合中指定位置的元素删除。常见的删除算法有直接删除、移动删除、标记删除等。

5. 修改:修改数据集合中指定位置的元素。例如,修改一个学生的成绩或者修改一个商品的价格等。

🍁三、 算法和算法的评价

💎3.1、算法的基本概念

算法是指解决特定问题的一系列清晰而有限的指令集合,它描述了一个计算过程,能够把一个初始状态转变成所需的最终状态。算法可以用来求解各种问题,例如排序、搜索、最短路径等。

算法具有以下几个基本概念:

1. 有限性:算法必须在有限步内结束,不能无限循环或递归

2. 确定性:算法的每一步必须明确而无歧义,执行结果唯一

3. 可行性:算法必须能够在计算机或者其他可执行设备上实现。

4. 输入:算法需要接受输入数据,这些数据可能是预处理的、用户输入的或者从其他系统获取的。

5. 输出:算法必须产生输出结果,这些结果可能是打印、显示、存储等形式。

6. 无误性:算法必须能够正确地解决问题,无论输入数据是什么,都能够得到正确的结果。

算法是计算机科学中的核心概念之一,是计算机程序设计的基础。

好的算法应该考虑达到下面这几个目标:

1. 正确性(Correctness):算法应该能够正确地解决问题,无论输入数据是什么,都能够得到正确的结果。

2. 可读性(Readability):算法应该易于理解和阅读,便于他人理解和维护。代码应该注重命名、缩进、注释等方面的规范化和可读性。

3. 高效性(Efficiency):算法应该具有高效的执行速度和内存占用,能够在可接受的时间内完成运算。

4. 健壮性(Robustness):算法应该能够在各种不同情况下都能够正确地运行,避免因异常或无效输入导致程序崩溃或出现错误。

5. 可扩展性(Scalability):算法应该能够适应不同规模和复杂度的问题,随着数据规模增大而不失效率。

这些目标是设计和实现好的算法时需要考虑的关键因素。一个好的算法应该能够在正确性、可读性、高效性、健壮性和可扩展性等方面达到一个良好的平衡,从而满足问题需求并提高程序的性能和可靠性。

💎3.2、算法效率的度量

算法效率的度量通常使用时间复杂度和空间复杂度来描述。

特别注意:

在算法设计中,原地工作(in-place)指的是一种特殊的算法实现方式,它能够在不使用额外的辅助空间(除了常数大小的辅助空间)的情况下,在原始数据上进行计算和修改。

如果一个算法被称为是“原地工作”的,只有该算法只使用了与输入数据规模无关的额外辅助空间。这种算法实现方式可以有效地减少空间复杂度,并且避免不必要的空间浪费,特别适用于在嵌入式系统和其他资源受限环境中的应用场景。

但是、并非所有的算法都可以或者需要原地工作。某些问题可能需要构造新的数据结构,而不得不使用额外的辅助空间,才能更加高效地解决问题。因此,在选择算法实现方式时,需要综合考虑时间复杂度、空间复杂度、实际应用场景等多个方面的因素。

总结下:原地工作是一种重要的算法设计思想,它可以帮助我们优化算法性能和节约资源开销。

⚡3.2.1、时间复杂度

时间复杂度是用来描述算法执行时间与输入规模之间关系的度量,它是指算法的运行时间随着问题规模的增加而增加的速度。在进行算法分析时,我们通常关注最坏情况下的时间复杂度,即算法在最坏情况下执行所需的最长时间。

时间复杂度通常用大 O 记号来表示,记为 O(f(n)),其中 n 表示输入规模,f(n) 是一个随着 n 增大而增加的函数。O 表示算法的时间复杂度,f(n) 表示随着输入规模 n 的增大,算法所需要的计算量也随之增加,但增加的速度最终被 f(n) 控制。

举个栗子:

若一个算法的时间复杂度为 O(n),则表示当输入规模 n 增大时,该算法执行所需的计算量随之线性增长。如果输入规模增加一倍,那么算法执行所需的时间也会增加一倍

若算法的时间复杂度为 O(n^2),则表示该算法执行所需的计算量随着输入规模的平方级别增加,如果输入规模增加一倍,那么算法执行所需的时间就会增加四倍。

时间复杂度是衡量算法效率的重要指标,一般来说,时间复杂度越小的算法效率越高。但在实际应用中,我们还需要考虑空间复杂度、代码的可读性和可维护性等因素来综合评估算法的优劣。

例子:

 

 重点部分:

⚡3.2.2、空间复杂度

空间复杂度是指算法在执行过程中需要占用的内存空间大小,通常用数据占用的存储单元数量来表示。和时间复杂度一样,空间复杂度也是衡量算法效率的一个重要指标。

空间复杂度的计算方法与时间复杂度类似,都是通过分析算法执行过程中所需的存储空间与输入规模之间的关系来确定的。我们通常关注的是算法在最坏情况下的空间复杂度,即算法在存储最多数据时所需的最大存储空间。

空间复杂度也通常用大 O 记号来表示,记为 O(f(n)),其中 n 表示输入规模,f(n) 是一个随着 n 增大而增加的函数。与时间复杂度类似,空间复杂度越小的算法所占用的内存空间越少,效率越高。

需要注意的是,在实际应用中,我们往往需要在时间复杂度和空间复杂度之间进行权衡,找到一个平衡点来满足实际需求。有些算法可能时间复杂度比较高,但空间复杂度比较低;有些算法则相反。因此,我们需要根据具体问题的特点来选择合适的算法。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

机器学习——线性回归篇

基本概念 什么是回归预测?什么是分类预测? 模型输入变量预测结果应用回归预测实值离散一个连续值域上的任意值预测值的分布情况分类预测实值离散两个或多个分类值将输入变量分类到不同类别 思考一个问题:分类问题是否可以转变为回归问题&am…

R:GAM非线性回归曲线拟合与散点密度图绘制

作者:CSDN @ _养乐多_ 本文将介绍使用R语言以及GAM模型,绘制回归曲线和散点密度图。 文章目录 一、R语言脚本二、色带一、R语言脚本 install.packages("ggpointdensity") install.packages("ggplot2") insta

问题解决:cmd中创建文件夹被拒绝访问。

问题: 在cmd中准备创建一个B盘node.js文件夹下的一个node_global文件被拒绝访问出错。 Microsoft Windows [版本 10.0.19045.2965] (c) Microsoft Corporation。保留所有权利。C:\Users\SueMagic>md B:\nodejs\node_global 拒绝访问。C:\Users\SueMagic>原因…

【分享】科大讯飞星火认知大模型(初体验)

前言: 哈喽,大家好,我是木易巷~ 随着人工智能技术的迅猛发展,自然语言处理(NLP)成为了热门话题。在众多NLP模型中,科大讯飞星火认知大模型成为了一个备受瞩目的新秀,今天我们来了解…

【MySQL】MySQL的事务原理和实现?

文章目录 MySQL事务的底层实现原理一、事务的目的可靠性和并发处理 二、实现事务功能的三个技术2.1 redo log 与 undo log介绍2.1.1 redo log2.1.2undo log 2.2 mysql锁技术2.2.1 mysql锁技术 2.3 MVCC基础 三、事务的实现3.1 原子性的实现3.1.1 undo log 的生成3.1.2 根据undo…

书单 | IPD的12本书

随着IPD(集成产品开发)在IBM、华为等企业取得了巨大的成功,IPD逐渐被人们所知晓。诸多实践证明,IPD既是一种先进思想,也是一种卓越的产品开发模式,随着人们对IPD认识和探索,未来将会被应用到更多…

Window的创建

Window的创建 上一篇说到了Window和WindowManager的关系并且讲述了WindowManager如何添加Window与Window内部的三个方法的实现 这篇主要讲几个常见的Window的创建比如Activity,Dialog和Toast 其中Activity属于应用Window Dialog属于子Window Toast属于系统Window z-order…

git工作流实践

常见分支命名 远程仓库的分支:主干分支master, 开发分支dev,发布分支release 个人开发分支:特性分支feature, 缺陷修改分支bugfix, 热更新分支 hotfix 一般工作流如下 创建个人本地开发分支: git checkout -b feat…

springboot+vue+elementui计算机专业课程选课管理系统vue

本系统的主要任务就是负责对学生选课。主要用户为老师、学生,其中,学生可对自己的信息进行查询,可以进行选课,也可以进行删除已选课程,教师可对学生和课程的信息进行查询,教师拥有所有的权限,可以添加删除学生信息。系统提供界面,操作简单。 为实现这些功能,系统一个…

JAVA之数组2

添加元素 从后往前进行迭代,最后在末尾插入元素 tip:为避免数字在覆盖过程中丢失,故从后往前覆盖 删除元素 从前往后迭代,最后将末尾赋值为0 tip: 以覆盖的数arr【i】为基准,构造循环 共同处Tip: 范围均为【index1&…

【网络协议详解】——DHCP系统协议(学习笔记)

目录 🕒 1. DHCP概述🕒 2. 工作过程🕒 3. DHCP的报文格式🕒 4. DHCP中继代理🕒 5. 实验:DHCP配置 🕒 1. DHCP概述 动态主机配置协议DHCP(Dynamic Host Configuration Protocol&…

SpringCloudAlibaba整合分布式事务Seata

文章目录 1 整合分布式事务Seata1.1 环境搭建1.1.1 Nacos搭建1.1.2 Seata搭建 1.2 项目搭建1.2.1 项目示意1.2.2 pom.xml1.2.2.1 alibaba-demo模块1.2.2.2 call模块1.2.2.3 order模块1.2.2.4 common模块 1.2.3 配置文件1.2.3.1 order模块1.2.3.2 call模块 1.2.4 OpenFeign调用1…

【C++】容器篇(四)—— queue的基本介绍以及模拟实现

前言: 在上期博文中我带大家对stack进行深入的学习,本期我将带领学习的是关于 queue的基本知识,并且还将给大家介绍并实现 priority_queue。接下来,让我们正式本期的内容。 目录 (一)queue的基本介绍 &…

Eclipse教程 Ⅵ

今天分享Eclipse Java 构建路径、Eclipse 运行配置(Run Configuration)和Eclipse 运行程序 Eclipse Java 构建路径 设置 Java 构建路径 Java构建路径用于在编译Java项目时找到依赖的类,包括以下几项: 源码包项目相关的 jar 包及类文件项目引用的的类…

83.响应式设计原则

什么是响应式设计? ● 使网页根据任何可能的屏幕尺寸(窗口或视口尺寸)调整其布局和视觉风格的设计技术。 ● 在实践中,这意味着响应式设计使网站可以在所有设备上使用,如台式电脑、平板电脑和手机。 ● 这是一套做法&…

LearnOpenGL-高级OpenGL-9.几何着色器

本人初学者,文中定有代码、术语等错误,欢迎指正 文章目录 几何着色器使用几何着色器造几个房子爆破物体法向量可视化 几何着色器 简介 在顶点和片段着色器之间有一个可选的几何着色器几何着色器的输入是一个图元(如点或三角形)的一…

Spark入门介绍

目录 一、Spark框架概述 1、Spark简介 2、发展 二、Spark功能及特点 1、定义

K8s进阶7——Sysdig、Falco、审计日志

文章目录 一、分析容器系统调用:Sysdig1.1. 安装1.2 常用参数1.3 采集分析1.4 示例1.4.1 查看某进程系统调用事件1.4.2 查看建立TCP连接事件1.4.3 查看某目录下打开的文件描述符1.4.4 查看容器的系统调用 1.5 Chisels工具1.5.1 网络类1.5.2 硬盘类1.5.3 cpu类1.5.4 …

奇舞周刊第493期:Hook 革命!浅谈 React 新 Hook 的未来与思想

关注前端生态发展,了解行业动向。 下面先一起看下本期周刊 摘要 吧~ 奇舞推荐 ■ ■ ■ Hook 革命!浅谈 React 新 Hook 的未来与思想 作者阳羡曾写文章对 React 新 Hook use 的设计理念和限制进行了深入分析,并提供了一个可能的实现来帮助读者…

如何在 Alpine Linux 上启用或禁用防火墙?

防火墙是计算机网络安全的重要组成部分,它用于保护计算机和网络免受未经授权的访问和恶意攻击。Alpine Linux 是一种轻量级的 Linux 发行版,常用于构建容器化应用和嵌入式系统。本文将详细介绍如何在 Alpine Linux 上启用或禁用防火墙。步骤 1&#xff1…