《算法概论》读书笔记及读后感 (2).docx
版权申诉
65 浏览量
2023-03-05
13:39:30
上传
评论
收藏 33KB DOCX 举报
-----WORD 格式--可编辑--专业资料-----
《算法概论》读书笔记
12 计转1 12130907 李酉辰
第 0 章
本章较为简短，没有深入系统地涉及某些内容。主要以Fibonacci 数列的例子，让我体会了递归和递推思
想的差别。针对Fibonacci 数列例子直接递归解法中涉及的重复计算，优化出递推方式，展示了思考问题中自
顶向下与自底向上的不同思考角度可能产生较大的算法效率差别，同时隐约体现记忆化搜索的思想。另外本章
较为详细介绍了大O 复杂度度量标准。
第 1 章
本章以RSA 算法为例，细致深入讨论了RSA 算法涉及的相关数论知识，诸如取模运算、模下的四则运算
与逆元概念、取模幂运算、素性检测。
在素性检测部分有经典的欧几里德算法、扩展欧几里德算法，同时引入随机化算法概念，以极高的概率保
证素性检测有效性。
通过本章的学习，我对过去不曾深入考虑或者说真正考虑的基础性运算有了更深的理解。之前对乘除运算
复杂度总是在以单元操作的概念下以O（1）带过，以后会更加细致地考虑乘除等基本运算的复杂度。另外，
本章以RSA 为案例，系统地展示了针对某一问题，如何从基础性知识入手，一步一步学习案例所需基础知识，
并将其整合从而解决案例。
素性检测与素因子分解，两个看似相去不远的问题，其复杂性天差地别的现实，从一般角度让人们想到的
是类似问题的解决难度可能差别很大仅此而已，而RSA 算法展示了如何深入的多想一步，利用这种情况设计
出优雅的解决方案。这思想很值得我借鉴与利用。
第 2 章
本章介绍分治算法思想，提及分治，相信每一个学习算法的人都不会陌生，经典的《算法导论》中就已合
并排序为例在开篇不久就引入分治概念。本书介绍分治的角度与众不同，不似《导论》中总是介绍比较显而易
见的可以分治的案例。本书列举了矩阵相乘、快速傅立叶变换等数学领域分治的应用案例，在这些案例之中，
分治的应用很多情况下隐藏的较为深，并非显而易见，加大了分析难度。但是更能让我感受到分治应用之广泛，
可能在学习本章之前，许多类型的题目我不会想到去向分治的角度思考，因为不易看出，但是本章给我的备忘
录上加了一条：永远不要忽视分治，针对陌生题目，不要轻易就否决掉往分治角度思考的路线。另外，通过本
章学习，对于算法复杂度的评估以及根据递推式评估复杂度的能力有了很大的提高。
第 3 章
学习到本章时，发现本章讲解部分只有15 页，算上习题也不过 20 余页，大致翻看内容，发现讲解的是
DFS，便松了一口气，自认为作者真逗，一个 DFS 也用得着单独分出一章来叙述？岂不知市面上的绝大多数
算法书，就是将 DFS 作为搜索或图、树遍历部分的一小节叙述。可是通过两遍的学习，总算体会到作者的用
心良苦及自己过去对DFS 认识的肤浅。
DFS 无论是递归形式，即使是用栈迭代实现都不太难。但是其精髓我认为在于两方面，一是其在图论中
对于连通性、有无环判定等性质判定的应用，另一方面是在DFS 中访问顶点的先、后操作函数的实现。这两
方面前者主要针对无向、有向图的性质研究，而后者的应用领域可就不能一言概括了，针对现实问题很多都可
专门设计具体的先、后操作函数巧妙地利用DFS 解决。比较简单而又具有代表性的例子是记录顶点的previsit
与 postvisit 数值应用，这两个数值看似简单但是结合图的特性可谓用处大大，比如postvisit 值最小的为汇点、
最大的为源点，参考这两个值组成的区间的包含性来判定遍历过程中，某节点是否为根到某一节点路径上的祖
先节点等。
另外细节部分，拓扑排序和有向图的强连通分量分解思想的相似性研究，值得好好品味。
做练习题过程中，能体会到如果图模型建立好，我能够反应到DFS 针对问题的应用，但是关键难点在于根据
题目描述如何联想到图模型，但是这不是说看书能够看会的，看来只有多做题慢慢培养这种关联性思维了。
第 4 章
本章内容与上一章承接。以 BFS 为媒介，引出了图论中求解顶点的最短距离相关的一系列算法，诸如
--完整版学习资料分享----
资源评论
不吃鸳鸯锅
- 粉丝: 8346
- 资源: 2万+
最新资源
- Matlab基于PCA算法的简单图像人脸识别.zip
- 免费的画图工具drawio，可以代替visio，版本24.5.3，适用于windows
- 瑞昱RTL8723DS-WiFi-linux- android 驱动 内含详细移植说明，支持android4.4
- AMSR/ADEOS-II L1A Raw Observation Counts, Version 3用户手册
- zaopingshujufenxi.zip
- 六级作文模板万能句型pdf.zip
- delphi 12 控件之DISQLite3 v5.48.3 for Delphi 11-12 Athens + CRACK.7
- Delphi 12 控件之DIXml v6.3.1 for Delphi 11-12 Athens + CRACK.7z
- Delphi 12 控件Mitov Software MegaLab 8.0 for D12 Athens Source Cod
- Delphi 12 控件之Delphi-WinTaskSched-master.zip
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
