当前位置：首页 > 科技 > 软件

数据结构与算法（DSA）基础篇

来源：责编：时间：2023-10-30 09:06:54 232观看

导读什么是 DSA？DSA（Data Structures and Algorithms）。在计算机科学的背景下，术语 DSA 代表数据结构和算法。数据结构与算法简介（DSA）什么是数据结构？数据结构被定义为在我们的设备中存储和组织数据以高效且有效地使用数据的特

什么是 DSA？

DSA（Data Structures and Algorithms）。

在计算机科学的背景下，术语 DSA 代表数据结构和算法。

数据结构与算法简介（DSA）

什么是数据结构？

数据结构被定义为在我们的设备中存储和组织数据以高效且有效地使用数据的特定方式。使用数据结构背后的主要思想是最小化时间和空间复杂性。高效的数据结构占用最少的内存空间并需要最少的时间来执行数据。

什么是算法？

算法被定义为一个过程或一组定义明确的指令，通常用于解决一组特定的问题或执行特定类型的计算。简单来说，就是为了执行任务而按步骤的方式进行的一组操作。

认识DSA

时间和空间复杂性

这是一个有趣且重要的话题。使用 DSA 的主要动机是有效且高效地解决问题。如何判断自己编写的程序是否高效？这是通过复杂性来衡量的。复杂性有两种类型：

时间复杂度：时间复杂度用于衡量执行代码所需的时间量。
空间复杂度：空间复杂度是指成功执行代码功能所需的空间量。

上述两种复杂性都是根据输入参数来测量的。但这里出现了一个问题。执行代码所需的时间取决于几个因素，例如：

程序中执行的操作数量。
以及设备的速度。
在平台执行时数据传输的速度。

以下3种渐近符号主要用于表示算法的时间复杂度：

Big-O 表示法 (Ο) – Big-O 表示法专门描述了最坏的情况。
Omega 表示法 (Ω) – Omega(Ω) 表示法专门描述了最佳情况。
Theta 表示法 (θ) – 该表示法表示算法的平均复杂度。

算法的增长率

PS：横坐标：输入数据的大小；纵坐标：执行的完成时间。

代码分析中最常用的表示法是Big O 表示法，它给出了代码运行时间的上限（或输入大小方面使用的内存量）。

数据结构

数组（Array）

最基本但重要的数据结构是数组。它是一种线性数据结构。数组是同类数据类型的集合，其中元素被分配连续的内存。由于内存的连续分配，数组的任何元素都可以在恒定时间内访问。每个数组元素都有一个对应的索引号。

数组数据结构

链表（Linked Lists）

和上面的数据结构一样，链表也是一种线性数据结构。但Linked List在配置上与Array不同。它没有分配到连续的内存位置。相反，链表的每个节点都被分配到一些随机内存空间，并且前一个节点维护一个指向该节点的指针。因此任何节点都不可能直接访问内存，而且它也是动态的，即链表的大小可以随时调整。

链表数据结构

链表的不同实现：

单向链表– 链表中的每个节点仅指向其下一个节点。
循环链表——这是最后一个节点指向链表头的链表类型。
双向链表——在这种情况下，链表的每个节点都保存两个指针，一个指向下一个节点，另一个指向前一个节点。

堆栈（Stack）

堆栈是一种线性数据结构，遵循特定的操作执行顺序。顺序可以是LIFO（后进先出）或 FILO（先进后出）。

Stack之所以被认为是一种复杂的数据结构，是因为它根据Stack数据结构的特点和特点，使用了其他数据结构来实现，比如数组、链表等。

队列（Queue）

Stack类似但特性不同的数据结构是Queue。

队列是一种线性结构，其各个操作遵循先进先出 (FIFO)方法。

队列可以有不同的类型，例如：

循环队列——在循环队列中，最后一个元素连接到队列的第一个元素
双端队列（或称为双端队列） ——双端队列是一种特殊类型的队列，可以从队列的两端执行操作。
优先级队列——这是一种特殊类型的队列，其中元素按照其优先级排列。低优先级元素在高优先级元素之后出列。

堆（Heap）

堆是一种特殊的基于树的数据结构，其中树是完全二叉树。

堆的类型：

一般来说，堆有两种类型。

大顶堆：

在这个堆中，根节点的值必须是其所有子节点中最大的，并且其左右子树也必须执行相同的操作。

小顶堆：

在这个堆中，根节点的值必须是其所有子节点中最小的，并且其左右子树也必须执行相同的操作。

哈希（Hash）

散列是指使用称为散列函数的数学公式从可变大小的输入生成固定大小的输出的过程。该技术确定数据结构中项目存储的索引或位置。

树（Tree）

树数据结构类似于我们在自然界中看到的树，但它是颠倒的。它也有根和叶。根是树的第一个节点，叶子是最底层的节点。树的特点是从它的任何一个节点到任何其他节点只有一条路径。

树数据结构

树有多种不同的类型和变种，常见的树包括：

二叉树（Binary Tree）：每个节点最多有两个子节点，分别称为左子节点和右子节点。
二叉搜索树（Binary Search Tree）：二叉树的一种特殊形式，其中左子节点的值小于等于父节点的值，右子节点的值大于等于父节点的值，便于进行快速的搜索和插入操作。
平衡树（Balanced Tree）：树的节点在高度上保持平衡，以确保树的操作具有良好的性能。常见的平衡树包括AVL树、红黑树等。
堆（Heap）：一种特殊的树结构，用于高效地找到最大值或最小值。常见的堆包括最大堆和最小堆。
B树（B-tree）：一种多路搜索树，常用于数据库和文件系统等存储系统，具有高度的平衡性和高效的查找操作。

图（Graph）

它类似于Tree数据结构，不同之处在于没有特定的根或叶节点，并且可以按任意顺序遍历。

图是一种非线性数据结构，由一组有限的顶点（或节点）和一组连接一对节点的边组成。

图数据结构

每条边都显示一对节点之间的连接。这种数据结构有助于解决许多现实生活中的问题。根据边和节点的方向，有各种类型的图。

以下是一些必须了解的图概念：

图的类型：根据节点的连通性或权重，有不同类型的图。
BFS 和 DFS ：这些是遍历图的算法
图中的循环：循环是一系列连接，我们将在循环中移动这些连接。
图中的拓扑排序
图中的最小生成树

算法

搜索算法

搜索算法用于查找数组、字符串、链表或其他数据结构中的特定元素。

最常见的搜索算法是：

线性搜索- 在此搜索算法中，我们从一端到另一端迭代地检查元素。
二分搜索——在这种类型的搜索算法中，我们将数据结构分成两个相等的部分，并尝试决定需要在哪一半中查找元素。
三元搜索——在这种情况下，数组被分为三个部分，根据分区位置的值，我们决定需要在哪个段中查找所需元素。

除此之外，还有其他搜索算法，例如

跳转搜索
插值搜索
指数搜索

排序算法

通常我们需要根据特定条件对数据进行排列或排序。排序算法就是在这些情况下使用的算法。根据条件，我们可以对一组同质数据进行排序，就像按升序或降序对数组进行排序一样。

排序算法用于根据元素上的比较运算符重新排列给定的数组或列表元素。比较运算符用于决定相应数据结构中元素的新顺序。

显示排序的示例

有许多不同类型的排序算法。一些广泛使用的算法是：

快速排序
归并排序
堆排序
冒泡排序
插入排序
选择排序
树排序
等等

排序算法的复杂性

分治算法

顾名思义，它将问题分解为多个部分，然后解决每个部分，然后再次合并已解决的子任务以解决实际问题。

分而治之是一种算法范式。典型的分而治之算法使用以下三个步骤解决问题。

分解（Divide）：将给定问题分解为相同类型的子问题。
解决（Conquer）：递归地解决这些子问题。
合并（Combine）：将子问题合并为原始问题的解决方案。

这是前面提到的归并排序和快速排序这两种排序算法中提到的主要技术。

贪心算法

顾名思义，该算法一次构建一个解决方案，并选择下一个提供最明显和直接好处的解决方案，即当时的最佳选择。因此，选择局部最优也导致全局解决方案的问题最适合贪婪。

例如，考虑分数背包问题。局部最优策略是选择具有最大价值与重量比的项目。这种策略还可以产生全局最优解决方案，因为我们可以获取某个项目的一部分。

回溯算法

回溯算法源自递归算法，如果递归解决方案失败，则可以选择恢复，即如果解决方案失败，程序将追溯到失败的时刻并构建另一个解决方案。所以基本上它会尝试所有可能的解决方案并找到正确的解决方案。

回溯是一种递归解决问题的算法技术，通过尝试逐步构建解决方案，一次一个部分，删除那些在任何时间点都无法满足问题约束的解决方案

动态规划

动态编程主要是对普通递归的优化。无论何时我们看到重复调用相同输入的递归解决方案，我们都可以使用动态编程对其进行优化。

动态规划算法的主要思想是利用先前计算的结果来避免同一子任务的重复计算，从而有助于降低时间复杂度。

动态规划

图算法

图算法用于解决将图表示为网络的问题，例如航空公司航班、互联网如何连接或社交软件里人之间亲密度。它们在NLP和机器学习中也很流行，用于形成网络。

一些顶级的图形算法包括：

实现广度优先遍历
实现深度优先遍历
计算图级别中的节点数
查找两个节点之间的所有路径
查找图的所有连通分量
迪杰斯特拉算法（Dijkstra）在图数据中查找最短路径
移除边缘

总结

本篇是从理论和概念上对数据结构与算法的一些简单介绍，后面会详细解释数据结构和算法。

本文链接：http://www.28at.com/showinfo-26-15756-0.html数据结构与算法（DSA）基础篇

声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com

上一篇： Git详细使用教程，你学会了吗？

下一篇：顶级ML后端工程师“进化”指南

标签：

热门焦点

一加Ace2 Pro真机揭晓钛空灰配色质感拉满

终于，在经过了几波预热之后，一加Ace2 Pro的外观真机图在网上出现了。还是博主数码闲聊站曝光的，这次的外观设计还是延续了一加11的方案，只是细节上有了调整，例如新加入了钛空灰
小米官宣：2023年上半年出货量中国第一！

今日早间，小米电视官方微博带来消息，称2023年小米电视上半年出货量达到了中国第一，同时还表示小米电视的巨屏风暴即将开始。“公布一个好消息2023年#小米电视上半年出货量中国
CSS单标签实现转转logo

转转品牌升级后更新了全新的Logo，今天我们用纯CSS来实现转转的新Logo，为了有一定的挑战性，这里我们只使用一个标签实现，将最大化的使用CSS能力完成Logo的绘制与动画效果。新logo
Golang 中的 io 包详解：组合接口

io.ReadWriter// ReadWriter is the interface that groups the basic Read and Write methods.type ReadWriter interface { Reader Writer}是对Reader和Writer接口的组合，
让我们一起聊聊文件的操作

文件【1】文件是什么？文件是保存数据的地方，是数据源的一种，比如大家经常使用的word文档、txt文件、excel文件、jpg文件...都是文件。文件最主要的作用就是保存数据，它既可以保
冯提莫签约抖音公会前“斗鱼一姐”消失在直播间

来源：直播观察提起“冯提莫”这个名字，很多网友或许听过，但应该不记得她是哪位主播了。其实，作为曾经的“斗鱼一姐”，冯提莫在游戏直播的年代影响力不输于现
网传小米汽车开始筛选交付中心建筑面积不低于3000平方米

7月7日消息，近日有微博网友@长三角行健者爆料称，据经销商集团反馈，小米汽车目前已经开始了交付中心的筛选工作，要求候选场地至少有120个车位，建筑不能低
华为Mate60系列模具曝光：采用硕大圆形后置相机模组+拼接配色方案

据此前多方爆料，今年华为将开始恢复一年双旗舰战略，除上半年推出的P60系列外，往年下半年的Mate系列也将迎来更新，有望在9-10月份带来全新的华为Mate60
iQOO 11S或7月上市：搭载“鸡血版”骁龙8Gen2 史上最强5G Soc

去年底，iQOO推出了“电竞旗舰”iQOO 11系列，作为一款性能强机，iQOO 11不仅全球首发2K 144Hz E6全感屏，搭载了第二代骁龙8平台及144Hz电竞屏，同时在快充