文档介绍：《算法概论》读书笔记第0章本章较为简短,没有深入系统地涉及某些内容。i数列的例子,让我体会了递归和递推思想的差别。i数列例子直接递归解法中涉及的重复计算,优化出递推方式,展示了思考问题中自顶向下与自底向上的不同思考角度可能产生较大的算法效率差别,同时隐约体现记忆化搜索的思想。另外本章较为详细介绍了大O复杂度度量标准。第1章本章以RSA算法为例,细致深入讨论了RSA算法涉及的相关数论知识,诸如取模运算、模下的四则运算与逆元概念、取模幂运算、素性检测。在素性检测部分有经典的欧几里德算法、扩展欧几里德算法,同时引入随机化算法概念,以极高的概率保证素性检测有效性。通过本章的学****我对过去不曾深入考虑或者说真正考虑的基础性运算有了更深的理解。之前对乘除运算复杂度总是在以单元操作的概念下以O(1)带过,以后会更加细致地考虑乘除等基本运算的复杂度。另外,本章以RSA为案例,系统地展示了针对某一问题,如何从基础性知识入手,一步一步学****案例所需基础知识,并将其整合从而解决案例。素性检测与素因子分解,两个看似相去不远的问题,其复杂性天差地别的现实,从一般角度让人们想到的是类似问题的解决难度可能差别很大仅此而已,而RSA算法展示了如何深入的多想一步,利用这种情况设计出优雅的解决方案。这思想很值得我借鉴与利用。第2章本章介绍分治算法思想,提及分治,相信每一个学****算法的人都不会陌生,经典的《算法导论》中就已合并排序为例在开篇不久就引入分治概念。本书介绍分治的角度与众不同,不似《导论》中总是介绍比较显而易见的可以分治的案例。本书列举了矩阵相乘、快速傅立叶变换等数学领域分治的应用案例,在这些案例之中,分治的应用很多情况下隐藏的较为深,并非显而易见,加大了分析难度。但是更能让我感受到分治应用之广泛,可能在学****本章之前,许多类型的题目我不会想到去向分治的角度思考,因为不易看出,但是本章给我的备忘录上加了一条:永远不要忽视分治,针对陌生题目,不要轻易就否决掉往分治角度思考的路线。另外,通过本章学****对于算法复杂度的评估以及根据递推式评估复杂度的能力有了很大的提高。第3章学****到本章时,发现本章讲解部分只有15页,算上****题也不过20余页,大致翻看内容,发现讲解的是DFS,便松了一口气,自认为作者真逗,一个DFS也用得着单独分出一章来叙述?岂不知市面上的绝大多数算法书,就是将DFS作为搜索或图、树遍历部分的一小节叙述。可是通过两遍的学****总算体会到作者的用心良苦及自己过去对DFS认识的肤浅。DFS无论是递归形式,即使是用栈迭代实现都不太难。但是其精髓我认为在于两方面,一是其在图论中对于连通性、有无环判定等性质判定的应用,另一方面是在DFS中访问顶点的先、后操作函数的实现。这两方面前者主要针对无向、有向图的性质研究,而后者的应用领域可就不能一言概括了,针对现实问题很多都可专门设计具体的先、后操作函数巧妙地利用DFS解决。比较简单而又具有代表性的例子是记录顶点的previsit与postvisit数值应用,这两个数值看似简单但是结合图的特性可谓用处大大,比如postvisit值最小的为汇点、最大的为源点,参考这两个值组成的区间的包含性来判定遍历过程中,某节点是否为根到某一节点路径上的祖先节点等。另外细节部分,拓扑排序和有向图的强连通分量分解思想的相似性研究,值得好好品味。做练****题过程中,能体会到