- 博客(99)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 LOCK、ACC、ON、START的含义及正确使用
整体而言，汽车电源状态包括OFF、ACC、CRANK、RUN四个模式，分别对应车辆未通电、附件上电、发动机点火、发动机运行状态。正确的使用这些模式有助于节约能源和保护蓄电池。参考文档：若我的内容对您有所帮助，还请关注我的公众号。不定期分享干活,剖析案例，也可以一起讨论分享。踩完您工作中的所有坑并分享给您，让你的工作无bug，人生尽是坦途。
2024-04-15 18:00:05
985
原创 【案例分析】解决困扰项目半年之久的问题，并让同事对我竖起了大拇指！！！
为了帮助您快速理解问题，我先向您简单介绍一下软件架构（架构以及基础件的设计非常不合理🤕，勿喷！！！我们采用多进程服务方式。不同类型的业务由不同的进程去实现。为了日志分析方便。后续决定将不同进程的log打印输入到同一个文件中。于是就产生了logRcv进程。它的作用就是通过读取共享内存中，来自其它业务线程的日志。将其写入统一的日志文件中。int tail;/** 1.获取共享内存锁*//** 2.将日志写入buf*/
2024-04-07 20:30:47
1083
原创 gdb 环境问题：Backtrace stopped: previous frame identical to this frame (corrupt stack?)
若您与我遇到了相似的问题，不妨试试将以上三个库重新编译一份，替换成具备debug_info,以及not stripped。若依旧不能解决，坚决一点，就是供应商的问题，让他们去解决。若我的内容对您有所帮助，还请关注我的公众号。不定期分享干活,剖析案例，也可以一起讨论分享。踩完您工作中的所有坑并分享给您，让你的工作无bug，人生尽是坦途。
2024-04-06 10:23:40
902
原创 AG35-CEN休眠模式，异常唤醒。问题分析及分享
本主要介绍如何分析 AG35-CEN 模组休眠模式被异常唤醒的分析思路。通过一点点排查，分析。最终定位到是 TCP 协议中 keep alive 机制导致的。令我收获比较大的就是了解到车辆低功耗的整个实现方案，以及遇到相关问题是的大致方向。希望能帮到有需要的朋友。若我的内容对您有所帮助，还请关注我的公众号。不定期分享干活,剖析案例，也可以一起讨论分享。踩完您工作中的所有坑并分享给您，让你的工作无bug，人生尽是坦途。
2024-03-28 21:22:33
690
原创 【案例分析】入职第一天，如何让同事对我刮目相看
确认是进程自己触发crash，还是系统触发。若是程序自己触发，可以通过打开系统的coredump属性，待生成core文件时，进行gdb分析。关于gdb的使用，可以参考我的文章【小白进阶】Linux 调试大法——gdb。（打开程序的调试选项-g和not strip若是系统触发，一般是因为触发了OOM机制。如果内存会随着时间逐步增加，一般就是存在内存泄漏了，最简便的方式就是使用valgrind工具，运行一段时间，查看内存泄漏点；若不是逐步增加，一般是因为某个操作导致的内存急剧增加。
2024-03-24 21:44:55
635
2
原创 一文搞懂系列——可变参数函数实现原理及注意事项
可变参数函数是C语言中常见的特性，允许函数接受数量不定的参数。常见的实现方式是通过va_list系列函数，包括va_startva_argva_end。本文介绍了其实现原理，希望大家能够得到更进一步的理解。不正确使用可变参数，可能会导致程序崩溃（段错误）或其他安全问题。例如，如果调用函数时没有提供足够的参数，va_arg可能会访问非法的内存地址。明确固定参数和可变参数的个数和类型。使用编译器的警告选项（如-Wformat）来检测潜在的问题。在函数调用时提供正确的参数数量和类型。
2024-02-22 18:17:10
643
原创 案例分享：进程如何加载相同库的不同版本
本文分享了工作中的一个案例，由于历史原因。我们不得不在一个进程中采用两个不同的版本的相同算法库。识别到了潜在问题：符号重定义、全局符号介入、如何指定版本符号。并从理论与实践上分析解决。更深入了解运行时模块加载的好处与特殊场景。若我的内容对您有所帮助，还请关注我的公众号。不定期分享干活,剖析案例，也可以一起讨论分享。踩完您工作中的所有坑并分享给您，让你的工作无bug，人生尽是坦途。
2024-02-19 18:37:44
1101
原创 vsCode无法连接服务器问题解决及思考
虽然问题最终是通过更新虚拟机镜像版本得以解决。但是前面走了很多弯路。我的感受就是：遇到问题，我们的第一反映则是百度搜索，查看是否解决方法，然后按照他人的操作，执行一遍，看是否能解决。如果不行，继续百度，继续做尝试。这样的方式，在大多数情况下，可能会很快的帮助我们解决问题。但是当你经历多次盲目的尝试，并且失败后。我们应该静下心来自己进行问题分析，可能会有意想不到的发现。多思考，多发现。若我的内容对您有所帮助，还请关注我的公众号。不定期分享干活,剖析案例，也可以一起讨论分享。
2024-02-05 14:38:44
2100
原创 安卓平台valgrind交叉编译
本文主要讲述了在Android平台使用ndk23交叉编译工具链编译valgrind时遇到的问题及解决方法。主要问题包括不支持Android系统、结构体重复定义、无法找到libgcc.a库以及32位工具编译失败等。作者首先尝试通过修改configure参数和解决依赖问题来解决问题，但在目标机调试时仍然遇到断言错误。随后，作者尝试使用gcc编译而非clang，并找到了一个早期版本的ndk14，最终成功编译并调试了valgrind。有时换一个思路，也许会让你柳暗花明又一村，拥有意外收获。
2024-02-04 15:50:23
1368
2
原创 一文搞懂系列——非局部跳转setjmp和longjmp使用及原理
本文向大家介绍了非局部跳转函数setjmp和longjmp的使用方式，以及实现原理。即使它的存在，有很多不好的影响。但是在特定场景下还是能够体现它的价值。比如异常处理，实现C语言的异常捕获和协程。但是还是希望大家谨慎使用，按需设计。若我的内容对您有所帮助，还请关注我的公众号。不定期分享干活,剖析案例，也可以一起讨论分享。踩完您工作中的所有坑并分享给您，让你的工作无bug，人生尽是坦途。
2024-01-25 16:04:02
1019
2
原创 【程序员的自我修养11】栈与函数调用过程
首先我们来看一张Linux进程中经典的内存布局图：内核空间：是操作系统内核运行的区域，它是内核中一个重要的部分，专门为内核以及与内核直接相关的操作和进程提供服务。用户空间无法直接访问内核空间。栈栈用于维护函数调用的上下文。离开了栈，函数调用就无法实现。栈通常在用户空间的最高地址处分配，通常大小为8M。往地址方向生长。堆：堆是用来容纳应用程序动态分配的内存区域，当程序使用malloc或new分配内存时，得到的内存来自堆里。往高地址生长。动态库：用于程序运行时，动态链接器或在程序运行过程中通过。
2024-01-16 11:30:17
540
1
原创 一文搞懂系列——Linux C线程池技术
实际上，我觉得在诊断项目中，线程池技术是非必要的。因此它不会涉及到大量的请求，以及每一个请求处理，一般都会比较耗时。参考：https://www.cnblogs.com/zhaoosheLBJ/p/9337291.html。
2024-01-15 21:09:36
1115
2
原创 【程序员的自我修养10】动态库的兼容问题——GLIBC_2.34‘ not found
前几章，花了较大篇幅介绍了动态库链接过程原理，需要面对的场景以及解决思路，真真切切的了解到动态库的优秀之处。这就导致大量开始程序使用动态链接。随着系统中的动态库越来越多，也会出现一些问题。本文介绍动态库的发展过程中遇到的问题，以及如何解决的。以及非常好用的调试tips。本文花了较大篇幅介绍了动态库如何解决和避免兼容性问题，以及分享两个分享实用的环境变量LD_PRELOADLD_DEBUG，至此关于动态库的分享算是结束了。下一章节，我们开始向《库与运行库》进军。若我的内容对您有所帮助，还请关注我的公众号。
2024-01-10 20:53:05
1677
2
原创 【程序员的自我修养09】动态链接过程的场景补充及其思考
通过上一篇【程序员的自我修养08】精华！！！动态库的由来及其实现原理,大致介绍了动态链接的历史背景，以及通过示例进一步了解当今动态库的实现过程。由于篇幅有限，所以针对一些特殊场景和动态库链接的过程没有进一步展开描述。本文主要作为上文内容的补充。本文是对上篇文章的补充，讲解了共享模块中全局变量的处理方式，以及如何实现共享模块中数据段的地址无关性。共享对象全局符号介入。坑惨啦！！！——符号冲突案例分析若我的内容对您有所帮助，还请关注我的公众号。不定期分享干活,剖析案例，也可以一起讨论分享。
2024-01-04 09:15:33
905
1
原创 【程序员的自我修养08】精华！！！动态库的由来及其实现原理
通过前文的讲解，我们大致了解将程序加载到内存的过程。程序与虚拟内存空间映射表虚拟内存空间与物理内存映射表。之后在程序运行过程中，通过不断触发页错误，持续将相应程序页加载到内存中，从而保证进程正常运行。似乎一切都已经完备了。的确，在早期的程序开发中，源文件经过编译生成可重定位文件（.o文件），再经过静态链接生成可执行的ELF文件，最终运行时，通过页加载和页错误的方式，保证进程的正常运行。已经能够满足当时程序的研发，大家开发和使用都非常方便。但是随着IT行业的发展，原先静态链接方式的缺点也逐渐显露。
2024-01-03 09:13:10
1055
原创 【程序员的自我修养07】程序的装载过程——小内存如何运行大程序
经过前几篇文章的介绍，我们已经大致了解多个源文件如何编译生成可执行文件的过程。但是程序只有放在内存中才能被CPU执行，本章节向大家介绍,如何程序加载到内存中的过程。小内存如何运行大程序？本文讲述了程序加载到内存的步骤，其实质就是建立两个映射。一、虚拟空间和物理内存的映射关系；二、虚拟空间和程序的映射关系。进程运行过程中通过不断触发页错误，将程序中的页加载到内存中。从而解释了小内存运行大程序的原理。本文介绍了静态链接过程一些特殊场景和优化项。希望大家能够结合自己的实际工作，应用起来。
2024-01-03 09:11:42
990
原创 valgrind跨平台调试及其问题分析
本文介绍valgrind跨平台的调试及应用过程，主要目的是想和大家分享遇到问题是的分析思路，如何一步步推荐，最终达到目的。再结合内存泄漏问题分析思路（案例篇）和快速定位内存泄漏的套路两篇文章，我相信内存泄漏，对于你而言，应该不再是令人头疼的问题了。若我的内容对您有所帮助，还请关注我的公众号。不定期分享干活,剖析案例，也可以一起讨论分享。踩完您工作中的所有坑并分享给您，让你的工作无bug，人生尽是坦途。
2024-01-02 20:58:34
1110
2
原创 一文搞懂系列——替换动态库，为什么导致运行进程异常
至此，该问题终于解决了。内容较多，希望大家有所收获。在知道根因后，我们不妨再想想，如何在程序运行时，替换动态库，却不影响正在程序。提示：先删除，再拷贝。即。不妨试试哦，可以把原理在评论区写出。若我的内容对您有所帮助，还请关注我的公众号。不定期分享干活,剖析案例，也可以一起讨论分享。踩完您工作中的所有坑并分享给您，让你的工作无bug，人生尽是坦途。
2024-01-02 09:48:59
1232
4
原创 【工具】stress-ng 压力测试环境模拟及分析
stress是一个linux的压力测试工具，专门用于对设备的CPU、IO、内存、负载、磁盘等进行压测。另一个版本是其升级版本stress-ng。在模拟io_wait性能场景时，stress一直表现不好，本文以stress-ng为例，进行介绍。stress-ng工具，在性能测试，或压力测试场景，是一个很实用的工具。希望大家能够掌握基本用法。若我的内容对您有所帮助，还请关注我的公众号。不定期分享干活,剖析案例，也可以一起讨论分享。踩完您工作中的所有坑并分享给您，让你的工作无bug，人生尽是坦途。
2023-12-21 14:58:05
1157
2
原创 cpulimit设计理念及其思考
以上便是的初步设想，后续有时间会进行代码验证，有兴趣的朋友可以关注哈。若我的内容对您有所帮助，还请关注我的公众号。不定期分享干活,剖析案例，也可以一起讨论分享。踩完您工作中的所有坑并分享给您，让你的工作无bug，人生尽是坦途。
2023-12-20 22:05:44
1116
3
原创 一文搞懂系列——DBC数据库信号解析规则及案例
DBC是vector公司定义的can网络通信文件格式。网上介绍的文章很多，有兴趣的朋友可以去搜索一下。本文的主要核心是解析DBC信号部分，对于相关信息进行简略描述。版本与新符号波特率定义网络节点的定义报文帧的定义信号的定义注解部分特征部分数值表部分格式为含义如下：。BU_为关键字，表示网络节点；表示网络节点名字，由用户自己定义。通过网络节点方便地进行CAN网络的设计、开发和测试。如下：格式为BO_,为关键字，表示报文；MessageId,报文ID，是以10进制数表示的。
2023-12-18 21:55:25
2137
4
原创 【程序员的自我修养06】静态链接过程的思考
经过前两章的介绍，我们应该大致掌握了.o文件静态链接为可执行文件的过程。相同的符号定义在多个源文件中，符号解析流程是如何处理方式的呢？无用代码是如何处理的呢？链接的过程，可以控制函数初始化的过程吗？本文则进一步分析,探讨上述几个问题，希望能够给你的工作带来帮助。我们知道不同的.o文件在链接之前是不知道其它.o文件的内容，因此它们之间若存在相同的符号，也是只有在链接阶段才能发现。若链接器发现同一个符号有多处定义，它又是如何处理的呢？两个或两个以上强符号；
2023-12-14 15:44:14
1127
4
原创 【程序员的自我修养05】符号修正的功臣——重定位表
在上篇文章【程序员的自我修养04】目标文件生成可执行文件过程空间与地址分配符号解析和重定位。建议读者看一遍上文，方便理解本章内容。在上篇文章的最后，并提出了一个思考题：链接器是如何知道哪些符号需要被修正的呢？从上文中，我们知道对外部引用的符号或变量，目标文件暂时会设置成0，待符号分析完成后，可执行程序已经确认其真实的虚拟地址，再进行修正。我们是否可以根据变量值是否为0来进行修改正呢？这样的思路，对于函数引用好像是可以的，毕竟没有哪个函数的地址是0吧。
2023-12-13 17:39:07
1019
2
原创 【程序员的自我修养04】目标文件生成可执行文件过程
在前两章的内容中，我们已经了解目标文件的基本布局以及部分局部细节，单独的可执行文件并没有什么实际作用。我们需要多个目标文件链接成可执行文件，或生成动态库。接下来的几章，我会详细介绍目标文件链接成可执行文件的过程，希望大家能够坚持，坚持必有所获。本章节概述了目标文件链接成可执行文件的过程。由如何合并多个目标文件开始，了解到相似段合并的优点。空间与地址分配符号解析和重定位。并用示例分析其过程。内容较多，希望读者能够自己本地操作一遍，认真思考，推敲。若有疑问，也可与我沟通。
2023-12-12 20:27:14
1129
3
原创 一文搞懂系列——字节对齐的前因后果及应用
通过同事偶然间遇到的一个问题，深入剖析，了解到字节对齐前因后果。也给我们警示结构体定义需要满足编译器的规则，否则可能会大量浪费内存空间。在跨平台开发过程中，我们也要考虑结构体成员long数据类型在不同平台的变化。当然也有可能会因为编译器的不同，其它基础数据的自身对齐值，也会发生变化。定义结构体成员变量时，考虑跨平台的情况。对外提供的头文件，可以通过强制设置自身对齐值。若我的内容对您有所帮助，还请关注我的公众号。不定期分享干活,剖析案例，也可以一起讨论分享。
2023-12-11 17:39:10
634
2
原创 一文搞懂系列——你真的了解如何生成动态库了吗？
本文从两个实际存在的场景，向大家介绍了动态库生成过程中的一些特定需求。简单介绍了和两个链接属性及使用方式。。有兴趣的朋友可以了解一下。若我的内容对您有所帮助，还请关注我的公众号。不定期分享干活,剖析案例，也可以一起讨论分享。踩完您工作中的所有坑并分享给您，让你的工作无bug，人生尽是坦途。
2023-12-07 16:50:28
1047
1
原创 daemon和pthread_create之间的问题（线程阻塞）
这样就导致，463编译的软件，调用之后daemon之后，主线程就直接退出了，当我们调用pthread_create函数之后，会发唤醒消息给pthread_initialize记录的pid线程时，让他继续执行。首先第一点，我们之前一直听过一句话，main函数是程序的入口，其实并不是的。最近完成工具链和uClibc库升级的任务，升级之后出现了一个bug，就是大软件起来之后，原先ps能看到6个线程的进程，现在只能看到三个，导致出现了一些功能上的问题。综上所述，用了新的工具链之后出现问题，主要的原因是由于，
2023-12-05 16:24:08
874
1
原创 一文搞懂系列——动态库的加载方式及应用场景
我们从输出结果，可以知道，动态链接器只加载/etc/ld.so.cache配置文件，并没有加载/etc/ld.so.conf配置文件。-Wl,-rpath是编译阶段修改可执行程序的rpath参数，但是往往我们在工程中是不太确认最终的集成路径的。我们只需要将动态库放到对应的路径下即可。我们在工作中经常会遇到动态库链接的问题，因为正常的方式并不能满足我们的场景。知道可执行程序依赖哪些动态库口，动态链接器就需要去找这些动态库，查找的方式主要有以下四种。是我们最最常用的方式，大部分情况下，我们使用该方式即可。
2023-12-04 14:16:19
1154
4
原创 程序员的养生之道：远离猝死、脱发、身体虚的尴尬人生
因此，我们要合理安排运动时间，每天至少进行30分钟的有氧运动，如散步、跑步、游泳等。此外，还可以进行一些针对性的锻炼，如瑜伽、拉伸运动等，以缓解长时间坐姿带来的身体不适。所以，我们要尽量保持规律的作息，白天高效工作，晚上按时入睡。因此，我们要确保每天摄入足够的水分，保持身体水分充足。在工作之余，可以和朋友聚会、旅行，或者培养一些兴趣爱好，如摄影、画画等，以释放压力。在休息时间里，可以进行一些轻松的活动，如散步、喝水等，以缓解大脑疲劳。在这场较量中，我们要充分利用有限的时间，提高工作效率，同时保证身体健康。
2023-12-01 09:38:51
472
3
原创 程序员的吐槽
这位程序员的职场经历，让我们看到了一个平凡人在职场中的成长与奋斗。在这个过程中，他吐槽过、抱怨过，但最终还是选择勇敢面对，寻求改变。他的故事告诉我们，职场中的困境和挑战是每个人都会遇到的，关键是如何应对。只有调整心态，不断提升自己，才能在职场中取得成功。而对于领导和同事，我们也要学会理解和包容，努力打造一个和谐的工作氛围。如此，才能共同促进公司的发展，实现个人和团队的共赢。
2023-11-30 18:40:42
840
原创 【程序员的自我修养03】深入了解ELF文件格式
我们知道链接器在处理目标文件时，需要对目标文件中某些部位进行重定位，即代码段和数据段中哪些绝对地址的引用需要修改。我们知道不同文件间对函数、变量之间的引用，其实就是对符号的引用。之后再介绍常见的段，代码段，数据段，bss段，符号表等内容，以及工作中可以借鉴的地方。：用16进制打印了.text、.data、.rodata、.comment、.eh_frame段的信息，其长度与段表中显示的长度是一一对应的。综上所述，我们基本已经了解了ELF文件格式的布局，接下来，我们尝试深入了解各个段的内容。
2023-11-30 18:05:38
1376
原创 【程序员的自我修养02】初识ELF文件格式
正如其专栏名，本专栏主要分享学习《程序员的自我修养——链接、装载与库》的知识点以及结合自己的工作经验以及思考。若你希望与一群志同道合的朋友一起学习，也希望加入到我们的学习群中。本章介绍了linux平台下可重定位文件，动态库文件，可执行文件的存储格式都是ELF类型。也欢迎加入我们的讨论组群。它与目标执行平台大小端无关，它的作用是告诉目标执行平台，本文件的代码段，数据段的存储方式，用于解析。下一章，我们再通过了解段表，更进一步了解ELF文件的内容布局。可执行文件的入口地址在文件的偏移0x540地址。
2023-11-30 10:23:02
1261
2
原创 【面试心经】——上海广升智能科技有限公司
我们用户一般只能访问用户态的功能，不可以直接访问内核态。其实这个是不正确的，若了解过编译原理，main和其它函数并无特殊的地方，在最终的可执行文件中，都是一个符号而已。在计算机系统中，程序使用的地址是逻辑地址，而物理内存的地址是实际的硬件地址。2>&1 ，表示将错误输出指向标准输出指向的文件表项，此时标准输出指向的是终端，故错误输出指向的还是终端。解析：shell解释是从左往右的，command默认的标准输入，标准输出，错误输出是终端。首先这两个对应的是两个方面，进程对应的是存储资源，线程对应的计算资源。
2023-11-29 15:43:42
951
原创 【面试心经】——蔚来汽车Linux 岗位开发 02
第四次挥手：客户端收到从服务器端发出的TCP报文，确认了服务器端已做好释放连接的准备，于是再次向服务端发送报文表示接收到服务端准备好释放连接的信号，并进入TIME-WAIT阶段等待2MSL ( 最大报文生存时间) 后再断开连接，服务端收到最终确认报文后立即断开连接，双方断开TCP连接。第三次挥手：服务端自从发出ACK确认报文之后，经过了关闭等待阶段，做好了释放服务器端到客户端方向上的连接准备，再次向客户端发出一段TCP报文表示已经准备好释放连接了（没有数据需要传输给客户端了），然后进入最后确认状态。
2023-11-29 11:33:21
1189
原创 【面试心经】——蔚来汽车Linux 岗位开发01
优点：我们可以看到使用共享内存进行进程间的通信真的是非常方便，而且函数的接口也简单，数据的共享还使进程间的数据不用传送，而是直接访问内存，也加快了程序的效率。同时，它也不像匿名管道那样要求通信的进程有一定的父子关系。它也是一种半双工的通信方式，但它允许无亲缘关系进程间的通信。缺点：共享内存没有提供同步的机制，这使得我们在使用共享内存进行进程间通信时，往往要借助其他的手段来进行进程间的同步工作。在多个进程同步访问一个给定存储区时，若服务器进程正在将数据放入存储区，则在它做完之前，客户进程不应该去取这些数据。
2023-11-29 11:29:21
958
原创 【小白进阶】Linux 调试大法——gdb
设备里面可能同时运行多个应用，不同的应用可能都会发生crash，若core文件名不做特殊识别，可能无法在多个core文件中，找到我们需要的那一个。作为后端开发工程师，gdb 调试是必备技能，这个技能应该是一个能力集，不仅仅是会几个gdb 调试指令即可，而是在这个过程中，遇到任何问题，都应该能够独立分析解决。我想说的是，这点能力是完全不够的，身边一些同事稍微遇到一点问题，就不知道如何进行调试了。coredump是将程序崩溃的那一刻的内存进行快照，因此越占用内存的进程，其生成的core文件，也就会越大。
2023-11-28 16:07:53
1736
2
原创 深思：C与C++相互调用问题
简单沟通下，才知道他遇到了一个工程编译的问题，一直无法编译通过，困扰了他快一天时间。在历史的长河中，先辈们发现随着项目工程的扩大，很容易出现不同模块定义了相同的全局变量或对外函数，导致符号相同的情况。我相信有经验的朋友肯定已经知道问题的原因了，但是对于未接触相关案例的同学，估计还是一头雾水，特别是一直从事C语言开发的工程师，估计还不清楚发生了什么。，因此会导致C++ 认知中A.h 的符号与 A.o的实际符号不匹配，虽然动态库libB.so 已经能生成，但是在链接阶段，符号重定位时，就会出现。
2023-11-27 17:09:32
1217
原创 【程序员的自我修养01】编译流程概述
在大型的工程项目中，随着需求的迭代代码分支也比较多，经常会用到类似"if"、"#ifdef"、"#elif"、"#else"、"#endif" 等分支控制方式。答：我们在工作中，经常会遇到一些问题，需要查看动态库的信息，比如查看依赖库，反汇编，甚至是gdb调试。以上便是本文的内容，我们回顾了编译的四大过程：预处理，编译，汇编，链接。在一般应用中，不会逃逸的局部对象所占用的比例很大，如果能在编译器优化时，为其在栈上分配内存空间，那大量的对象就会随着方法结束而自动销毁了，也欢迎加入我们的讨论组群。
2023-11-25 18:04:59
1165
原创 【追求卓越13】算法--深度和广度优先算法
对于有向图，如果顶点i到顶点j之间，有一条从i指向j的边，我们就将Array[i][j]置为1；假设图的顶点个数是V，边的个数是E。*对于访问过的顶点，我们不再处理，因为广度优先算法是按层搜索的，即使遇到访问过的顶点，那一定不是最短路径，故可以忽略*空间上的消耗主要是queue，prev,visit三个数组，但它们的长度不会多于V，故空间复杂度是O(V)之前我学习算法图解的时候，我写过一个广度优先算法的程序，只不过当时并没有说明图的概念，完全用数组来实现。比如，图中的A，B，C，D，E,F六个顶点。
2023-11-22 16:46:25
922
原创 【追求卓越12】算法--堆排序
建堆的时间复杂度是O(n),排序的时间复杂度是O(nlogn)（实际上应该是logn+log(n-1)+log(n-2)+...+log(1),这里方便，我们记录为O(logn)）。故插入第一个数据的消耗的时间为log1,第二个数据消耗的时间为log2...以此推测，第n个数据消耗时间为logn。堆化的过程，其实也简单，只要循着插入节点，向上对比，进行交换即可。假设每个元素都需要进行插入，那么就是堆化n个元素，堆化的时间复杂度是O(logK),故使用过堆求top K的问题，其时间复杂度是O(nlogk)。
2023-11-22 16:42:37
903
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人