算法（英文版·第4版）的笔记(28)

我来写笔记

按有用程度 按页码先后 最新笔记

展开收起
第25页 Basic Programming Model

叫什么好呢？ (名字是最短的咒)

如何设计递归？ ①确定基准条件(递归退出条件) ②子问题的规模要比原问题的规模小---递归过程中，处理的问题规模越来越小，且越来越趋近于递归退出条件 ③递归函数处理的子问题不要重叠。如果重叠了，时间复杂度就会很高(指数级)，这也是动态规划解要比递归解更优的一个原因。因为动态规划会把已经计算出来的结果保存到表中，然后查表.....
2016-10-27 15:43:31 2人喜欢
展开收起
环的检测

Steelwings

环的检测的基本思路是使用DFS。但是要分情况看是有向图还是无向图。对于无向图来说，如果在DFS的过程中当前点发现自己的相邻点是已经访问过的且不是到达当前点的点，那么我们就有一个环了。但是对比有向图，却不能用同样的方法。假设我们从圈内的上面的点开始访问，那么圈内的三个点都会被标记为已访问，并且无路可走了。我们只能再从右侧最上面的点开始访问，走到右下角的点，如果往左走去圈内，那是一个已访问的点，我们能...
2017-03-14 20:42:53
展开收起
第191页 1.4 Analysis of Algorithms

z6g

2-sum, brute-force N**2 sort + binary-search N*logN 3-sum brute-force N**3 sort + binary-search N**2 * logN
2019-10-17 23:41:01
展开收起
第129页 1.3 Bags, Queues, and Stacks

z6g

E.K.Dijkstra’s Two-Stack Algorithm for Expression Evaluation 使用双栈表达式求值
2019-10-12 00:04:18
展开收起
第111页算法分析--实验数据的分析

硕666

对数图像的直线的斜率为什么是3？怎么算的？看的？
2019-08-26 01:37:17
展开收起
书上代码是否有逻辑错误？

文明是什么

中文版第462页，高位优先的字符串排序的代码是否有逻辑错误？我照着书中的代码一行一行敲进去，出来的结果是不对的。代码中，在递归调用MSD.sort(String[] a, int lo, int hi, int d)的过程中，如果字符串数组的上界hi和下界lo满足hi<=lo+M(M为小数组的切换阈值)，则进入插入排序，以字符串的第d位为键对字符串数组进行排序，问题就在于，插入排序结束之后，MSD.sort(String[] a, int lo, int hi, int d)函数就直接return了... (3回应)
2019-04-09 15:46:49
展开收起
第108页算法分析

进击的MsCat

是的，我还在基础阶段（表面冷静，内心：阿西吧这本好书要等到什么时候！）科学方法的一条关键原则是我们所设计的实验必须是可重现的，这样他人也可以自己验证假设的真实性。尽管有许多复杂的因素影响着我们对程序的运行时间的理解，原则上我们仍然可能构造出一个数学模型来描述任意程序的运行时间。——一个程序运行的总时间主要和两点有关：执行每条语句的耗时；执行每条语句的频率
2018-04-13 20:13:36
展开收起
拓扑排序

Steelwings

图论以前一直学的不太好，当初英文讲课学习算法，双重复杂度简直就是一脸的懵逼。现在少了英文那一重复杂度，再看这个算法似乎并没有当时那种难以理解的感觉。拓扑排序可以应用在很多方面： * 一些任务是有先决条件的，那么这些任务要怎样安排才能按照各自的要求完成呢？比如要开始A需要B和C，而C又需要D和E等等 * 上学的时候，你修一门课之前要先修基础课程。那么如何安排这个课程也是一个拓扑排序的问题。 * Java类的Inherit...
2017-03-14 10:41:21
展开收起
第504页矩阵运算

Steelwings

又一次看到了这里，直感叹大神的算法真是精妙。如果用array去表示矩阵，那么这个矩阵运算就是O(N^2)的。假设这个matrix是sparse matrix，那大部分位置上都没有值，这么做就是在浪费时间。我们人在做矩阵运算的时候，都是只看有值的部分。那么在编写算法的时候，也可以遵循这样的想法。我只要快速的拿到有值的位置上的值进行运算就OK了。那么如何达到？用一个Symbol Table为基础的Sparse Vector来表示。剩下的事情都迎刃而解了...
2017-03-12 23:07:32
展开收起
Hashing

Steelwings

以前看Hashing这一章的LinearProbing这个方法，总是有点纠结为什么resizing是必须的？我知道因为load factor的缘故如果有太多的element在table里面会导致performance有问题，但是今天仔细读完才发现，原来不这么做，最终的结果就是search miss将处于一个无线循环之中。因为Linear Probing下的search其终止条件是某一个array位置上是null(search miss)或者找到了对应的key。那么如果我们不resize，任凭其发展，最终会出现没地方...
2017-03-11 12:05:22