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

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

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

导读什么是 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官宣：普及16G内存引领24G

一加官方今天继续为本月发布的新机一加Ace2 Pro带来预热，公布了内存方面的信息。“淘汰 8GB ，12GB 起步，16GB 普及，24GB 引领，还有呢？#一加Ace2Pro#，2023 年 8 月，敬请期待。”同时
虚拟键盘 API 的妙用

你是否在遇到过这样的问题：移动设备上有一个固定元素，当激活虚拟键盘时，该元素被隐藏在了键盘下方？多年来，这一直是 Web 上的默认行为，在本文中，我们将探讨这个问题、为什么会发生
一个注解实现接口幂等，这样才优雅！

场景码猿慢病云管理系统中其实高并发的场景不是很多，没有必要每个接口都去考虑并发高的场景，比如添加住院患者的这个接口，具体的业务代码就不贴了，业务伪代码如下：图片上述代码有
2天涨粉255万，又一赛道在抖音爆火

来源：运营研究社作者 | 张知白编辑 | 杨佩汶设计 | 晏谈梦洁这个暑期，旅游赛道彻底火了：有的「地方」火了——贵州村超旅游收入 1 个月超过 12 亿；有的「博主」火了&m
华为和江淮汽车合作开发百万元问界MPV？双方回应来了

8月1日消息，郭明錤今天在社交平台发文称，华为正在和江淮汽车合作，开发售价在100万元的问界MPV，预计在2024年第2季度量产，销量目标为上市首年交付5万辆。
2纳米决战2025

集微网报道从三强争霸到四雄逐鹿，2nm的厮杀声已然隐约传来。无论是老牌劲旅台积电、三星，还是誓言重回先进制程领先地位的英特尔，甚至初成立不久的新
超级标准版旗舰！iQOO 11S全球首发iQOO超算独显芯片

上半年已接近尾声，截至目前各大品牌旗下的顶级旗舰都已悉数亮相，而下半年即将推出的顶级旗舰已经成为了数码圈爆料的主流，其中就包括全新的iQOO 11S系
英特尔Xe-HP项目终止，将专注Xe-HPC/HPG系列显卡

据10 月 31 日消息报道，英特尔高级副总裁兼加速计算系统和图形事业部总经理表示，Xe-HP“ Arctic Sound” 系列服务器 GPU 已经应用于 oneAPI devcloud 云服
“买真退假” 这种“羊毛”不能薅

□ 法治日报记者王春　　□ 本报通讯员胡佳丽　　2020年初，还在上大学的小东加入了一个大学生兼职QQ群。群主“七王”在群里介绍一些刷单赚

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

什么是 DSA？

什么是数据结构？

什么是算法？

认识DSA

时间和空间复杂性

数据结构

数组（Array）

链表（Linked Lists）

堆栈（Stack）

队列（Queue）

堆（Heap）

哈希（Hash）

树（Tree）

图（Graph）

算法

搜索算法

排序算法

分治算法

贪心算法

回溯算法

动态规划

图算法

总结

一加Ace2 Pro官宣：普及16G内存引领24G

虚拟键盘 API 的妙用

一个注解实现接口幂等，这样才优雅！

2天涨粉255万，又一赛道在抖音爆火

华为和江淮汽车合作开发百万元问界MPV？双方回应来了

2纳米决战2025

超级标准版旗舰！iQOO 11S全球首发iQOO超算独显芯片

英特尔Xe-HP项目终止，将专注Xe-HPC/HPG系列显卡

“买真退假” 这种“羊毛”不能薅

最新推荐

猜你喜欢

热门推荐

相关资讯