《算法概论》读书笔记及读后感

《《算法概论》读书笔记及读后感》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法概论》读书笔记12计转112130907李酉辰第0章本章较为简短，没有深入系统地涉及某些内容。主要以Fibonacci数列的例子，让我体会了递归和递推思想的差别。针对Fibonacci数列例子直接递归解法中涉及的重复计算，优化出递推方式，展示了思考问题中自顶向下与自底向上的不同思考角度可能产生较大的算法效率差别，同时隐约体现记忆化搜索的思想。另外本章较为详细介绍了大O复杂度度量标准。第1章本章以RSA算法为例，细致深入讨论了RSA算法涉及的相关数论知识，诸如取模运算、模下的四则运算与逆元概念、取模幂运算、素性检测。在素性检测部分有经典的欧几里德算

2、法、扩展欧几里德算法，同时引入随机化算法概念，以极高的概率保证素性检测有效性。通过本章的学习，我对过去不曾深入考虑或者说真正考虑的基础性运算有了更深的理解。之前对乘除运算复杂度总是在以单元操作的概念下以O（1）带过，以后会更加细致地考虑乘除等基本运算的复杂度。另外，本章以RSA为案例，系统地展示了针对某一问题，如何从基础性知识入手，一步一步学习案例所需基础知识，并将其整合从而解决案例。素性检测与素因子分解，两个看似相去不远的问题，其复杂性天差地别的现实，从一般角度让人们想到的是类似问题的解决难度可能差别很大仅此而已，而RSA算法展示了如何深入的多想一步

3、，利用这种情况设计出优雅的解决方案。这思想很值得我借鉴与利用。第2章本章介绍分治算法思想，提及分治，相信每一个学习算法的人都不会陌生，经典的《算法导论》中就已合并排序为例在开篇不久就引入分治概念。本书介绍分治的角度与众不同，不似《导论》中总是介绍比较显而易见的可以分治的案例。本书列举了矩阵相乘、快速傅立叶变换等数学领域分治的应用案例，在这些案例之中，分治的应用很多情况下隐藏的较为深，并非显而易见，加大了分析难度。但是更能让我感受到分治应用之广泛，可能在学习本章之前，许多类型的题目我不会想到去向分治的角度思考，因为不易看出，但是本章给我的备忘录上加了一条

4、：永远不要忽视分治，针对陌生题目，不要轻易就否决掉往分治角度思考的路线。另外，通过本章学习，对于算法复杂度的评估以及根据递推式评估复杂度的能力有了很大的提高。第3章学习到本章时，发现本章讲解部分只有15页，算上习题也不过20余页，大致翻看内容，发现讲解的是DFS，便松了一口气，自认为作者真逗，一个DFS也用得着单独分出一章来叙述？岂不知市面上的绝大多数算法书，就是将DFS作为搜索或图、树遍历部分的一小节叙述。可是通过两遍的学习，总算体会到作者的用心良苦及自己过去对DFS认识的肤浅。DFS无论是递归形式，即使是用栈迭代实现都不太难。但是其精髓我认为在于两

5、方面，一是其在图论中对于连通性、有无环判定等性质判定的应用，另一方面是在DFS中访问顶点的先、后操作函数的实现。这两方面前者主要针对无向、有向图的性质研究，而后者的应用领域可就不能一言概括了，针对现实问题很多都可专门设计具体的先、后操作函数巧妙地利用DFS解决。比较简单而又具有代表性的例子是记录顶点的previsit与postvisit数值应用，这两个数值看似简单但是结合图的特性可谓用处大大，比如postvisit值最小的为汇点、最大的为源点，参考这两个值组成的区间的包含性来判定遍历过程中，某节点是否为根到某一节点路径上的祖先节点等。另外细节部分，拓扑

6、排序和有向图的强连通分量分解思想的相似性研究，值得好好品味。做练习题过程中，能体会到如果图模型建立好，我能够反应到DFS针对问题的应用，但是关键难点在于根据题目描述如何联想到图模型，但是这不是说看书能够看会的，看来只有多做题慢慢培养这种关联性思维了。第4章本章内容与上一章承接。以BFS为媒介，引出了图论中求解顶点的最短距离相关的一系列算法，诸如Dijikstra算法、Bellman-Ford算法等。由上一章我们知道，DFS的应用一般在于连通分量、结合先、后序操作的算法设计。而BFS的应用一般集中于求解最优化或最短距离方面。在做本章练习题过程中，我更加体

7、会到为什么自己之前看的算法书不少，而提高却总是很慢的原因。光看书确实是不够的，每一本算法书都配以大量的习题确实是十分必要的。也许对于一本算法书，你看了一遍两遍甚至三遍，对于每一章的内容以及例题都已了然，但是没有经过大量题目的思考解答过程，根本谈不上掌握。如何算作掌握了某一算法？许多人会以掌握其设计思想为由搪塞过去，对于算法的细节往往忽略不谈。自己过去也总是效仿这一种做法，仿佛抠细节是愚蠢之人的做法，其实不然。我当然不赞成一味深入细节，但是我们应当知道算法的某一步骤为何这么设计（这往往是显然的），比如在Dijikstra中，当扩展到新的一个节点v，如果有

8、dist[u]>dist[v]+l(v,u)时，要更新u的距离，一般人都不会不懂这个操作的原理