大学四年计算机旅途，那些惊艳我们的高效算法

傷城~ 2023-10-12 12:32 7阅读 0赞

> 下面这些算法都具有高效、快速、可靠等特点，它们在计算机科学中有着广泛的应用，并被广泛认为是令人惊艳的高效算法。

## 一、快速排序算法（QuickSort） ##

快速排序是一种常用的排序算法，它的时间复杂度为 O(nlogn)，是目前最快的排序算法之一。它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的元素都比另一部分的元素小，然后再按照此方法对这两部分数据分别进行快速排序，整个排序过程递归进行，以此达到整个数据变成有序序列的目的。  
![在这里插入图片描述][fa96c6c1d16f46468fcabca643e17e1b.png]

## 二、分治算法（Divide and Conquer） ##

分治算法是一种递归式的问题解决方法，它将一个大规模的问题分解成若干个规模较小但结构与原问题相似的子问题，然后递归地解决这些子问题，最后将各个子问题的解合并起来得到原问题的解。分治算法的经典应用包括归并排序、二分查找等，下面以二分查找算法为例说明分治的思想。

二分查找是一种高效的查找算法，它通过反复将查找区间划分为两半来工作。它特别适用于搜索排序数组或列表，并且时间复杂度为O（log n），其中n是数组或列表的大小。

![在这里插入图片描述][03711443b7ef482882e963280613fc40.png]

## 三、动态规划算法（Dynamic Programming） ##

动态规划是一种将复杂问题分解成更小的子问题来解决的优化技术，它通常用于优化多阶段决策问题的求解。动态规划算法的特点是通过储存已经计算过的结果，减少重复计算，从而提高算法的效率。动态规划的经典应用包括背包问题、最长公共子序列问题等。刷过算法题的同学应该对DP比较熟悉了，因为除去复杂数据结构外，DP算是算法题中的top了，非常锻炼思维。

![在这里插入图片描述][cd97d4073aee4442a6dbb4c50cfbcccc.png]

## 四、Dijkstra算法 ##

这是一种在图中寻找两个节点之间最短路径的著名算法，数据结构课必教的内容。它的工作原理是通过迭代地选择距离最小的节点并松弛其相邻节点，直到达到目标节点。Dijkstra算法的时间复杂度为O（E + V\*log(V)），其中E是边的数量，V是图中的节点数。各大高校的考研机试最喜欢出的题目之一，作为签到题考察学生的算法基础。

![在这里插入图片描述][bda074a98d4e4749b1bcdc04d0ddcc9d.png]

## 五、A\*搜索算法 ##

A*是一种启发式搜索算法，通常用于路径规划和图遍历问题。它结合了广度优先搜索和Dijkstra算法的优点，通过使用启发式函数来估计到达目标节点的代价，从而帮助它集中于最有前途的路径。A*算法的时间复杂度为O（b^d），其中b是搜索树的分支因子，d是解决方案的深度。常用于机器人的自主导航，在二维栅格地图中使用A\*规划到达目标点的路径。

![在这里插入图片描述][3503efd09b764bd69826e1fde11f2875.png]

## 六、蒙特卡罗算法 ##

蒙特卡罗算法是一类使用随机采样来解决问题的概率性算法。它们通常用于模拟、优化和统计分析。蒙特卡罗算法可以产生高概率的准确结果，并且对于复杂问题比确定性算法通常更快。蒙特卡罗算法一般分为三个步骤，包括构造随机的概率的过程，从构造随机概率分布中抽样，求解估计量。在求解激光SLAM定位时，经常会用到蒙特卡洛算法，可以说是实际工程中我接触的最多的算法。

![在这里插入图片描述][14fa2fc1be244446add50c5da8901316.png]

最后放上所有的C++算法标签，你掌握了是否有50%呢，没有的话抓紧去学习吧~

![在这里插入图片描述][b3ad9a7c2bee4568a6bbd2defeaf5ec7.png]

[fa96c6c1d16f46468fcabca643e17e1b.png]: https://img-blog.csdnimg.cn/fa96c6c1d16f46468fcabca643e17e1b.png
[03711443b7ef482882e963280613fc40.png]: https://img-blog.csdnimg.cn/03711443b7ef482882e963280613fc40.png
[cd97d4073aee4442a6dbb4c50cfbcccc.png]: https://img-blog.csdnimg.cn/cd97d4073aee4442a6dbb4c50cfbcccc.png
[bda074a98d4e4749b1bcdc04d0ddcc9d.png]: https://img-blog.csdnimg.cn/bda074a98d4e4749b1bcdc04d0ddcc9d.png
[3503efd09b764bd69826e1fde11f2875.png]: https://img-blog.csdnimg.cn/3503efd09b764bd69826e1fde11f2875.png
[14fa2fc1be244446add50c5da8901316.png]: https://img-blog.csdnimg.cn/14fa2fc1be244446add50c5da8901316.png
[b3ad9a7c2bee4568a6bbd2defeaf5ec7.png]: https://img-blog.csdnimg.cn/b3ad9a7c2bee4568a6bbd2defeaf5ec7.png