程序员经验分享-hwhale

C++算法之——常用算法总结

2023-05-16

基本的C++算法分为三类：排序算法、树算法、图算法

算法思想有三种：递推、分治、动态规划 以及 贪心算法。
本文将简要介绍上面三类算法，介绍时穿插介绍算法思想。
一、排序算法
1、基本O(n^2)排序算法： （对基本排序算法的时间复杂度分析主要考虑   比较次数、数据交换次数）
冒泡排序：针对数组、本地排序、需要交换数据。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年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd)和威廉姆斯(J．Williams)在1964年共同发明了著名的堆排序算法( Heap Sort )
堆是一种非常高效的数据结构，可以用数组来表示堆。
堆排序是针对数组的本地排序，时间复杂度为O(N*logN)，空间复杂度为O(1)
对于降序排列时用最小堆，首先建立堆，然后将第一个元素（堆头）与组后一个元素交换。找到了排列的最后一个元素，然后再调整前N-1个元素为最小堆，依次类推，即完成排序。
注意：堆得建立， 堆的建立的时间复杂度为O(N*logN)，可以有多种方法建立堆
4. 基数排序
数据的取值范围不大，利用bitmap
5. 外排序
归并排序，多路归并排序（利用堆实现多路归并排序）
使用堆进行多路排序时，堆中的每个元素同附加上一个域，存放该元素来自那一路
堆一般还可以用于TopK算法，求TopK最大可以使用K个元素的最小堆维护K个最大元素，对原始数组扫描一遍即可。
二、树的算法
树一般用链表实现，通常用树数据结构实现数据的快速插入、删除、查找。
1. 平衡二叉查找树
RB-Tree、 AVL、 Treap、 伸展树（无需存放额外信息）
2. B树
用于建立文件系统或数据库的索引。B树的设计目标是减少IO访问次数。B树也是一棵平衡树
3. 二项树、二项堆、费波那奇堆
三、图的算法
1. 图的表示
有向图、无向图 的 邻接表表示、矩阵表示
2. 广度优先搜索、深度优先搜索
广度优先搜索（BFS）：找到从单个源点到所有点得 最短路径，适用于有向图、无向图。算法发杂度为O(V+E)，注意算法对应图的边没有权重。算法使用队列实现广度优先。算法使用三个辅助变量、color、paraent、distance数组。搜索后的parent构成广度优先树
深度优先搜索（DFS）：可以随意从一个节点开始，遍历树的所有节点，使用于有向图、无向图。搜索构成森林。算法通过递归方式实现，依次递归完成后可能只搜索整个连通树的部分节点，因此需要从新任意选择一个节点从新开始DFS，整个搜索结果构成搜索森林。算法使用三个辅助变量：color，v，f。v表示搜索到该节点时间，f表示该节点的邻接节点都扫描完成的时间。
注意DFS可以完成拓扑排序。利用f出现时间的降序就是拓扑序，可以在深度优先搜索的过程中得到该排序。
DFS算法还可以用于发现强连通分支。
3. 最小生成树
针对无向连通图的，常见的算法有 Kruskal算法和Prim算法
Kruskal算法
将所有的边非降序排列，所有的顶点初始化为不相交集合，每次取一个边，如果该边属于不同的集合，则该边加入解集，同时更新不想交集合。注意：不想交集合实现有专门的数据结构。
Prim算法
该算法与Dijkstra算法类似，每次加入已覆盖集合A和未覆盖集合B之间最短的边。
4. 最短路径
有权值的最短路径问题。可以是有向图，可以是无向图。权值可以为负值。
变种：点与点之间最短路径、固定终点最短路径、所有点之间最短路径、最长路径（将权值去负值利用bellman-ford算法即可）
Bellman-Ford算法
惊醒V-1遍松弛遍历，每次遍历，按照一定顺序，依次将所有的边松弛一遍。结束后，对所有的边进行一次check，如果有边不符合松弛条件，则返回false，表明图中存在负权值的环（该特性可以用于检测有向图中得环），算法复杂度O(VE)
Dijkstra算法
只能针对于正值的边。算法复杂度O(V^2)
5. 求所有点之间的最短路径
矩阵上得动态规划算法。
Floyd-Warshall算法，d_ij(k) 表示从顶点i到顶点j，中间节点只包含{1、2、... k}的最短路径。d_ij(n)即为所求。
Floyd-Warshall算法可以用于求任意两个顶点是否可达
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

C++算法之——常用算法总结 的相关文章

  • SQL Server调用WebAPI和WebService

    SQLSERVER调用WebAPI和WebServiceSqlServer调用webapi和webService接口 declare 64 url nvarchar max set 64 url 61 39 http XXX GetToke

  • SQL Server中cross apply和inner join的区别

    Sqlserver 中 CrossApply 和 inner join 的区别 cross apply和inner join有很多相同处 xff0c 都是为了联表查询数据 xff0c 而且取两张表之间的交集 xff0c 不同在于 xff0c

  • C语言 rand函数（随机）

    rand 函数不是真正的随机数生成器 xff0c 而srand 会设置供rand 使用的随机数种子 如果你在第一次调用rand 之前没有调用srand xff0c 那么系统会为你自动调用srand 而使用同种子相同的数调用 rand 会导致

  • 键盘输入 kbhit()

    函数名 xff1a kbhit 功能及返回值 xff1a 检查当前是否有键盘输入 xff0c 若有则返回一个非0值 xff0c 否则返回0 用 法 xff1a int kbhit void 包含头文件 xff1a include lt co

  • 设置光标输出位置

    void gotoXY short x short y 设置光标输出位置 COORD pos 61 x y HANDLE out 61 GetStdHandle STD OUTPUT HANDLE SetConsoleCursorPosit

  • tensorflow错误 Assign requires shapes of both tensors to match. lhs shape= rhs shape=

    在跑tensorflow任务的时候 xff0c 有时候会碰到这种错误 Tensorflow Assign requires shapes of both tensors to match lhs shape 61 20 rhs shape

  • 贪吃蛇游戏源码（可在VC++6.0运行）（在原作者的基础上进行小改进）

    自己做的第一个游戏 xff01 xff01 xff01 说说制作历程吧 xff1a 1 阅读并理解原作者 xff08 没有找到作者名 xff09 源码 2 仿写一边源码 3 经过一天的冥想 xff08 其实是玩了一天吃鸡 xff09 4 然

  • MFC插背景图

    把下面这段代码加进OnPaint 里就行了 CPaintDC dc this CBitmap bitmap bitmap LoadBitmap IDB BITMAP1 这个IDB BITMAP1要自己添加 CBrush brush brus

  • MFC按钮跳转

    需要先添加新建的dialo 的头文件 例如 include 34 AAA h 34 void COnclickDlg OnBnClickedOk AAA Dlg Dlg DoModal

  • MSDN关闭窗口

    退出程序用 AfxGetMainWnd gt SendMessage WM CLOSE 关闭当前窗口 用 DestroyWindow 关闭模式对话框用 EndDialog 0

  • 链表的插入和删除

    while NULL 61 p amp amp i lt pos 1 插入 p 61 p gt pNext 43 43 i if NULL 61 61 p i gt pos 1 return false while NULL 61 p gt

  • 初始化！

    int length list PNODE pHead int len 61 0 需要初始化 xff0c 不然会显示乱码 PNODE p 61 pHead gt pNext while NULL 61 p len 43 43 p 61 p

  • Python爬虫：爬虫所需要的爬虫代理ip是什么？

    当我们对某些网站进行爬去的时候 xff0c 我们经常会换IP来避免爬虫程序被封锁 代理ip地址如何获取 xff1f 其实也是一个比较简单的操作 xff0c 目前网络上有很多IP代理商 xff0c 例如西刺 xff0c 芝麻 xff0c 犀牛

  • MySQL知识点

    主键自增 JDBC中MySQL自增主键的值 xff1a 是通过connection连接发送sql语句时多传入一个参数conn prepareStatement sql PreparedStatement RETURN GENERATED K

  • C语言实现FTP文件传输

    一 要求 FTP实则为两个程序的互相交流 xff0c 把信息指令相互发送并处理 1 客户端请求下载文件 把文件名发送给服务器 2 服务器接收客户端发送的文件名 根据文件名找到文件 xff0c 把文件大小发送给客户端 3 客户端接收到文件大小

  • 我的2013，它不平淡

    2013年春节过后 xff0c 等我再赴学校 xff0c 我已经是大三下学期的学生了 对于一名软件学院的学生 xff0c 这就意味着要整备离开校园出去实习了 果然 xff0c 陆陆续续各大软件公司 xff08 培训部门而已 xff09 或培

  • mac下office文档自动恢复

    如果想要查找mac上自动恢复的文件 xff0c 可以在如下的文件目录中找到 xff0c 注意将 username 替换为自己的用户名 xff1a Excel Users username Library Containers com mic

  • FreeRTOS消息队列/信号量/事件

    1 消息队列主要用于任务之间消息的传递 2 信号量分为计数信号量 二值信号量 互斥信号量 3 事件用于外部事件的触发 4 计数信号量用于发生次数的统计 读取以后可以减1 二值信号量 互斥信号量与二值信号量的主要区别是可以防止优先级翻转 5

  • python装饰器详解-python中的装饰器详解

    在了解装饰器的之前一定要先了解函数作为参数传递 什么是函数内嵌 请参考我之前写的博客函数简介 因为在python里面 函数也是对象 也可以作为参数进行传递 python装饰器本质也是一种特殊函数 它接收的参数是函数对象 然后动态地函数参数添

  • python装饰器详解-python装饰器的详细解析

    什么是装饰器 xff1f python装饰器 xff08 fuctional decorators xff09 就是用于拓展原来函数功能的一种函数 xff0c 目的是在不改变原函数名 或类名 的情况下 xff0c 给函数增加新的功能 这个函

随机推荐

  • 安装oracle出现环境不满足最低要求

    安装win64 11gR2 database 1of2的时候出现这个 xff0c 百度了下解决方法 在oracle安装包找到stage文件夹 然后找到cvu 然后在cvu里面找到cvu prereq xff0c 用记事本打开 增加以下内容

  • mybatis的优缺点

    优点 xff1a 1 基于SQL语法 xff0c 简单易学 2 能了解底层组装过程 3 SQL语句封装在配置文件中 xff0c 便于统一管理与维护 xff0c 降低了程序的耦合度 4 程序调试方便 5 与传统JDBC比较较少了大量的代码量

  • Eclipse打不开，提示查看Log文件

    今天在使用Eclipse的时候 xff0c Eclipse整个黑屏 xff0c 然后果断启动任务管理器 xff0c 关掉了Eclipse然后重启 xff0c 发现Eclipse打不开了 xff0c 然后提示查看log文件 xff0c 然后解

  • equals的用法的注意事项

    String a 61 34 equals的用法 34 String b 61 a equals 34 equals的用法 34 34 相等 34 34 不相等 34 这样的用法有隐患 xff0c 当传入的参数a是空值的时候 xff0c 程

  • svnE175002、E160024以及提交冲突解决方法

    E17005与Eclipse代理有关 xff0c 将代理勾选掉 xff0c 把active provider 改为Direct 即可 E160024 是以为有的文件过期了 xff0c 右键更新即可 最后 xff0c svn代码提交冲突的时候

  • break和continue的区别

    1 一般的continue会退回最内层循环的开头 xff08 并继续执行 xff09 2 带标签的continue会到达标签的位置 xff0c 并重新进入紧接在那个标签后面的循环 3 一般的break会中断并跳出当前循环 4 带标签的bre

  • samba服务常用命令

    sudo vim etc samba smb conf 里增添用户 span class token punctuation span bsp span class token punctuation span comment span c

  • 用mac进行图片的自由裁剪

    用mac上自带的图片预览工具 xff0c 即可完成对图片的自由裁剪

  • WEB项目部署到Linux下无法访问html、css、js等静态文件的解决

    WEB项目 xff0c 在自己本机 xff08 windows xff09 下通过Tomcat访问 一切正常 部署到Linux下的Tomcat 进行访问 除了 do接口和jsp页面能访问外 其他的都不能访问 原因 xff1a 默认80端口

  • Java规范的三种注释方式

    在学习开发中药养成良好的编码习惯 xff0c 规整的代码格式会为程序日后的维护工作提供便利 在此对编码规则做了以下总结 xff1a 1 每条语句尽量单独占一行 xff0c 每条语句都要以分号结束 xff1b 2 在声明变量时 xff0c 尽

  • Tensorflow2.5安装（安装问题，这一篇全解决）

    恭喜你发现全网最简单最详细的Tensorflow安装教程 xff01 本文将给出2 5版本的具体配置 xff0c 若要安装其他版本也可参照本文的思路 与过去版本对比 xff0c 你可以感受到来自Tensorflow2 5的善意 xff1a

  • linux嵌入式arm基础笔记5之录音与播放

    1 粤嵌GEC6818开发板介绍 http www gec lab com arm show 72 html 2 粤嵌GEC6818平台介绍及其开发板配置 操作系统 心若十年的博客 CSDN博客 https blog csdn net qq

  • C++应用之线程池ThreadPool

    include 34 ThreadPool h 34 include 34 StopWatch h 34 include lt thread gt include lt chrono gt include lt iostream gt vo

  • Centeros最小化安装后很多常用命令无法使用（一键安装linux常用命令）

    运行如下命令立即解决问题 最小化安装系统后还会有一些基本的工具没装 xff0c 可采用yum方式批量安装 xff0c 也可以使用哪个安装哪个 yum y install wget setuptool system config firewa

  • 【从零开始的SDN学习之路】之闲话Neutron与SDN的联系

    闲话Neutron与SDN的联系 前言一 OpenStack中的网络发展二 Neutron是不是SDN xff1f 前言 OpenStack作为当前最富盛名的云计算管理工具 xff0c 其服务覆盖了网络 虚拟化 操作系统 服务器等各个方面

  • ESP8266（ESP模块）Arduino开发环境快速搭建方法--含网盘离线文件

    目录 1 ESP8266简介 1 1 乐鑫ESP8266 1 2 安信可ESP模组 2 ESP8266开发 3 开发环境搭建 4 网盘文件离线安装 1 ESP8266简介 1 1 乐鑫ESP8266 乐鑫公司的提供的ESP8266 系列模组

  • 解决Ubuntu虚拟机地无法上网问题

    虚拟机软件 xff1a VMware xff0c 操作系统 xff1a Ubuntu20 04 1 笔者安装好Unbutu20 04 1的虚拟机之后一直遇到一个问题 xff0c 网络图标不显示 xff0c 网络也不可用 每次都要把 虚拟网络

  • python中wraps的详解

    1 name 用来显示函数的名称 xff0c doc 用来显示文档字符串也就是 34 34 文档字符串 34 34 这里面的内容 2 首先我们来看不加 64 wraps的例子 span class token keyword def spa

  • 读书笔记-深度学习推荐系统1-概述章节

    推荐系统充斥于互联网的各个角落 xff0c 听音乐 看视频 看新闻 购物 学习课程等等 1 1 推荐系统的作用 用户 xff1a 在信息过载的情况下 xff0c 帮助用户高效获得感兴趣的信息 公司 xff1a 通过推荐吸引用户留存 增加用户

  • C++算法之——常用算法总结

    基本的C 43 43 算法分为三类 xff1a 排序算法 树算法 图算法 算法思想有三种 xff1a 递推 分治 动态规划 以及 贪心算法 本文将简要介绍上面三类算法 xff0c 介绍时穿插介绍算法思想 一 排序算法 1 基本O n 2 排

热门标签