算法设计与分析基础（第3版）读书笔记（及几处翻译上的错误~~）
浏览数：18 /
时间：2015年06月08日
算法设计与分析基础（第3版）
- p16 in-place翻译为‘在位’？‘就地’更合适点
- p38 amortized应翻译为‘均摊’，‘摊销’这个词简直莫名其妙（可能因为翻译是做算法交易导致的？）
- p64 迭代优于递归（迭代始终是增量式的，而递归就没办法增量了，除非能够dump整个运行时栈）
- p73 通过算法可视化得到一个更好的非递归算法（人的图像认知直觉思维？）
- p79 验证一个拓扑是环、星、还是团？（这个地方有点意思，因为我想到了动态的Verify）
- p87 凸包问题：从数据结构上讲，Set<LineSegment> --> SortedList<Point>
- p92 解决分配问题的匈牙利方法（Konig & Egervary）？妈的，书里没详谈
- p97（无向图？）DFS对应树边和回边，而BFS对应树边和叉边。
- p112 生成排列：Johnson-Throttler算法（本书最大的优点是算法都带了人的名字，哈）
- p115 习题4 HeapPermute
- 这个伪码算法有点难于理解，我记得标准的写法似乎不是这么写的吧？
- p119 ‘every second’被翻译为“每次第二个”，似乎翻译为“偶数编号的”更合适点
- p122 Lomuto划分：这好像就是Steven S.Skiena的《算法设计手册（第2版）》中的快速排序使用的版本，事实上还是有点技巧的
- p124 一种更加复杂的算法，用于在快速排序中选出pivot，在最坏情况下也能保持线性时间效率？？？
- p127 Nim游戏：此处印刷有错误，应为“正好加到100”
- p132 主定理：此定理的形式不正确，应该去看Sara Basse的《计算机算法》（这本书2001年的，怎么始终没更新了？）
- p137 快速排序（HoarePartition）：由于两边的扫描遇到==的情况都会停止，此时相当于A[i]==A[j]
- p138 当i>=j时撤销最后一次swap？靠
- p140 ‘world‘s leading expert’翻译成了‘权威’，靠
- p147 Strassen算法最难的是记住这7个子矩阵相乘的公式吧
- p149 最近对：先递归得到d（实际上这里很有意思）；然后根据d分治处理边界情况
- 处理边界：数据的局部性约束减少了问题的排查规模
- p151 凸包/快包：这里直线左侧/右侧的说法很莫名其妙
- p155 reduction我喜欢翻译为‘归约’，而不是‘化简’
- p159 问题10：注意这里结果的点集是两两不可比较的（x1>x2但y1<y2）
- p162 部分选主元：避免了大数相减造成的误差（此误差又被作为了除数，导致误差被放大）
- p166 注意，行列式的完全展开中，每一项的正负号依赖于行列下标的差值之和
- p171 AVL树在Mark Allen Weiss的《数据结构与算法分析》一书中讲得很好
- p174 2-3树：这里我怎么没办法理解，2-3树始终高度平衡的吗？似乎存在2种内节点。。。
- p190 线性规划/单纯性：只有概念上的描述
- p195 整数线性规划（ILP）是NPC的吧？
- p201 Horspool是BM的简化版（本书为什么不谈KMP？不过BM确实比KMP要更复杂一点）
- p204 本书讲解Boyer-Moore比较详细，值得仔细看看（KMP考虑了模式内部的重复，但它是前缀匹配；但BM考虑了字母表的规模）
- p220 动态规划：DP最经典的例子是“编辑距离”
- p226 为了设计一个动态规划算法，需要推导出一个递推关系
- p230 最优BST：有点复杂。。。
- p243 贪心：每一步选择必须满足3个条件：可行、局部最优、不可取消（？）
- p248 Prim算法的正确性证明，不错
- p259 Fibonacci堆实现优先队列：‘只具有理论价值’？
- p263 动态Huffman树？有意思
- p266 迭代改进？快速迭代 + 增量改进
- p270 单纯形：极点不是最优解时，处理下一个邻近的（这里似乎可以使用某些随机梯度下降之类的状态空间检索技术）
- p275 单纯形的增量过程可能是不稳定的
- p276 椭球法/Karmarkar算法（内点法？）
- p279 最大流：记住2个名词，增广路径 和 预流推进，哈
- p285 预流推进不属于迭代改进，因为它并没有在满足约束的前提下生成一系列渐进最优的解
- p286 更先进的最大流：Dinitz、Karzanov、Malhotra-Kamar-Maheshwari、Goldberg-Tarjan
- me：不如直接去阅读网络优化方面的数学专著好了 -_-
- p291 提升效率：把多次迭代在一个阶段完成（Batch？）
- p291 加权的二分图最大匹配：这个应该是非常复杂的算法了，靠
- p293 稳定婚姻：让我想到‘选举几何’了
- p308 难解（untractable）与不可判定
- 可以是‘部分可计算’和‘部分可判定’吗？
- 停机问题的证明：这个形式证明不是直觉主义构造法的，假如离散的‘所有程序’空间实际上是‘不可枚举’的呢？
- p319 ill-conditioned问题：对应于非刚性（Non=Stiff）的常微分方程？
- p320 一元二次方程的例子，有意思
- p332 分支限界：看上去有点难于理解
- p344 TSP近似算法：著名的Christofides？比‘绕树2周’更复杂
- 对欧几里得实例，本地查找启发：2选、3选、Lin-Kernighan
- p364 我记得并行算法里有一类‘超线性加速’的例子？
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
