元数据
算法图解
- 书名： 算法图解
- 作者： 巴尔加瓦
- 简介： 本书示例丰富，图文并茂，以简明易懂的方式阐释了算法，旨在帮助程序员在日常项目中更好地利用算法为软件开发助力。前三章介绍算法基础，包括二分查找、大O表示法、两种基本的数据结构以及递归等。余下的篇幅将主要介绍应用广泛的算法，具体内容包括：面对具体问题时的解决技巧，比如何时采用贪婪算法或动态规划；散列表的应用；图算法；K最近邻算法。本书适合所有程序员、计算机专业相关师生以及对算法感兴趣的读者。
- 出版时间 2017-03-01 00:00:00
- ISBN： 9787115447630
- 分类： 计算机-编程设计
- 出版社： 人民邮电出版社
- PC地址：https://weread.qq.com/web/reader/fbf32b80715c0184fbff41f
高亮划线
2.1 内存的工作原理
📌 需要将数据存储到内存时，你请求计算机提供存储空间，计算机给你一个存储地址。 ⏱ 2019-08-20 16:37:54
2.2 数组和链表
📌 链表的优势在插入元素方面， ⏱ 2019-08-20 16:39:08
📌 需要同时读取所有元素时，链表的效率很高：你读取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率真的很低 ⏱ 2019-08-20 16:40:01
📌 需要指出的是，仅当能够立即访问要删除的元素时，删除操作的运行时间才为O(1)。 ⏱ 2019-08-20 16:46:00
📌 顺序访问意味着从第一个元素开始逐个地读取元素。 ⏱ 2019-08-20 16:48:04
📌 随机访问意味着可直接跳到第十个元素。 ⏱ 2019-08-20 16:48:09
📌 这个数组包含26个元素，每个元素都指向一个链表。 ⏱ 2019-08-20 16:51:05
第3章 递归
📌 学习如何将问题分成基线条件和递归条件。 ⏱ 2019-08-20 17:02:39
3.2 基线条件和递归条件
📌 编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。 ⏱ 2019-08-20 17:06:20
3.3 栈
📌 栈在递归中扮演着重要角色 ⏱ 2019-08-30 14:43:13
📌 使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。 ⏱ 2019-08-30 14:43:13
3.4 小结
📌 递归指的是调用自己的函数。 ⏱ 2019-08-30 14:43:13
第4章 快速排序
📌 面对新问题时，你不再束手无策，而是自问：“使用分而治之能解决吗？” ⏱ 2019-08-30 14:43:13
4.1 分而治之
📌 你要将这块地均匀地分成方块，且分出的方块要尽可能大。 ⏱ 2019-08-30 14:43:13
📌 如何缩小前述问题的规模呢？我们首先找出这块地可容纳的最大方块。 ⏱ 2019-08-30 14:43:14
📌 适用于这小块地的最大方块，也是适用于整块地的最大方块。 ⏱ 2019-08-30 14:43:14
📌 这确实不好理解，但遗憾的是，要证明这一点，需要的篇幅有点长，在本书中无法这样做，因此你只能选择相信这种说法是正确的。如果你想搞明白其中的原因，可参阅欧几里得算法。可汗学院很清楚地阐述了这种算法，网址为https://www.khanacademy.org/computing/computer-science/ryptography/modarithmetic/a/the-euclidean-algorithm。 ⏱ 2019-08-30 14:43:14
📌 每次递归调用都必须离空数组更近一步。 ⏱ 2019-08-30 14:43:14
📌 诸如Haskell等函数式编程语言没有循环，因此你只能使用递归来编写这样的函数。 ⏱ 2019-08-30 14:43:14
4.2 快速排序
📌 C语言标准库中的函数qsort实现的就是快速排序。 ⏱ 2019-08-30 14:43:14
📌 首先，从数组中选择一个元素，这个元素被称为基准值（pivot）。 ⏱ 2019-08-30 14:43:14
📌 这里只是进行了分区，得到的两个子数组是无序的。 ⏱ 2019-08-30 14:43:14
5.2 应用案例
📌 网站将数据记住，而不再重新计算。 ⏱ 2019-08-30 15:01:05
5.5 小结
📌 一旦填装因子超过0.7，就该调整散列表的长度。 ⏱ 2019-08-30 15:30:36
6.1 图简介
📌 解决最短路径问题的算法被称为广度优先搜索。 ⏱ 2019-08-30 15:59:52
6.3 广度优先搜索
📌 只有按添加顺序查找时，才能实现这样的目的。 ⏱ 2019-09-01 12:26:07
📌 尾递归 ⏱ 2019-08-30 14:43:13
7.4 负权边
📌 在包含负权边的图中，要找出最短路径，可使用另一种算法——贝尔曼-福德算法（Bellman-Ford algorithm）。 ⏱ 2019-09-01 20:15:12
8.1 教室调度问题
📌 用专业术语说，就是你每步都选择局部最优解，最终得到的就是全局最优解。信不信由你，对于这个调度问题，上述简单算法找到的就是最优解！ ⏱ 2019-09-01 20:42:10
8.2 背包问题
📌 在有些情况下，完美是优秀的敌人。有时候，你只需找到一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，因为它们实现起来很容易，得到的结果又与正确结果相当接近。 ⏱ 2019-09-01 20:46:00
8.3 集合覆盖问题
📌 即它覆盖了最多的未覆盖州。 ⏱ 2019-09-01 21:06:18
📌 ❑ 速度有多快； ❑ 得到的近似解与最优解的接近程度。 ⏱ 2019-09-01 21:06:31
📌 练习 下面各种算法是否是贪婪算法。 8.3 快速排序。 8.4 广度优先搜索。 8.5 狄克斯特拉算法。  ⏱ 2019-09-02 17:48:56
8.4 NP完全问题
📌 起点就是未知的 ⏱ 2019-09-02 17:53:50
📌 你需要通过计算为旅行商找出起点和最佳路线。 ⏱ 2019-09-02 17:53:52
📌 因此，如果涉及的城市很多，根本就无法找出旅行商问题的正确解。 ⏱ 2019-09-02 17:55:41
📌 旅行商问题和集合覆盖问题有一些共同之处：你需要计算所有的解，并从中选出最小/最短的那个。这两个问题都属于NP完全问题。 ⏱ 2019-09-02 17:55:52
📌 NP完全问题的简单定义是，以难解著称的问题，如旅行商问题和集合覆盖问题。 ⏱ 2019-09-02 17:56:29
📌 ❑ 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。 ❑ 涉及“所有组合”的问题通常是NP完全问题。 ❑ 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。 ❑ 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。 ❑ 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。 ❑ 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。 ⏱ 2019-09-02 18:08:02
9.1 背包问题
📌 你学习了如何找到近似解，这接近最优解，但可能不是最优解 ⏱ 2019-09-05 12:26:15
📌 动态规划先解决子问题，再逐步解决大问题。 ⏱ 2019-09-04 00:30:31
9.2 背包问题FAQ
📌 各行的排列顺序无关紧要。 ⏱ 2019-09-05 13:49:48
📌 答案是没法处理。使用动态规划时，要么考虑拿走整件商品，要么考虑不拿，而没法判断该不该拿走商品的一部分 ⏱ 2019-09-05 13:49:50
📌 但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用 ⏱ 2019-09-05 13:49:50
9.3 最长公共子串
📌 单元格中的值通常就是你要优化的值。 ⏱ 2019-09-05 14:13:05
📌 在动态规划中，你要将某个指标最大化 ⏱ 2019-09-05 13:49:52
📌 在这个例子中，你要找出两个单词的最长公共子串。hish和fish都包含的最长子串是什么呢？ ⏱ 2019-09-05 13:49:52
📌 这个算法是以著名物理学家理查德·费曼命名的，其步骤如下。 (1) 将问题写下来。 (2) 好好思考。 (3) 将答案写下来。  ⏱ 2019-09-05 13:53:28
📌 你使用过诸如git diff等命令吗？它们指出两个文件的差异，也是使用动态规划实现的。 ⏱ 2019-09-05 14:09:08
9.4 小结
📌 问题可分解为离散子问题时，可使用动态规划来解决。
- 💭 算是把运筹学没学的在这里补上了😂 - ⏱ 2019-09-05 14:12:22
10.2 创建推荐系统
📌 但如何确定两位用户的相似程度呢？ ⏱ 2019-09-05 14:17:37
📌 在前面的水果示例中，你根据个头和颜色来比较水果，换言之，你比较的特征是个头和颜色。 ⏱ 2019-09-05 14:17:55
📌 毕达哥拉斯公式。 ⏱ 2019-09-05 14:18:14
📌 你评论的电影越多，Netflix就越能准确地判断出你与哪些用户类似。 ⏱ 2019-09-05 14:20:57
📌 实际工作中，经常使用余弦相似度（cosine similarity）。 ⏱ 2019-09-05 14:24:00
📌 余弦相似度不计算两个矢量的距离，而比较它们的角度， ⏱ 2019-09-05 14:24:15
10.3 机器学习简介
📌 OCR算法提取线段、点和曲线等特征。 ⏱ 2019-09-05 14:31:56
📌 OCR的第一步是查看大量的数字图像并提取特征，这被称为训练（training）。大多数机器学习算法都包含训练的步骤：要让计算机完成任务，必须先训练它。 ⏱ 2019-09-05 14:32:19
11.1 树
📌 也有一些处于平衡状态的特殊二叉查找树，如红黑树。 ⏱ 2019-09-05 14:41:06
11.6 布隆过滤器和HyperLogLog
📌 面临海量数据且只要求答案八九不离十时，可考虑使用概率型算法！ ⏱ 2019-09-05 14:48:58
11.7 SHA算法
📌 这种散列算法是单向的。你可根据字符串计算出散列值 ⏱ 2019-09-05 14:50:07
11.8 局部敏感的散列算法
📌 Scribd允许用户上传文档或图书，以便与人分享，但不希望用户上传有版权的内容！这个网站可使用Simhash来检查上传的内容是否与小说《哈利·波特》类似，如果类似，就自动拒绝。 需要检查两项内容的相似程度时，Simhash很有用。 ⏱ 2019-09-05 14:51:14
练习答案
📌 个不错的经验规则是：如果有N位用户，应考虑sqrt(N)个邻居。 ⏱ 2019-09-05 14:38:49
读书笔记
9.4 小结
划线评论
📌 问题可分解为离散子问题时，可使用动态规划来解决。 ^8292450-7b9Bpglec - 💭 算是把运筹学没学的在这里补上了😂 - ⏱ 2019-09-05 14:12:52
本书评论
书评 No.1
通俗易懂，要是能早点读就好了。
⏱ 2019-09-05 14:53:07