常见的C++算法知识总结

开课吧小一2021-06-29 17:13

    一般来说想要成为C++开发工程师,需要了解的知识是很多的,这不仅包括C++各个标签的使用,还包括算法、职业规划等更多信息。那么常见的C++算法有哪些呢?

常见的C++算法知识总结

    基本的C++算法分为三类:排序算法、树算法、图算法。算法思想有三种:递推、分治、动态规划以及贪心算法。

    一、排序算法:

    1、基本:

    排序算法:(对基本排序算法的时间复杂度分析主要考虑 比较次数、数据交换次数)。

    冒泡排序:针对数组、本地排序、需要交换数据。O(1)额外空间。

    选择排序:一般针对数组、本地排序、需要交换数据。O(1)的额外空间。

    插入排序:可以是针对数组的本地排序,此时需要移动大片数据,但是比较次数是O(N*logN)。如果是针对链表,比较次数是O(N^2),但是不需要交换数据。

    注意:一般排序都是针对数组的本地排序,数组与链表相比,可以随机访问,空间使用效率更高(链表需要存放指针),而链表一般对于插入与删除操作有更好的性能。

    2、O(N*logN)算法:

    快速排序:针对数组的本地排序,时间复杂度平均O(N*logN),最坏时O(N^2)。空间复杂度O(1)。

    归并排序:可以针对数组,也可以针对链表。针对数组时时间复杂度为O(N*logN),空间复杂度为O(N)。

    3、堆排序:

    1991年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(RobertW.Floyd)和威廉姆斯(J.Williams)在1964年共同发明了著名的堆排序算法(HeapSort)。

    堆是一种非常高效的数据结构,可以用数组来表示堆。

    堆排序是针对数组的本地排序,时间复杂度为O(N*logN),空间复杂度为O(1)。

    对于降序排列时用最小堆,首先建立堆,然后将第一个元素(堆头)与组后一个元素交换。找到了排列的最后一个元素,然后再调整前N-1个元素为最小堆,依次类推,即完成排序。

    注意:堆得建立,堆的建立的时间复杂度为O(N*logN),可以有多种方法建立堆。

    4、基数排序:

    数据的取值范围不大,利用bitmap。

    5、外排序:

    归并排序,多路归并排序(利用堆实现多路归并排序)。

    使用堆进行多路排序时,堆中的每个元素同附加上一个域,存放该元素来自那一路。

    堆一般还可以用于TopK算法,求TopK最大可以使用K个元素的最小堆维护K个最大元素,对原始数组扫描一遍即可。

常见的C++算法知识总结

    二、树的算法:

    树一般用链表实现,通常用树数据结构实现数据的快速插入、删除、查找。

    1、平衡二叉查找树:

    RB-Tree、AVL、Treap、伸展树(无需存放额外信息)。

    2、B树:

    用于建立文件系统或数据库的索引。B树的设计目标是减少IO访问次数。B树也是一棵平衡树。

    3、二项树、二项堆、费波那奇堆。

常见的C++算法知识总结

    三、图的算法:

    1、图的表示:

    有向图、无向图的邻接表表示、矩阵表示。

    2、广度优先搜索、深度优先搜索:

    广度优先搜索(BFS):找到从单个源点到所有点得最短路径,适用于有向图、无向图。算法发杂度为O(V+E),注意算法对应图的边没有权重。算法使用队列实现广度优先。算法使用三个辅助变量、color、paraent、distance数组。搜索后的parent构成广度优先树

    深度优先搜索(DFS):可以随意从一个节点开始,遍历树的所有节点,使用于有向图、无向图。搜索构成森林。算法通过递归方式实现,依次递归完成后可能只搜索整个连通树的部分节点,因此需要从新任意选择一个节点从新开始DFS,整个搜索结果构成搜索森林。算法使用三个辅助变量:color,v,f。v表示搜索到该节点时间,f表示该节点的邻接节点都扫描完成的时间。

    注意DFS可以完成拓扑排序。利用f出现时间的降序就是拓扑序,可以在深度优先搜索的过程中得到该排序。

    DFS算法还可以用于发现强连通分支。

    3、最小生成树:

    针对无向连通图的,常见的算法有Kruskal算法和Prim算法。

    4.最短路径:

    有权值的最短路径问题。可以是有向图,可以是无向图。权值可以为负值。

    变种:点与点之间最短路径、固定终点最短路径、所有点之间最短路径、最长路径(将权值去负值利用bellman-ford算法即可)。

    Bellman-Ford算法。惊醒V-1遍松弛遍历,每次遍历,按照一定顺序,依次将所有的边松弛一遍。结束后,对所有的边进行一次check,如果有边不符合松弛条件,则返回false,表明图中存在负权值的环(该特性可以用于检测有向图中得环),算法复杂度O(VE)。

    Dijkstra算法。只能针对于正值的边。算法复杂度O(V^2)。

    5、求所有点之间的最短路径:

    矩阵上得动态规划算法。

    以上就是开课吧广场小编为大家整理的“常见的C++算法知识总结”一文,更多相关信息尽在开课吧广场C/C++教程频道。

相关推荐:

2021大厂高频面试题精选,0元免费领

福利来袭,C++经典项目实战免费领取!

职场进阶必备,数据分析职业能力特训营

免责声明:本站所提供的内容均来源于网友提供或网络搜集,由本站编辑整理,仅供个人研究、交流学习使用。如涉及版权问题,请联系本站管理员予以更改或删除。
有用1
分享