算法导论读书笔记

《算法导论读书笔记》由会员分享，可在线阅读，更多相关《算法导论读书笔记（10页珍藏版）》请在装配图网上搜索。

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

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

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

4、易就否决掉往分治角度思考的路线。另外，通过本章学习， 对于算法复杂度的评估以及根据递推式评估复杂度的能力有了很大 的提高。第3章 学习到本章时，发现本章讲解部分只有 15页，算上习题也不过20 余页，大致翻看内容，发现讲解的是dfs,便松了一口气，自认为作 者真逗，一个dfs也用得着单独分出一章来叙述？岂不知市面上的 绝大多数算法书，就是将dfs作为搜索或图、树遍历部分的一小节 叙述。可是通过两遍的学习，总算体会到作者的用心良苦及自己过 去对dfs认识的肤浅。另外细节部分，拓扑排序和有向图的强连通分量分解思想的相似性 研究，值得好好品味。 做练习题过程中，能体会到如果图模型建立 好，我能够反应

5、到dfs针对问题的应用，但是关键难点在于根据题 目描述如何联想到图模型，但是这不是说看书能够看会的，看来只 有多做题慢慢培养这种关联性思维了。第4章本章内容与上一章承接。以bfs为媒介，引出了图论中求解顶点的最短距离相关的一系列算法，诸如dijikstra算法、bellman-ford算 法等。由上一章我们知道，dfs的应用一般在于连通分量、结合先、 后序操作的算法设计。而bfs的应用一般集中于求解最优化或最短 距离方面。在做本章练习题过程中，我更加体会到为什么自己之前看的算法书 不少，而提高却总是很慢的原因。光看书确实是不够的，每一本算 法书都配以大量的习题确实是十分必要的。也许对于一本算法

6、书， 你看了一遍两遍甚至三遍，对于每一章的内容以及例题都已了然， 但是没有经过大量题目的思考解答过程，根本谈不上掌握。如何算 作掌握了某一算法？许多人会以掌握其设计思想为由搪塞过去，对于算法的细节往往忽略不谈。自己过去也总是效仿这一种做法，仿 佛抠细节是愚蠢之人的做法，其实不然。我当然不赞成一味深入细 节，但是我们应当知道算法的某一步骤为何这么设计(这往往是显 然的)，比如在dijikstra中，当扩展到新的一个节点v,如果有 distu distv+l(v,u)时，要更新u的距离，一般人都不会不懂这个l=J操作的原理。但是我们的思考往往也在这一步停止了。在做书中题 目时，我发现有一类题目，即

7、到某一点的最短距离路径不唯一时， 如何确定？思考了很久，忽然恍然大悟，这不就是 dijikstra 算法中 进行 distu和 distv+l(v,u)过程中，出现 distu = distv+l(v,u)的 情况么？单单是对于一个比较符号的深入思考，我们便有了新的收 获，同时可以将原算法的应用领域扩展一步。如果没有针对题目的 思考，又怎会对算法中一个比较符号的进行分析？又怎会真正体会 一个算法的精巧。.=Jbfs 作为可获得最优解的一种暴力搜索算法，可以用于状态空间搜 索，在这一类应用之中，关键在于状态节点数据结构的设计，以及 分析清楚下一步状态节点扩展所依赖的操作，分析清楚这两点之后， 便

8、可以以bfs实现求解。另外，本章算法的应用领域的抽象建模过程较之第3章dfs部分较 为简单明了。同时应用的灵活性自然也不如dfs。至此经典的暴力搜 索dfs、bfs部分已经结束。=J第5章 本章重点介绍贪心算法。贪心算法并非某一特定的算法，而是一类 算法或者说是一种算法设计思路。针对某一类满足贪心算法适用的 问题背景，我们可以通过每一次都选择当前最优的策略获得最优解。 当然，算法的难度并不在于算法实现，而在于对于贪心算法是否适 用于某一问题的证明，这也是唯一的难点之一。.=J本章重点介绍了贪心算法的经典范例最小生成树算法(kruskal与 prim)，以及huffman编码。另外，引入了数据结

9、构并查集的介绍。 内容较为容易理解，习题难度也不大。第6章 本章内容为动态规划。动态规划作为经典的一类算法设计策略，一 直以来都是各算法书籍的重头戏。类似于贪心算法，动态规划并不 是某一种特定的算法，而是一种设计策略。在算法导论中，作 者以多步决策引入了动态规划概念，同时指出动态规划适用的情况 是问题同时具有最优子结构和重叠子问题的情况。而在算法概论 一书中，作者并没有采用这种传统的介绍方式。本书采用了一种结 构上的抽象，针对动态规划问题的状态对应于节点，而选择转换对 应为边，将动态规划抽象为dag (有向无环图)，从而结合求解最 短路径思想描述了动态规划。动态规划的一般实现形式：记忆化搜索（

10、自顶向下）、递推式自底 向上。本章主要范例为lis、les、背包（单副本、多副本）、矩阵相乘、】 短路及tsp以及独立集。类似之前的章节，在习题中设置了许多范例的变种问题，通过完成习题使我对这些范例的理解更为深刻。总 而言之，动态规划题目千变万化，唯有大量练习培养思维敏感性。第7章本章介绍线性规划。由于之前已经学习过线性规划相关专著，所以 这部分过得比较快。总而言之，这部分内容具有理论上的意义，并 且做为数学规划其他内容时必须掌握的。但是，事实上，实际问题 中建模后，很难出现这种简单的线性规划模式。所以这一章算是数 学规划的一个引言。第8章本章介绍np-完全问题。主要要明确以下概念：能够在多项

11、式时间 判断某一个解答是否是原问题的正确解，则是np问题；而在叩问 题中，若还能在多项式时间内求解出解，则是p问题；若在np问题 中，若不确定能否在多项式时间内求出原问题的解，则是 叩完全问 题。换言之，np问题包含p问题与np-完全问题。所以，许多人不 求严谨，老是说np问题与p问题求解难度不同，实则是想说np-完 全问题与p问题求解难度不同。另外需要明确，所有的np-完全问题 都可以规约为同一个问题。第9章本章承接上一章，针对np-完全问题的难度，提出了一系列不同的解决策略。主要归结为以下几种：智能化搜索（剪枝、分支定界）、 近似算法（退而求其次，不要求一定求得最优解）、局部搜索中的 启发

12、式方法（涉及进化算法和模拟退火）。本章算是起到抛砖引玉 的作用，如何求解np-完全问题一直是研究的热点，由最初的启发式 搜索，包括书中提及的剪枝、分支定界、以及后来的a*算法，到后 来逐步发展的进化算法，虽然一直没有冲破np-完全与p的界限，但 是从不同的思考角度都为我们提供了不少在实践中具有实际应用意 义的解决方法。正如书中所说，判定一个问题为np-完全问题并不是 宣判了该问题的死刑。在np-完全问题的诸多风格的求解方式中，我 们更能体会到算法设计领域的博大精深。第 10 章本章讲解量子算法，虽然理解不深，但是本章着实让我大开眼界。算法概论读书心得算法概论的前身是加州大学伯克利分校和加州大学

13、圣迭戈分校 本科生的算法课讲义。经过十年课堂教学的检验，这本书以其生动 有趣的风格、精心挑选的内容和精确严谨的叙述得到了我的喜爱。 算法是计算机科学的灵魂，其复杂与抽象让许多初学者望而却步。这本书最显著的特点是生动的写作风格：作者贯穿一条主线，以讲 故事的形式将概念娓娓道来，非常易于理解和消化。当然，这本书没有走另一个极端：过分强调语言的生动而忽视了严 谨性。恰恰相反，这本书完美地兼顾了两者。在书中我们看不到很 多数学式子，取而代之的是精确的文字叙述。作者认为这种用严谨 的语言代替数学形式化的方法更容易被学生接受，因为读者需要知 道的往往是蕴涵在数学公式或者程序代码背后的思想，而正是这些 思想

14、促成了精巧的算法。这本书不是一本字典式的百科全书，而是 一本教科书。因此，作者合理地挑选了讲授的内容，用 300 多页的 篇幅使学生对这门博大精深的科学有了深刻的认识本书共分为四 个部分。其中第一部分是引论和算术运算（这是算法的起源），包 括复杂度分析、算术运算、最大公约数、素性测试、散列函数、快 速乘法、递归、合并排序、矩阵乘法，还有在一般算法书中不多见 的 rsa 公钥体制和快速傅里叶变换等内容。第二部分是“传统”的算 法和数据结构（树和图）：图的搜索、连通性、最短路径、最小生 成树、堆、赫夫曼编码等。在第三动态部分里，作者用新颖的方式介绍了两种强大的运筹学算法 规划和线性规划，以及它们的

15、应用。利用这两种运筹学算法，能够 优美地解决一大批实际问题。最后一部分是关于如何解决困难的问 题，包括np完全、优化搜索（回溯、分支限界）、近似算法等。值 得一提的是本书的最后一章量子算法。作者首次将理论研究中 最前沿的内容以通俗易懂的形式写入算法教科书中，给入耳目一新 的感觉。作者以人类最古老的算法（算术运算）为起点，将各种算 法中优美而有代表性的内容囊括书中，并以最前沿的理论结束本书， 构成了完整的知识体系。篇二：算法导论学习报告】算法设计与分析学习报告第一部分 学习内容归纳“计算机算法是以一步接一步的方式来详细描述计算机如何将输入转 化为所要求的输出的过程，或者说，算法是对计算机上执行的

16、计算 过程的具体描述。”（参考文献：百度百科）算法设计与分析是 一门面向设计，在计算机科学中处于核心地位的课程。这门课程主=JlJ要讲授了在计算机应用中经常遇到的问题和求解的方法，分治法、 动态规划法、随机算法等设计算法的基本原理、技巧和算法复杂性 的分析，以及计算理论简介。第一部分“概论和数学准备”在简单了解了算法的基本概念和复杂性、 研究步骤等几个重要知识点后，着重学习了算法的数学基础，包括 生成函数、差方方程的求解等，主要适用于求解算法的时间复杂性。 “任何可以用计算机求解的问题所需要的计算时间都与其规模有关： 问题的规模越小，解题所需的计算时间往往也越短，从而也就比较 容易处理。”（参

17、考文献：计算机算法设计与分析（第 3版） 而第二部分介绍的算法常用技术之首分治法就运用了这样的思 想。分治法的要领在于divide （子问题的划分）-conquer （子问题 的求解）-combine （子问题解的组合）。由于子问题和原问题是同 类的，递归的思想在分治法中显得尤其重要，它们经常同时运用在 算法设计中。这部分内容从select （求第k小元）算法，寻找最近 点对算法和快速傅立叶变换fft等实际应用中深化对分治法思想的理 解，同时也强调了平衡思想的重要性。第三部分“动态规划”与分治法类似，同样是把问题层层分解成规模 越来越小的同类型的子问题。但与分治法不同的是，分治法中的子问题通常

18、是相互独立的，而动态规划法中的子问题很多都是重复的， 因此通常采用递推的方法以避免重复计算。然而，也不是所有的情 况下都采用递推法，当有大量的子问题无需求解时，更好的方式是 采用动态规划法的变形备忘录方法。通常需要用到动态规划法 求解的问题都具有子问题的高度重复性和最优子结构性质两大特征， 这也是我们分析问题和设计算法时的关键点。最长公共子序列lcs问 题和最优二分搜索树就是从动态规划法的两个主要特征角度分析问 题，进而设计出相应的解决算法的。而这部分内容中的另一个问题流水作业调度，则告诉我们采用动态规划时偶尔也得不到高效的算法，我们要学会将已有的知识灵活运用，适当加工。第四部分“集合算法”中

19、首先介绍了一种分析算法复杂度的手法 平摊分析（amortized analysis）。与之前我们所接触的算法分析方 法即逐一考虑执行每条指令所需的时间复杂度再进行累加的方法不 同，平摊分析是对若干条指令从整体角度考虑其时间复杂度，通过 这样的方法获得的时间复杂度更加贴近实际的情况。平摊分析的主 要方法有聚集方法，会计方法和势能方法。聚集方法将指令的时间 复杂度分类计算再相加；会计方法采用了耗费提前计算的思想；势 能方法引入了势函数的概念，从每步操作的数据结构状态和势函数 的关系角度分析得出操作的平摊代价。 “集合算法”这一部分主要分 析了 union （合并集合）和find （给出元素所在集合

20、名）这两种运 算。从上学期的数据结构课程的学习中，我们就已经发现集合 和树之间的关系是密不可分的，我们经常用树结构来表示集合。而 2-3树是一种特殊的每个内结点都只有 2个或3个儿子的树，广泛的 应用于可实现member （查找）、insert （插入）、delete （删除） 操作的数据结构字典，可实现 insert、 delete、 union 和 min（查找最小叶结点）的数据结构可并堆，可实现 insert、 delete、find、concatenate （保序合并）和 split（分裂）的数据结构可连接队列等。之前讨论的算法中每一步计算步骤都是确定的，然而第五部分“随机 算法”中所

21、讨论的随机化算法允许算法在执行的过程中随机的选择下 一个执行步骤。 “在许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此随机化算法可在很大程度 上降低算法的复杂度。 ”（参考文献：计算机算法设计与分析（第3 版）随机化算法对问题用同一输入算法求解时可能会得到完全 不同的效果，这是它的基本特征算法在执行时产生真正随机的 结果。一般情况下，随即算法分为两大类las vegas算法和monte carlo 算法。 las vegas 算法不会得到不准确的结果，但有时 却会找不到解，这时就需要重复调用算法进行计算。而 monte carlo 算法用来求取问题的准确解。它能

22、保证求得一个截但无法保证其正 确性，这是 monte carlo 算法的主要缺点。不过由于每次执行的算法都是独立的，通过反复执行算法可以有效的将发生错误的概率大 大降低。另外，对于一个已经有了平均性质较好的确定性算法的问 题，通过sherwood随机化方法可将确定性算法改成随机算法，以解决其在最坏情况下效率不高的问题，提高了算法的性能。随机化 算法为很多用确定性算法难以很好的解决的难解问题提供了高效的 解决途径，具有很高的实用价值。第六部分“np完全性理论与近似算法”首先介绍了计算模型、确定性 和非确定性图灵(turing)机。“在进行问题的计算复杂性分析之前, 首先必须建立求解问题所用的计算

23、模型，包括定义该计算模型中所 用的基本运算，其目的是使问题的计算复杂性分析有一个共同的客 观尺度。 ”(参考文献：计算机算法设计与分析(第 3 版)随 机存取机ram (random access machine)、随机存取存储程序机 rasp( random access stored program machine)和图灵机(turing machine)是三种基本的计算模型。ram和rasp的相同处 在于都有各种寻址指令且时间复杂性数量级相同，不同处在于 ram 程序的不允许修改和rasp程序的可修改性。ram程序和rasp程序 之间可以相互模拟。图灵机可以计算函数部分的递归函数，涉及到

24、 递归可枚举集、递归集、原始递归集、部分递归函数、完全递归函 数和原始递归函数。确定性图灵机dtm和非确定性图灵机ndtm的 差别在于，ndtm的每一步动作允许有若干个选择，且它的id序列 通常是由树描述的，而dtm的id序列是线性的。这部分接着又进一 步深入介绍 叩完全性理论和解叩难问题的近似算法。np是能在多 项式时间内被一台ndtm所接受的语言。叩完全问题是当前计算机 算法领域的热点研究课题。第二部分 学习心得 学习之初刚开始看到那些函数以及一大堆数学公式的时候都觉得头 大，一时都摸不清这些复杂的式子是用来干什么的，甚至都以为学 的不是算法而是高数了。后来在接触到分治法等算法思想后，在老

25、 师讲解的例子中学会了对那些式子的应用。课后也在实际的应用中 真正掌握了第一部分所讲的数学知识，懂得了那些数学基础对算法 研究的重要性。所以说，只有当自己学会在问题中运用了，才算是 真正学会了那些知识。算法的思想看着都似乎简单易懂，就算思路复杂的只要认真研究也 比较容易理解，但要真正的在实验中、在实际问题的解决过程中运 用出来就不是那么容易的一件事了。对于同一个问题，往往都有好 几种不同的算法，就像要求分别运用kmp、 monte carlo、 las vegas 算法解决同一个问题的实验二一样。 每种算法都有各自的优缺点，需要我们从算法的准确性和时间复杂 度等多个方面进行权衡，从而找到最优的

26、算法。第三部分 个人建议一直以来都习惯于老师用ppt或者pdf课件上课，个人觉得上课看 着屏幕上的 word 文档有点不大适应。特别是刚开始上课讲函数的时 候，那部分知识涉及比较复杂的数学计算，看得比较吃力。所以建 议老师或许可以改用ppt课件作为教学的辅助工具，这样我们课后 打印课件进行复习的时候也会方便一点。另外，对于课后老师布置的实验题，做起来有难度而且很容易出现 错误，耗费了不少时间。我觉得可以专门在机房上几堂实验课，大 家在实验中碰到错误可以及时的请教老师或者和同学讨论。第四部分 报告总结 继上学期数据结构与算法课程的学习后，在算法设计与分析 这门课程中我又更深入的学习了几种算法常用

27、技术，学会了运用这 些典型方法设计算法和反洗算法的效率。将来不管是继续读研还是 工作，对算法的理解和研究都是十分重要的。因此，在今后的学习 和研究中，我也会继续对算法的重视。在最后，也要感谢邓老师继专业导论后对我们这门课的辛苦教授。篇三：算法导论笔记】第一章 算法在计算中的应用第九章 中位数和顺序统计学9.1-1【算法思想】：1. 将数组中的元素分组，每组两个元素，然后比较每组中的两个元素得到最小值，重新得到包含原来一半元素的数组，继续重复上述 过程，那么最后一个元素必然为最小值。如图所示，数组为2, 1, 4, 3, 52. 上述过程形成的是一个二叉树，其中叶子节点都为数组元素，非 叶子节点

28、刚好 4个，这是二叉树的性质。3. 然后我们来找第二小元素，第二小元素必然跟着 1，首先赋值为 5 然后再赋值为3， 然后赋值为2，即为所求。【运行结果】：1我们先将n个数配对，每两个数一对，每对之间进行互相比较得出小值。2.对得出的 n/2 个元素重复第一步，直至得出最小值。到这儿我们得出了最小值，实际上比较的次数为 n-1 次。不难发现 上面的过程实际上可以演示为一个二叉树。例如在 5,8,11,18四个数 找出最小值，二叉树演示如下（每个节点相当于一次比较）：,=Jl=j观察二叉树，可以得出这样一个结论，所有与最小值比较过的数中.=J的最小值纪即为第二小的的值。二叉树的高度为Ign,因此

29、与最小值 比较的数的数目为Ign,在Ign个数中找出最小值要进行lgn-1次比较。 9.1-29.3 节的方法可以在最坏情况下的线性复杂度的算法来求顺序统计量.其核心思想在于获得一个更好的中枢值来更好地划分数组.然而题中 给了我们一个黑盒子来以线性复杂度获取一个真正好的中枢值,那 么再好不过了。在同时找到最大值和最小值时,每个元素都参与了与最大值和最小 值的比较,比较了两次。将数组成对处理。两两互相比较,将大的 与最大值比较,小的与最小值比较。每两个元素需要的比较次数是, 两两比较一次,大者与最大值比较一次,小者与最小值比较一次, 共三次。 9.2-1长度为0的数组，randomized-select直接返回，当然不会递归调用。 9.2-292-3写出randomized-select的一个迭代版本【算法思想】： 递归：在函数中调用自身的程序过程。深度优先。 递归是在函数内 调用本身,迭代是循环求值递推：用堆栈来代替递归要完成的过程。可实现广度优先或深度优 先。迭代：深度是可以预见的，所以不需要递归和递推来实现，直接把 代码嵌套写下去就行。for for for就是典型的迭代。在这里，顺便实现在数组内寻找第i小 的数值。【运行结果】：9.2-4 见书9.3- 19.3- 29.3- 39.3- 49.3- 5