每个程序员都应该知道的 7 种算法

作为一名编程专业的学生,​​您可能在整个职业生涯中学习了许多不同的算法。精通不同的算法对于任何程序员来说都是绝对必要的。

有这么多算法,跟踪什么是必不可少的可能具有挑战性。如果您正在为面试做准备或只是提高自己的技能,这份清单会让事情变得相对容易。请继续阅读,因为我们列出了程序员最重要的算法。

1. Dijkstra 算法

Edsger Dijkstra 是他那个时代最有影响力的计算机科学家之一,他为计算科学的许多不同领域做出了贡献,包括操作系统、编译器构建等等。 Dijkstra 最显着的贡献之一是他的图最短路径算法的独创性,也称为 Dijkstra 的最短路径算法。

Dijkstra 算法在图中找到从源到所有图顶点的单个最短路径。在算法的每次迭代中,添加一个与源的最小距离的顶点,并且该顶点不存在于当前最短路径中。这是 Djikstra 算法使用的贪婪属性。

该算法通常使用集合来实现。 Dijkstra 算法在用最小堆实现时非常有效;您可以在 O(V+ElogV) 时间内找到最短路径(V 是顶点数,E 是给定图中的边数)。

Dijkstra 算法有其局限性;它仅适用于具有正权重边的有向图和无向图。对于负权重,Bellman-Ford 算法通常更可取。

面试问题通常包括 Djikstra 的算法,因此我们强烈建议您了解其复杂的细节和应用。

2. 归并排序

我们在这个列表中有几个排序算法,归并排序是最重要的算法之一。它是一种基于分而治之的编程技术的高效排序算法。在最坏的情况下,归并排序可以在 O(nlogn) 时间内对“n”个数字进行排序。与冒泡排序(需要 O(n^2) 时间)等原始排序技术相比,归并排序非常高效。

相关:归并排序算法简介

在归并排序中,要排序的数组被反复分解为子数组,直到每个子数组都包含一个数字。然后递归算法反复合并子数组并对数组进行排序。

3. 快速排序

快速排序是另一种基于分而治之编程技术的排序算法。在这个算法中,首先选择一个元素作为主元,然后围绕这个主元对整个数组进行分区。

正如您可能已经猜到的那样,良好的支点对于高效排序至关重要。枢轴可以是随机元素、媒体元素、第一个元素,甚至是最后一个元素。

快速排序的实现通常在选择枢轴的方式上有所不同。在一般情况下,快速排序将在 O(nlogn) 时间内对具有良好主元的大型数组进行排序。

快速排序的通用伪代码在枢轴上重复划分数组并将其定位在子数组的正确位置。它还将小于枢轴的元素放在其左侧,将大于枢轴的元素放在其右侧。

深度优先搜索 (DFS) 是最早教授给学生的图算法之一。 DFS 是一种用于遍历或搜索图的高效算法。也可以修改它以用于树遍历。

DFS 遍历可以从任意节点开始,深入到每个相邻的顶点。当没有未访问的顶点或有死胡同时,算法会回溯。 DFS 通常使用堆栈和布尔数组实现,以跟踪访问过的节点。 DFS 易于实现且非常高效;它有效(V+E),其中 V 是顶点数,E 是边数。

DFS 遍历的典型应用包括拓扑排序、检测图中的循环、寻路和查找强连通分量。

广度优先搜索 (BFS) 也称为树的层序遍历。 BFS 在 O(V+E) 中的工作类似于 DFS 算法。但是,BFS 使用队列而不是堆栈。 DFS 深入图中,而 BFS 横向遍历图。

BFS 算法利用队列来跟踪顶点。未访问的相邻顶点被访问、标记和排队。如果顶点没有任何相邻的顶点,则从队列中删除一个顶点并进行探索。

BFS 常用于点对点网络,未加权图的最短路径,以及寻找最小生成树。

二分搜索是一种在排序数组中查找所需元素的简单算法。它的工作原理是重复将数组一分为二。如果需要的元素小于最中间的元素,则进一步处理中间元素的左侧;否则,右侧被减半并再次搜索。重复该过程,直到找到所需元素。

二分查找的最坏情况时间复杂度是 O(logn),这使得它在查找线性数组时非常有效。

7. 最小生成树算法

图的最小生成树 (MST) 在所有可能的生成树中具有最小的成本。生成树的成本取决于其边的权重。需要注意的是,可以有不止一个最小生成树。有两种主要的 MST 算法,即 Kruskal 和 Prim。

Kruskal 的算法通过将成本最低的边添加到不断增长的集合中来创建 MST。该算法首先按权重对边进行排序,然后从最小值开始将边添加到 MST。

需要注意的是,该算法不会添加形成循环的边。 Kruskal 算法是稀疏图的首选。

Prim's Algorithm 也使用贪婪属性,非常适合密集图。 Prim 的 MST 的中心思想是有两组不同的顶点;一组包含不断增长的 MST,而另一组包含未使用的顶点。在每次迭代中,将选择连接两个集合的最小权重边。

最小生成树算法对于聚类分析、分类法和广播网络至关重要。

精通算法的高效程序员

程序员不断地学习和发展他们的技能,每个人都需要精通一些核心要素。熟练的程序员知道不同的算法,每种算法的优缺点,以及哪种算法最适合给定的场景。