算法导论读书笔记.pdfVIP

算法导论读书笔记

【篇一：《算法概论》读书笔记及读后感】

《算法概论》读书笔记

12计转1李酉辰

第0章

本章较为简短，没有深入系统地涉及某些内容。主要以fibonacci

数列的例子，让我体会了递归和递推思想的差别。针对fibonacci数

列例子直接递归解法中涉及的重复计算，优化出递推方式，展示了

思考问题中自顶向下与自底向上的不同思考角度可能产生较大的算

法效率差别，同时隐约体现记忆化有哪些信誉好的足球投注网站的思想。另外本章较为详细

介绍了大o复杂度度量标准。

第1章

本章以rsa算法为例，细致深入讨论了rsa算法涉及的相关数论知

识，诸如取模运算、模下的四则运算与逆元概念、取模幂运算、素

性检测。

在素性检测部分有经典的欧几里德算法、扩展欧几里德算法，同时

引入随机化算法概念，以极高的概率保证素性检测有效性。

通过本章的学习，我对过去不曾深入考虑或者说真正考虑的基础性

运算有了更深的理解。之前对乘除运算复杂度总是在以单元操作的

概念下以o（1）带过，以后会更加细致地考虑乘除等基本运算的复

杂度。另外，本章以rsa为案例，系统地展示了针对某一问题，如

何从基础性知识入手，一步一步学习案例所需基础知识，并将其整

合从而解决案例。素性检测与素因子分解，两个看似相去不远的问

题，其复杂性天差地别的现实，从一般角度让人们想到的是类似问

题的解决难度可能差别很大仅此而已，而rsa算法展示了如何深入

的多想一步，利用这种情况设计出优雅的解决方案。这思想很值得

我借鉴与利用。

第2章

本章介绍分治算法思想，提及分治，相信每一个学习算法的人都不

会陌生，经典的《算法导论》中就已合并排序为例在开篇不久就引

入分治概念。本书介绍分治的角度与众不同，不似《导论》中总是

介绍比较显而易见的可以分治的案例。本书列举了矩阵相乘、快速

傅立叶变换等数学领域分治的应用案例，在这些案例之中，分治的

应用很多情况下隐藏的较为深，并非显而易见，加大了分析难度。

但是更能让我感受到分治应用之广泛，可能在学习本章之前，许多

类型的题目我不会想到去向分治的角度思考，因为不易看出，但是

本章给我的备忘录上加了一条：永远不要忽视分治，针对陌生题目，

不要轻易就否决掉往分治角度思考的路线。另外，通过本章学习，

对于算法复杂度的评估以及根据递推式评估复杂度的能力有了很大

的提高。

第3章

学习到本章时，发现本章讲解部分只有15页，算上习题也不过20

余页，大致翻看内容，发现讲解的是dfs，便松了一口气，自认为作

者真逗，一个dfs也用得着单独分出一章来叙述？岂不知市面上的

绝大多数算法书，就是将dfs作为有哪些信誉好的足球投注网站或图、树遍历部分的一小节

叙述。可是通过两遍的学习，总算体会到作者的用心良苦及自己过

去对dfs认识的肤浅。

另外细节部分，拓扑排序和有向图的强连通分量分解思想的相似性

研究，值得好好品味。做练习题过程中，能体会到如果图模型建立

好，我能够反应到dfs针对问题的应用，但是关键难点在于根据题

目描述如何联想到图模型，但是这不是说看书能够看会的，看来只

有多做题慢慢培养这种关联性思维了。

第4章

本章内容与上一章承接。以bfs为媒介，引出了图论中求解顶点的

最短距离相关的一系列算法，诸如dijikstra算法、bellman-ford算

法等。由上一章我们知道，dfs的应用一般在于连通分量、结合先、

后序操作的算法设计。而bfs的应用一般集中于求解最优化或最短

距离方面。

在做本章练习题过程中，我更加体会到为什么自己之前看的算法书

不少，而提高却总是很慢的原因。光看书确实是不够的，每一本算

法书都配以大量的习题确实是十分必要的。也许对于一本算法书，

你看了一遍两遍甚至三遍，对于每一章的内容以及例题都已了然，

但是没有经过大量题目的思考解答过程，根本谈不上掌握。如何算

作掌握了