Python -Analytics Vidhya中数据结构的前7个算法

介绍

有效的软件开发取决于对算法和数据结构的强烈了解。 Python以其易用性而闻名，它提供了内置的数据结构，例如列表，词典和集合。但是，通过将适当的算法应用于这些结构来释放真正的力量。算法本质上是解决问题的规则或过程集。算法和数据结构的联合使用将基本脚本转换为高度优化的应用程序。

本文探讨了Python数据结构的七种基本算法。

目录

• 介绍
• 算法在Python数据结构中的重要性
• Python数据结构的七个关键算法
  • 1. 二进制搜索
  • 2. 合并排序
  • 3. 快速排序
  • 4. Dijkstra的算法
  • 5. 广度优先搜索（BFS）
  • 6. 深度优先搜索（DFS）
  • 7. 哈希
• 结论

算法在Python数据结构中的重要性

有效算法至关重要，原因有几个：

• 增强的性能：精心设计的算法，再加上合适的数据结构，最大程度地减少时间和空间的复杂性，从而更快，更有效的程序。例如，在二进制搜索树上的二进制搜索大大减少了搜索时间。
• 大型数据集的可伸缩性：有效的算法对于处理大量数据集至关重要，以确保处理仍然迅速且资源效率。没有优化的算法，大型数据结构的操作在计算上变得昂贵。
• 改进的数据组织：算法有助于组织结构内的数据，从而简化搜索和操纵。对QuickSort和Mergesort等算法排序在阵列或链接列表中排列元素，以便于访问。
• 优化的内存使用情况：算法通过最大程度地减少内存消耗来有助于有效存储。哈希功能，例如，在哈希表上分配数据，以减少搜索时间。
• 利用库功能：许多Python库（Numpy，Pandas，Tensorflow）依赖于复杂的算法进行数据操作。了解这些算法使开发人员可以有效地使用这些库。

Python数据结构的七个关键算法

让我们检查七种至关重要的算法：

1。二进制搜索

二进制搜索是用于在排序列表中查找特定项目的高效算法。它通过反复将搜索间隔分为一半而起作用。如果目标值小于中间元素，则搜索将继续在下半部分。否则，它会在上半部继续。这种对数时间复杂性（O（log n））使其比对大数据集的线性搜索要快得多。

算法步骤

1. 初始化：将left设置为0， right设置为阵列的长度负1。
2. 迭代： left小于或等于right ：
   • 计算中间索引（ mid ）。
   • 将中间元素与目标值进行比较。如果相等，请返回mid 。
   • 如果目标小于中间元素， right更新到mid - 1 。
   • 否则， left更新到mid 1 。
3. 找不到目标：如果循环完成未找到目标，请返回-1。

代码实施（说明性）

 Def Binary_search（ARR，目标）：
    ＃...（原始文本中的实现）

在需要快速查找的情况下，二进制搜索是无价的，例如数据库索引。

2。合并排序

合并排序是一种划分和争议算法，它递归将未分类的列表划分为较小的sublist，直到每个sublist仅包含一个元素。然后，这些订订者反复合并以产生新的分类订书机，直到获得单个排序列表为止。它的时间复杂性是O（n log n），使大型数据集有效。

算法步骤

1. 分割：递归将数组分为两个半部分，直到每个半仅包含一个元素。
2. 征服：递归对每个子列表进行分类（基本情况：已经对单元素列表进行了排序）。
3. 合并：通过比较每个sublist的元素并将较小的元素放入结果列表中，将分类的子列表合并到单个排序列表中。

代码实施（说明性）

 DEF MERGE_SORT（ARR）：
    ＃...（原始文本中的实现）

合并排序特别适合整理链接列表和处理可能完全不适合内存的大型数据集。

3。快速排序

快速排序是另一种分裂和串扰算法，选择一个“枢轴”元素，并根据它们是小于还是大于枢轴的两个子阵列，将其他元素分为两个子阵列。此过程递归地应用于子阵列，直到整个数组分类为止。尽管其最差的时间复杂性是O（n²），但其平均案例性能为O（n log n），使其成为高度实用的分类算法。

算法步骤

1. 枢轴选择：选择一个枢轴元素（存在各种策略）。
2. 分区：重新排列阵列，以使元素比枢轴更小，并且元素更大。
3. 递归：在枢轴之前和之后，递归将快速排序应用于子阵列。

代码实施（说明性）

 def quick_sort（arr）：
    ＃...（原始文本中的实现）

Quick Sort的效率使其成为许多库和框架中的流行选择。

4。Dijkstra的算法

Dijkstra的算法找到了从单个源节点到具有非阴性边缘权重的图中所有其他节点的最短路径。它迭代地选择距源最小的暂定距离的节点，并更新其邻居的距离。

算法步骤

1. 初始化：为每个节点分配一个暂定距离：源节点的零，以及所有其他节点的无穷大。
2. 迭代：虽然有未访问的节点：
   • 选择最小的暂定距离的未访问节点。
   • 对于每个邻居，计算通过选定节点的距离。如果此距离短于当前的暂定距离，请更新邻居的暂定距离。
3. 终止：当访问所有节点或优先队列为空时，该算法将终止。

代码实施（说明性）

导入heapq

Def Dijkstra（图，开始）：
    ＃...（原始文本中的实现）

Dijkstra的算法在GPS系统，网络路由和各种路障问题中具有应用。

5。广度优先搜索（BFS）

BFS是一种图形遍历算法，可以按级别探索图级。它从根节点开始，然后访问其所有邻居，然后再转移到下一个邻居。这对于在未加权图中找到最短路径很有用。

算法步骤

1. 初始化：从包含根节点的队列和跟踪访问的节点的集合开始。
2. 迭代：虽然队列不是空的：
   • dequeue a节点。
   • 如果未被访问，请将其标记为访问，并占领其未访问的邻居。

代码实施（说明性）

从藏品进口Deque

def bfs（图，启动）：
    ＃...（原始文本中的实现）

BFS在社交网络，点对点网络和搜索引擎中找到应用程序。

6。深度优先搜索（DFS）

DFS是另一种图形遍历算法，它通过在回溯之前沿每个分支进行深度探索图。它使用堆栈（或递归）来跟踪访问的节点。

算法步骤

1. 初始化：从包含根节点的堆栈开始，然后进行跟踪访问的节点的集合。
2. 迭代：虽然堆栈不是空的：
   • 弹出一个节点。
   • 如果未被访问，请将其标记为访问，并将其未访问的邻居推到堆栈上。

代码实施（说明性）

 def dfs_iterative（图，启动）：
    ＃...（原始文本中的实现）

DFS用于拓扑排序，循环检测和解决难题。

7。哈希

哈希是将密钥映射到哈希表中的索引的一种技术，以有效地检索数据。哈希功能将键转换为索引，从而可以快速查找，插入和删除。需要使用碰撞处理机制来解决不同键映射到相同索引的情况。

算法步骤

1. 哈希函数：选择哈希函数以将键映射到索引。
2. 插入：使用哈希功能计算索引，然后将键值对插入相应的存储桶（处理碰撞）中。
3. 查找/删除：使用哈希函数查找索引并检索/删除键值对。

代码实施（说明性）

班级可观：
    ＃...（原始文本中的实现）

哈希表是数据库，缓存和其他需要快速数据访问的应用程序的基础。

结论

算法的坚实掌握及其与数据结构的相互作用对于有效的Python编程至关重要。这些算法是优化性能，提高可扩展性和解决复杂问题的重要工具。通过掌握这些技术，开发人员可以构建强大而高性能的应用程序。

以上是Python -Analytics Vidhya中数据结构的前7个算法的详细内容。更多信息请关注PHP中文网其他相关文章！