2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】

本文涉及的产品
视觉智能开放平台,视频资源包5000点
视觉智能开放平台,分割抠图1万点
视觉智能开放平台,图像资源包5000点
简介: 数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】

欢迎各位彦祖与热巴畅游本人专栏与博客

你的三连是我最大的动力

以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]

专栏跑道一

➡️网络空间安全——全栈前沿技术持续深入学习

image.gif 编辑

专栏跑道二

➡️ 24 Network Security -LJS

image.gif 编辑

image.gif 编辑

image.gif 编辑

专栏跑道三


➡️ MYSQL REDIS Advance operation

image.gif 编辑

专栏跑道四

➡️HCIP;H3C-SE;CCIP——LJS[华为、华三、思科高级网络]

image.gif 编辑

专栏跑道五

➡️RHCE-LJS[Linux高端骚操作实战篇]

image.png

专栏跑道六

➡️数据结构与算法[考研+实际工作应用+C程序设计]

image.gif 编辑

专栏跑道七

➡️RHCSA-LJS[Linux初级及进阶骚技能]

image.gif 编辑

image.gif

上节回顾



 王道考研系列之数据结构与算法学习

第一章 数据结构绪论


image.gif 编辑 image.gif

1.1 数据结构的基本概念

  1. 数据:数据是信息的载体,符号的集合、所有能输入到计算机中并能被计算机程序处理的符号的集合,数据是计算机程序加工的原料。
  2. 数据元素:数据的基本单位,通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成。
  3. 数据项:构成数据元素的不可分割的最小单位。
  4. image.gif 编辑
  5. 数据对象:数据对象是具有相同性值的数据元素的集合,是数据的一个子集。
  6. 数据结构:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
  7. image.gif 编辑

举例说明

  1. 学校里的好多类型的表:数据
  2. 单独的一张成绩单表:数据对象
  3. 成绩单中每一行有姓名、课程、班级、成绩:数据元素
  4. 成绩单中每一行的每一个表格姓名等都是一个个的数据项

1.2 数据结构的三要素

image.gif 编辑

1.2.1. 数据的逻辑结构

image.gif 编辑

逻辑结构是指数据元素之间的逻辑关系,即从逻辑关系上描述数据。

逻辑结构包括

  1. 集合结构:结构中的数据元素之间除“同属一个集合”外,别无其它关系(例如:一群羊)。
  2. 线性结构:结构中的数据元素之间只存在一对一的关系,除了第一个元素,所有元素都有唯一前驱;除了最后一个元素,所有元素都有唯一后继(例如:排队取号)。
  3. 树形结构:结构中数据元素之间存在一对多的关系(例如:思维导图)。
  4. 图状结构:数据元素之间是多对多的关系(例如:道路信息)。

1.2.2. 数据的存储结构(物理结构)

如何用计算机表示数据元素的逻关系?

存储结构是指数据结构在计算机中的表示(又称映像),也称物理结构

存储结构包括:

  1. 顺序存储:把逻辑上相邻的元素存储在物理位置也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。
  2. 链式存储:逻辑上相邻的元素在物理位置上可以不相邻,借助指示元素存储地址的指针来表示元素之间的逻辑关系。
  3. 索引存储:在存储元素信息的同时,还建立附加的索引表,索引表中的每项称为索引项,索引项的一般形式是(关键字,地址)。
  4. 散列存储:根据元素的关键字直接计算出该元素的存储地址,又称哈希(Hash)存储。

1.2.3. 数据的运算

  • 数据上的运算包括运算的定义和实现。
  • 运算的定义是针对逻辑结构指出运算的功能。
  • 运算的实现是针对存储结构的,指出运算的具体操作步骤。

针对于某种逻辑结构,结合实际需求,定义基本运算。

例如:逻辑结构->线性结构

基本运算:
1.查找第i个数据元素
2.在第i个位置插入新的数据元素
3.删除第i个位置的数据元素......
image.gif

1.2.4. 数据类型和抽线数据类型

image.gif 编辑

数据类型是一个值的集合和定义在此集合上的一组操作的总称。例如:定义int整形,我们就可以把他们加减乘除等操作。

  1. 原子类型。其值不可再分的数据类型。如bool 和int 类型
  2. 结构类型。其值可以再分解为若干成分(分量)的数据类型(例如:结构体)。

抽象数据类型(Abstract Data Type,ADT)是抽象数据组织及与之相关的操作。ADT 用数学化的语言定义数据的逻辑结构、定义运算。与具体的实现无关

在探讨数据结构时我们需要理解几点:

  1. 定义逻辑结构(数据元素之间的关系)
  2. 定义数据的运算(针对现实需求应该对这种逻辑结构进行什么样的运算)
  3. 确定某种存储结构,实现数据结构,并实现一些对数据结构的基本运算

1.3 算法的基本概念

image.gif

算法简介

程序 = 数据结构+算法

数据结构:如何用数据正确地描述现实世界的问题,并存入计算机。

算法:如何高效地处理这些数据,以解决实际问题

算法(Algorithm)是对特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作。

算法的特性:

算法的特性

有穷性 一个算法必须总在执行有穷步之后结束,且每一步都可在有穷时间内完成
确定性 算法中每条指令必须有确定的含义,对于相同的输入只能得到相同的输出
可行性 算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现
输入 一个算法有零个或多个输入,这些输入取自于某个特定的对象的集合
输出 一个算法有一个多个输出,这些输出是与输入有着某种特定关系的量

举例说明:

我们可以类比:y = f(x)函数,其中x就是输出,y就是输出,这个函数就是算法。

优质的算法应该达到的目标:

优质的算法应该达到的目标

正确性 算法应能够正确的求解问题
可读性 算法应具有良好的可读性,以帮助人们理解
健壮性 输入非法数据时,算法能适当地做出反应或进行处理,而不会产生莫名奇妙地输出结果。
效率与低存储量需求 花的时间少即:时间复杂度低。不费内存即:空间复杂度低

1.4 算法的时间复杂度

image.gif

  1. 顺序执行的代码只会影响常数项,可以忽略。
  2. 只需挑循环中的一个基本操作分析它的执行次数与 n 的关系即可。
  3. 如果有多层嵌套循环只需关注最深层循环循环了几次。
  • 事前预估算法时间开销T(n)与问题规模 n 的关系 (T 表示“time“)
  • image.gif 编辑
  • image.gif 编辑
  • 一般情况下我们只看一个算法的最坏时间复杂度和平均时间复杂度
  • 如何计算 :找到一个基本操作(最深层循环)

1.5 算法的空间复杂度

image.gif 编辑

  • image.gif 编辑
  • 开一个与问题规模n有关的一维数组

函数递归调用带来的内存开销

  • 空间复杂度 与 递归调用的深度 有关
  • 指算法消耗的存储空间(即算法除本身所需存储外的辅助空间)
  • 算法的空间复杂度S(n)定义为该算法所耗费的存储空间,它是问题规模n的函数。
    记为S(n)=O(g(n))
  • image.gif 编辑

第一章归纳总结:

1. 循环中变量参与循环条件的判断

思路:找出基本运算执行次数 image.gif 编辑与问题规模 image.gif 编辑的关系,解得 image.gif 编辑 image.gif 编辑最高幂次为 image.gif 编辑,则算法时间复杂度为 image.gif 编辑

1.    int i = 1;                              2.    int y = 5;                 
      while(i <= n)                                 while((y+1)*(y+1)<n)
          i = i * 2;                                    y = y + 1;
image.gif

例1:设基本运算 image.gif 编辑执行次数为 image.gif 编辑,则 image.gif 编辑,解得 image.gif 编辑,则 image.gif 编辑

例2:设基本运算 image.gif 编辑执行次数为 image.gif 编辑,则 image.gif 编辑 (此处的y是指最终y的值,由于初始时y=5,所以最终y的值减去5才是基本运算的执行次数)。那么 image.gif 编辑

化简可得 image.gif 编辑,则 image.gif 编辑

2.循环中变量与循环条件无关

思路:数学归纳法 或 直接累计循环次数。(如1.2.3中的16)

🌷递归:公式递推           image.gif 编辑,即 image.gif 编辑

🌷非递归:直接累计次数

  • 课后习题精选
  • 一、单选
  • 01
  • 可以用()定义一个完整的数据结构。
  • A. 数据元素        B. 数据对象        C. 数据关系        D. 抽象数据类型
  • 03
  • 以下属于逻辑结构的是()。
  • A. 顺序表        B. 哈希表        C. 有序表        D. 单链表
  • 二、应用
  • 01
  • 对于两种不同的数据结构,逻辑结构或物理结构一定不相同吗?
  • 02
  • 试举一例,说明对相同的逻辑结构,同一种运算在不同的存储方式下实现时,其运算效率不同。
  • 1.2.3 习题
  • 一、单选
  • 03
  • 若某算法的空间复杂度为O(1),则表示该算法()。
  • A. 不需要任何辅助空间        B. 所需辅助空间大小与问题规模n无关
  • C. 不需要任何空间               D. 所需空间大小与问题规模n无关
  • 16
  • 下列程序段的时间复杂度是()。
int sum = 0;
for(int i = 1; i < n; i *= 2)
    for(int j = 0; j < i; ++j)
        sum++;
A. O(logn)        B. O(n)        C. O(nlogn)        D. O(n^2)
  • image.gif

  • 1.1.3 习题答案及解析
  • 一、单选
  • 01
  • ✅答案:D. 抽象数据类型
  • 💡解析:
  • 数据结构三要素:逻辑结构、存储结构、数据的运算。
  • 数据结构是相互之间具有一种 或 多种特定关系的数据元素的集合。
  • A. 数据元素:数据的基本单位
  • B. 数据对象:具有相同性质的数据元素的集合
  • C. 数据关系:即结构(数据元素相互之间的关系)
  • D. 抽象数据类型:一个数学模型 及 定义在该模型上的一组操作
  • 抽象数据类型(ADT)描述了数据的逻辑结构和抽象运算,通常用(数据对象,数据关系,基本操作集)这样的三元组来表示,从而可构成完整的数据结构定义。
  • 03
  • ✅答案:C. 有序表
  • 💡解析:
  • 顺序表、链表属于一般线性表;线性表、有序表是逻辑结构;顺序表,链表是存储结构
  • A. 顺序表是线性表的顺序存储、D. 单链表是线性表的链式存储
  • B. 哈希表(散列表)是基于哈希函数将数据映射到索引,使得增、删、查具有平均O(1)复杂度。
  • 哈希表本质上是数组加链表,不属于线性结构。
  • 顺序表、哈希表、单链表是三种不同的数据结构,既描述逻辑结构,又描述存储结构和数据运算。
  • 对于C. 有序表是指关键字有序的线性表,仅说明了数据元素之间的逻辑关系。
  • 二、应用
  • 01
  • ✅答案:
  • 数据结构三要素:逻辑结构、存储结构(物理结构)、数据的运算。
  • 当数据结构不同时,也有可能是数据的运算不同。
  • 例如,对于二叉树 和 二叉排序树,二叉排序树可以采用二叉树的逻辑表示和存储方式,虽然它们均有建立树、查找结点、插入结点、删除结点等操作,但是实际的定义是不同的,二叉树平均复杂度为O(n),而二叉排序树的平均时间复杂度为O(logn)。
  • 二叉排序树讲解
  • 02
  • ✅答案:
  • 例如,线性表可以采用顺序存储和链式存储。
  • 在顺序存储下,线性表插入、删除操作的时间复杂度为O(n);
  • 在链式存储下,线性表插入、删除操作的时间复杂度为O(1)。
  • 1.2.3 习题答案及解析
  • 一、单选
  • 03
  • ✅答案:B. 所需辅助空间大小与问题规模n无关
  • 💡解析:
  • 空间复杂度为算法所需的存储空间,
  • 若输入数据所占的空间只取决于问题本身,与算法无关,则只需分析辅助空间。
  • 16
  • ✅答案:B. O(n)
  • 💡解析:
  • 设最外层循环执行了次,则,化简可得。
  • 内层循环执行次数,则。
  • 那么f(n) = n,即时间复杂度T(n) = O(f(n)) = O(n)。

  • 思维扩展
  • 求解斐波那契数列
  • image.gif 编辑
  • 有递归、非递归算法。试分别分析两种算法的时间复杂度。

  • ✅答案:(1)递归: image.gif 编辑        (2)非递归: image.gif 编辑
  • 💡解析:
  • (1)递归
void F(n){
    if(n <= 1) return n;
    return F(n - 1) + F(n - 2);
}
  • image.gif
  • 从上述递归形式不难发现,每次会形成两个分支,最终形成递归二叉树,则时间复杂度约为 image.gif 编辑
  • 实际上时间复杂度为 image.gif 编辑。【斐波那契数列通项公式】
























相关文章
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
存储 固态存储 程序员
考研计算机组成原理总结(5)
考研计算机组成原理总结(5)
753 0
|
存储 算法 调度
【考研必备】解开“黑匣子”的神秘面纱,透视数字世界底层实现过程(计算机组成原理)(下)
【考研必备】解开“黑匣子”的神秘面纱,透视数字世界底层实现过程(计算机组成原理)
|
6月前
|
存储 知识图谱
【计算机组成原理】指令系统&考研真题详解之拓展操作码!
也就是说 “其中三地址指令29”条这句话,完全可以翻译成“三地址这种类型的指令一共能有29种不同的可能性” 这样说就清晰多 因为这就意味着 我们需要用若干个字节 来表示这29种不同的可能性 然后又已知每一个字节位能表示的可能性是2种(0/1),那么我们想有多少个字节可以表示29种不同的可能呢?最少5种 (因为2的4次方=16<29),2^5=32>29,也就是说有32-29=3种可能性是不在三地址指令这种类型的指令集里面的,所以这3 种余出来的可能性要被利用 就在下一种 “二地址指令集”中利用到
98 0
|
6月前
计算机网络——物理层相关习题(计算机专业考研全国统考历年真题)
计算机网络——物理层相关习题(计算机专业考研全国统考历年真题)
51 0
|
存储 安全 网络安全
【考研必备二】解开“黑匣子”的神秘面纱,透视数字世界底层实现过程(计算机组成原理)(下)
【考研必备二】解开“黑匣子”的神秘面纱,透视数字世界底层实现过程(计算机组成原理)
|
存储 Unix Linux
【考研必备二】解开“黑匣子”的神秘面纱,透视数字世界底层实现过程(计算机组成原理)(上)
【考研必备二】解开“黑匣子”的神秘面纱,透视数字世界底层实现过程(计算机组成原理)(上)
【考研必备二】解开“黑匣子”的神秘面纱,透视数字世界底层实现过程(计算机组成原理)(上)
|
存储 机器学习/深度学习 Unix
【考研必备】解开“黑匣子”的神秘面纱,透视数字世界底层实现过程(计算机组成原理)(上)
【考研必备】解开“黑匣子”的神秘面纱,透视数字世界底层实现过程(计算机组成原理)
【考研必备】解开“黑匣子”的神秘面纱,透视数字世界底层实现过程(计算机组成原理)(上)

热门文章

最新文章