什么是 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） 在图数据中查找最短路径
- 移除边缘
总结
本篇是从理论和概念上对数据结构与算法的一些简单介绍，后面会详细解释数据结构和算法。
