出版社: 人民邮电出版社
出品方: 图灵教育
原作名: Grokking Algorithms: An illustrated guide for programmers and other curious people
译者: 袁国忠
出版年: 2017-3
页数: 196
定价: 49.00元
装帧: 平装
丛书: 图灵程序设计丛书
ISBN: 9787115447630
内容简介 · · · · · ·
本书示例丰富,图文并茂,以让人容易理解的方式阐释了算法,旨在帮助程序员在日常项目中更好地发挥算法的能量。书中的前三章将帮助你打下基础,带你学习二分查找、大O表示法、两种基本的数据结构以及递归等。余下的篇幅将主要介绍应用广泛的算法,具体内容包括:面对具体问题时的解决技巧,比如,何时采用贪婪算法或动态规划;散列表的应用;图算法;K最近邻算法。
作者简介 · · · · · ·
Aditya Bhargava
软件工程师,兼具计算机科学和美术方面的教育背景,在adit.io撰写编程方面的博客。
目录 · · · · · ·
1.1 引言 1
1.1.1 性能方面 1
1.1.2 问题解决技巧 2
1.2 二分查找 2
1.2.1 更佳的查找方式 4
1.2.2 运行时间 8
1.3 大O表示法 8
1.3.1 算法的运行时间以不同的速度增加 9
1.3.2 理解不同的大O运行时间 10
1.3.3 大O表示法指出了最糟情况下的运行时间 12
1.3.4 一些常见的大O运行时间 12
1.3.5 旅行商 13
1.4 小结 15
第2章 选择排序 16
2.1 内存的工作原理 16
2.2 数组和链表 18
2.2.1 链表 19
2.2.2 数组 20
2.2.3 术语 21
2.2.4 在中间插入 22
2.2.5 删除 23
2.3 选择排序 25
2.4 小结 28
第3章 递归 29
3.1 递归 29
3.2 基线条件和递归条件 32
3.3 栈 33
3.3.1 调用栈 34
3.3.2 递归调用栈 36
3.4 小结 40
第4章 快速排序 41
4.1 分而治之 41
4.2 快速排序 47
4.3 再谈大O表示法 52
4.3.1 比较合并排序和快速排序 53
4.3.2 平均情况和最糟情况 54
4.4 小结 57
第5章 散列表 58
5.1 散列函数 60
5.2 应用案例 63
5.2.1 将散列表用于查找 63
5.2.2 防止重复 64
5.2.3 将散列表用作缓存 66
5.2.4 小结 68
5.3 冲突 69
5.4 性能 71
5.4.1 填装因子 72
5.4.2 良好的散列函数 74
5.5 小结 75
第6章 广度优先搜索 76
6.1 图简介 77
6.2 图是什么 79
6.3 广度优先搜索 79
6.3.1 查找最短路径 82
6.3.2 队列 83
6.4 实现图 84
6.5 实现算法 86
6.6 小结 93
第7章 狄克斯特拉算法 94
7.1 使用狄克斯特拉算法 95
7.2 术语 98
7.3 换钢琴 100
7.4 负权边 105
7.5 实现 108
7.6 小结 116
第8章 贪婪算法 117
8.1 教室调度问题 117
8.2 背包问题 119
8.3 集合覆盖问题 121
8.4 NP 完全问题 127
8.4.1 旅行商问题详解 127
8.4.2 如何识别NP完全问题 131
8.5 小结 133
第9章 动态规划 134
9.1 背包问题 134
9.1.1 简单算法 135
9.1.2 动态规划 136
9.2 背包问题FAQ 143
9.2.1 再增加一件商品将如何呢 143
9.2.2 行的排列顺序发生变化时结果将如何 145
9.2.3 可以逐列而不是逐行填充网格吗 146
9.2.4 增加一件更小的商品将如何呢 146
9.2.5 可以偷商品的一部分吗 146
9.2.6 旅游行程最优化 147
9.2.7 处理相互依赖的情况 148
9.2.8 计算最终的解时会涉及两
个以上的子背包吗 148
9.2.9 最优解可能导致背包没装满吗 149
9.3 最长公共子串 149
9.3.1 绘制网格 150
9.3.2 填充网格 151
9.3.3 揭晓答案 152
9.3.4 最长公共子序列 153
9.3.5 最长公共子序列之解决方案 154
9.4 小结 155
第10章 K最近邻算法 156
10.1 橙子还是柚子 156
10.2 创建推荐系统 158
10.2.1 特征抽取 159
10.2.2 回归 162
10.2.3 挑选合适的特征 164
10.3 机器学习简介 165
10.3.1 OCR 165
10.3.2 创建垃圾邮件过滤器 166
10.3.3 预测股票市场 167
10.4 小结 167
第11章 接下来如何做 168
11.1 树 168
11.2 反向索引 171
11.3 傅里叶变换 171
11.4 并行算法 172
11.5 MapReduce 173
11.5.1 分布式算法为何很有用 173
11.5.2 映射函数 173
11.5.3 归并函数 174
11.6 布隆过滤器和HyperLogLog 174
11.6.1 布隆过滤器 175
11.6.2 HyperLogLog 176
11.7 SHA算法 176
11.7.1 比较文件 177
11.7.2 检查密码 178
11.8 局部敏感的散列算法 178
11.9 Diffie-Hellman密钥交换 179
11.10 线性规划 180
11.11 结语 180
练习答案 181
· · · · · · (收起)
原文摘录 · · · · · · ( 全部 )
-
大O表示法(稍后介绍)讨论运行时间时, log指的都是log2。 使用大O表示法,这个运行时间为O(n)。单位秒呢?没有——大O表示法指的并非以秒为单位的速度。 大O表示法让你能够比较操作数,它指出了算法运行时间的增速。 (查看原文) —— 引自章节:大O表示法 -
下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。 O(log n),也叫对数时间,这样的算法包括二分查找。 O(n),也叫线性时间,这样的算法包括简单查找。 O(n * log n),这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。 O(n2),这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。 O(n!),这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。 (查看原文) —— 引自章节:大O表示法
> 全部原文摘录
丛书信息
喜欢读"算法图解"的人也喜欢的电子书 · · · · · ·
喜欢读"算法图解"的人也喜欢 · · · · · ·
算法图解的话题 · · · · · · ( 全部 条 )



算法图解的书评 · · · · · · ( 全部 17 条 )


《算法图解》读书摘要
这篇书评可能有关键情节透露
1.快速排序时间复杂度 2.使用分治法处理列表时,基线条件很可能是空数组或只包含一个元素的数组。 3.实现快速排序时,请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。 4.大O表示法中的常量有时候事关重大,这就是快速排序比合并排序快的原因所在。 5.比较... (展开)> 更多书评 17篇
-
我没有名字 (nil)
勘误: 对照原文看一下,原文的图中:Sarah will give Rama $7 if he trades his LP for her poster,所以海报是Sarah的,不是Sarah愿意用黑胶唱片和7美元换海报,而是用海报和7美元换黑胶唱片。 而原文的内容是:Suppose Sarah offers to trade the LP for the poster,假设Sarah提出这样一种交易,用LP换取海报,这里并没有说LP是谁的,海报是谁的,但仍然可以根据主语和介词来判断,主语是Sarah,她提供一种交易来换取海报,...2020-02-03 13:58 2人喜欢
勘误:
对照原文看一下,原文的图中:Sarah will give Rama $7 if he trades his LP for her poster,所以海报是Sarah的,不是Sarah愿意用黑胶唱片和7美元换海报,而是用海报和7美元换黑胶唱片。
而原文的内容是:Suppose Sarah offers to trade the LP for the poster,假设Sarah提出这样一种交易,用LP换取海报,这里并没有说LP是谁的,海报是谁的,但仍然可以根据主语和介词来判断,主语是Sarah,她提供一种交易来换取海报,所以海报是她的,这是我的理解。
这里造成译者错误的地方应该在原文的文字,而不是图,他也许看完文字直接翻译成了中文,然后并没有认真看图,直接把他翻译的内容标注在图旁边了。
回应 2020-02-03 13:58 -
gogu (符合灵魂的渴望)
这一整章编排有点敷衍(或者我不能理解? 7.1 计算最终路径卖两次关子说下一节告诉读者。然后 7.2 是术语,讲了加权图和环,没有相关内容。7.3 在陈述记录父节点的步骤时又卖了一次关子,讲完这个步骤才告诉读者「现在来兑现前面承诺」 首先承诺的内容没在下一节,很迷惑;然后不明白为什么为何要延后说明,这没能聚焦要讲的问题。 突然插入的「环」的内容也没讲清楚,为什么狄克斯特拉算法只适用于有向无环图?有环图在算法里... (1回应)2019-01-03 18:17 1人喜欢
这一整章编排有点敷衍(或者我不能理解?
7.1 计算最终路径卖两次关子说下一节告诉读者。然后 7.2 是术语,讲了加权图和环,没有相关内容。7.3 在陈述记录父节点的步骤时又卖了一次关子,讲完这个步骤才告诉读者「现在来兑现前面承诺」
首先承诺的内容没在下一节,很迷惑;然后不明白为什么为何要延后说明,这没能聚焦要讲的问题。
突然插入的「环」的内容也没讲清楚,为什么狄克斯特拉算法只适用于有向无环图?有环图在算法里会造成什么后果?
Dijkstra算法能否用于有环图?https://www.zhihu.com/question/61830552
1回应 2019-01-03 18:17
-
烟雨 (烟锁重楼千里尽,雨打芭蕉万点残)
配合书籍内容的算法简明图表表示:[https://www.manning.com/books/grokking-algorithms] 本书github:[https://github.com/egonschiele/grokking_algorithms] 算法运行时间是从其增速的角度度量的。 算法运行时间用大O表示法表示。 每个递归函数都有两个条件:基线条件和递归条件。 填装因子越低,发生冲突的可能性越小,散列表的性能越高。一个不错的经验规则是:一旦填装因子大于0.7,就调整散列表的长度。 狄克斯特拉算法只...2018-11-29 09:11
配合书籍内容的算法简明图表表示:https://www.manning.com/books/grokking-algorithms
本书github:https://github.com/egonschiele/grokking_algorithms
算法运行时间是从其增速的角度度量的。 算法运行时间用大O表示法表示。
每个递归函数都有两个条件:基线条件和递归条件。
填装因子越低,发生冲突的可能性越小,散列表的性能越高。一个不错的经验规则是:一旦填装因子大于0.7,就调整散列表的长度。
狄克斯特拉算法只适用于有向无环图(directed acyclic graph,DAG)。
不能用于包含负权边的图
负权边要用贝尔曼-福德算法
Python表示无穷大: infinity=float("inf")
DFS算法码如下。 node=find_lowest_cost_node(costs)←------在未处理的节点中找出开销最小的节点 whilenodeisnotNone:←------这个while循环在所有节点都被处理过后结束 cost=costs[node] neighbors=graph[node] forninneighbors.keys():←------遍历当前节点的所有邻居 new_cost=cost+neighbors[n] ifcosts[n]>new_cost:←------如果经当前节点前往该邻居更近, costs[n]=new_cost←------就更新该邻居的开销 parents[n]=node←------同时将该邻居的父节点设置为当前节点 processed.append(node)←------将当前节点标记为处理过 node=find_lowest_cost_node(costs)←------找出接下来要处理的节点,并循环 这就是实现狄克斯特拉算法的Python代码!函数
广度优先搜索用于在非加权图中查找最短路径。 狄克斯特拉算法用于在加权图中查找最短路径。 仅当权重为正时狄克斯特拉算法才管用。
covered=states_needed&states_for_station←------你没见过的语法!它计算交集
>>>fruits|vegetables←------并集
>>>fruits–vegetables←------差集
NP完全问题:你需要计算所有的解,并从中选出最小/最短的那个。
涉及“所有组合”的问题通常是NP完全问题。
不能将问题分成小问题,必须考虑各种可能的情况。这可能是NP完全问题。
动态规划功能强大,它能够解决子问题并使用这些答案来解决大问题。但仅当每个子问题都是离散的,即不依赖于其他子问题时,动态规划才管用
使用余弦相似度(cosine similarity)。假设有两位品味类似的用户,但其中一位打分时更保守。
OCR的第一步是查看大量的数字图像并提取特征,这被称为训练(training)。大多数机器学习算法都包含训练的步骤:要让计算机完成任务,必须先训练它。下一个示例是垃圾邮件过滤器,其中也包含训练的步骤。
垃圾邮件过滤器使用一种简单算法——朴素贝叶斯分类器(Naive Bayes classifier),你首先需要使用一些数据对这个分类器进行训练。
如果你对数据库或高级数据结构感兴趣,请研究如下数据结构:B树,红黑树,堆,伸展树。
这种数据结构被称为反向索引(inverted index),常用于创建搜索引擎。如果你对搜索感兴趣,从反向索引着手研究是不错的选择。
MapReduce是一种流行的分布式算法,你可通过流行的开源工具Apache Hadoop来使用它。
你需要通过Hadoop来使用MapReduce。MapReduce基于两个简单的理念:映射(map)函数和归并(reduce)函数。
布隆过滤器是一种概率型数据结构,它提供的答案有可能不对,但很可能是正确的。为判断网页以前是否已搜集,可不使用散列表,而使用布隆过滤器。使用散列表时,答案绝对可靠,而使用布隆过滤器时,答案却是很可能是正确的。
布隆过滤器的优点在于占用的存储空间很少。使用散列表时,必须存储Google搜集过的所有URL,但使用布隆过滤器时不用这样做。布隆过滤器非常适合用于不要求答案绝对准确的情况,前面所有的示例都是这样的。对bit.ly而言,这样说完全可行:“我们认为这个网站可能是恶意的,请倍加小心。”
HyperLogLog是一种类似于布隆过滤器的算法。如果Google要计算用户执行的不同搜索的数量,或者Amazon要计算当天用户浏览的不同商品的数量,要回答这些问题,需要耗用大量的空间!对Google来说,必须有一个日志,其中包含用户执行的不同搜索。有用户执行搜索时,Google必须判断该搜索是否包含在日志中:如果答案是否定的,就必须将其加入到日志中。即便只记录一天的搜索,这种日志也大得不得了!
散列函数是安全散列算法(secure hash algorithm,SHA)函数。给定一个字符串,SHA返回其散列值。
SHA实际上是一系列算法:SHA-0、SHA-1、SHA-2和SHA-3。本书编写期间,SHA-0和SHA-1已被发现存在一些缺陷。如果你要使用SHA算法来计算密码的散列值,请使用SHA-2或SHA-3。当前,最安全的密码散列函数是bcrypt,但没有任何东西是万无一失的。
有时候,你希望散列函数是局部敏感的。在这种情况下,可使用Simhash。如果你对字符串做细微的修改,Simhash生成的散列值也只存在细微的差别。这让你能够通过比较散列值来判断两个字符串的相似程度,这很有用! Google使用Simhash来判断网页是否已搜集。
Diffie-Hellman使用两个密钥:公钥和私钥。顾名思义,公钥就是公开的,可将其发布到网站上,通过电子邮件发送给朋友,或使用其他任何方式来发布。你不必将它藏着掖着。有人要向你发送消息时,他使用公钥对其进行加密。加密后的消息只有使用私钥才能解密。只要只有你知道私钥,就只有你才能解密消息!
线性规划使用Simplex算法。
人工智能使用K最近邻(k-nearest neighbours,KNN)算法
回应 2018-11-29 09:11
-
[https://mp.weixin.qq.com/mp/appmsgalbum?action=getalbum&album_id=1467508581766823939&__biz=MzU0OTc5NzY5NA==#wechat_redirect]
2020-08-10 20:44
-
EZ (泥锅泥碗你滚蛋,你追我赶2020年)
import math def fact(x): if (x==1): return x else: f = x*fact(x-1) return f # print(fact(3)) # 最大公倍数 def divideAndConquer(a,b): a1 = a if a>b else b b1 = b if a>b else a if (a1%b1==0): return (a1,b1) else: a1=a1%(a1%b1) b1=a1%b1 return (a1,b1) # print(divideAndConquer(16800,6400)) arr1=[7,1,4,5,6] arr2=[1,5] def sum(arr): if (arr==[]): return 0 else: return (arr[0]+sum(arr[1:])) def ...2020-03-09 16:10
import math
def fact(x):
if (x==1):
return x
else:
f = x*fact(x-1)
return f
# print(fact(3))
# 最大公倍数
def divideAndConquer(a,b):
a1 = a if a>b else b
b1 = b if a>b else a
if (a1%b1==0):
return (a1,b1)
else:
a1=a1%(a1%b1)
b1=a1%b1
return (a1,b1)
# print(divideAndConquer(16800,6400))
arr1=[7,1,4,5,6]
arr2=[1,5]
def sum(arr):
if (arr==[]):
return 0
else:
return (arr[0]+sum(arr[1:]))
def count(arr):
if (arr==[]):
return 0
else:
return (1+count(arr[1:]))
print(sum(arr1))
print(count(arr1))
def max(arr):
if (arr==[]):
return 0
else:
a1= arr[0] if arr[0]>max(arr[1:]) else max(arr[1:])
return (a1)
# print(123)
print(max(arr2))
# a 为猜测数值 x 为最小值 y为最大值 z为预测值 二分法
def bingo(a,x,y):
z=math.ceil((x+y)/2)
if (z==a):
return (z)
elif(z<a):
return bingo(a,z,y)
else:
return(bingo(a,x,z))
print(bingo(7,0,9000))
回应 2020-03-09 16:10 -
【联读】#树读二进制# 0/禅熵:毫不费力的作为 1/心流:轻而易举的富足 D79 (帝师私教·亲子学习力:双语高分高能○|●读家教练Ⅰ级三阶认证:①菁英阅读控②关联知识图谱③心法实践融合技 5157-5161/25000本“书单人生定制·品味范式长征”) 291-295/1800 《算法图解》巴尔加瓦 全书字数:63千字 速标时长:3分钟(23040字/分钟) 心读指数:★★★★★♥♥♥ 定价:49元 〖树摘〗 · 动态·规划 遇到问题时,如果不确定该...
2020-02-13 23:22
【联读】#树读二进制# 0/禅熵:毫不费力的作为 1/心流:轻而易举的富足 D79 (帝师私教·亲子学习力:双语高分高能○|●读家教练Ⅰ级三阶认证:①菁英阅读控②关联知识图谱③心法实践融合技 5157-5161/25000本“书单人生定制·品味范式长征”) 291-295/1800 《算法图解》巴尔加瓦 全书字数:63千字 速标时长:3分钟(23040字/分钟) 心读指数:★★★★★♥♥♥ 定价:49元 〖树摘〗 · 动态·规划 遇到问题时,如果不确定该如何高效地解决,可尝试分而治之或动态规划;如果认识到根本就没有高效的解决方案,可转而使用贪婪算法来得到近似答案。 动态规划功能强大,它能够解决子问题并使用这些答案来解决大问题。但仅当每个子问题都是离散的,即不依赖于其他子问题时,动态规划才管用。 · 二分查找 二分查找是一种算法,其输入是一个有序的元素列表(必须有序的原因稍后解释)。如果要查找的元素包含在列表中,二分查找返回其位置;否则返回null。 · 大O表示法 大O表示法指出了算法有多快。例如,假设列表包含n个元素。简单查找需要检查每个元素,因此需要执行n次操作。使用大O表示法,这个运行时间为O(n)。单位秒呢?没有——大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数,它指出了算法运行时间的增速。 下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。 ❑ O(log n),也叫对数时间,这样的算法包括二分查找。 ❑ O(n),也叫线性时间,这样的算法包括简单查找。 ❑ O(n * log n),这样的算法包括快速排序——一种速度较快的排序算法。 ❑ O(n2),这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。 ❑ O(n! ),这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。 ❑ 算法的速度指的并非时间,而是操作数的增速。 ❑ 谈论算法的速度时,我们说的是随着输入的增加,其运行时间将以什么样的速度增加。 ❑ 算法的运行时间用大O表示法表示。 ❑ O(log n)比O(n)快,当需要搜索的元素越多时,前者比后者快得越多。 · 集合 计算机就像是很多抽屉的集合体,每个抽屉都有地址。 ❑ 并集意味着将集合合并。 ❑ 交集意味着找出两个集合中都有的元素(在这里,只有西红柿符合条件)。 ❑ 差集意味着将从一个集合中剔除出现在另一个集合中的元素。 · 链表·数组 需要同时读取所有元素时,链表的效率很高:你读取第一个元素,根据其中的地址再读取第二个元素,以此类推。但如果你需要跳跃,链表的效率真的很低。 数组和链表哪个用得更多呢?显然要看情况。但数组用得很多,因为它支持随机访问。有两种访问方式:随机访问和顺序访问。顺序访问意味着从第一个元素开始逐个地读取元素。链表只能顺序访问:要读取链表的第十个元素,得先读取前九个元素,并沿链接找到第十个元素。随机访问意味着可直接跳到第十个元素。 ❑ 计算机内存犹如一大堆抽屉。 ❑ 需要存储多个元素时,可使用数组或链表。 ❑ 数组的元素都在一起。 ❑ 链表的元素是分开的,其中每个元素都存储了下一个元素的地址。 ❑ 数组的读取速度很快。 ❑ 链表的插入和删除速度很快。 ❑ 在同一个数组中,所有元素的类型都必须相同(都为int、double等)。 · 递归函数 每个递归函数都有两部分:基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己,而基线条件则指的是函数不再调用自己,从而避免形成无限循环。 · 待办事项·清单 一叠便条要简单得多:插入的待办事项放在清单的最前面;读取待办事项时,你只读取最上面的那个,并将其删除。因此这个待办事项清单只有两种操作:压入(插入)和弹出(删除并读取)。 · 栈 原来“盒子堆”存储在了栈中!这个栈包含未完成的函数调用,每个函数调用都包含还未检查完的盒子。使用栈很方便,因为你无需自己跟踪盒子堆——栈替你这样做了。使用栈虽然很方便,但是也要付出代价:存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存,如果栈很高,就意味着计算机存储了大量函数调用的信息。 · 分解 D&C算法是递归的。使用D&C解决问题的过程包括两个步骤。 (1) 找出基线条件,这种条件必须尽可能简单。 (2) 不断将问题分解(或者说缩小规模),直到符合基线条件。 · 归纳 归纳证明是一种证明算法行之有效的方式,它分两步:基线条件和归纳条件。是不是有点似曾相识的感觉?例如,假设我要证明我能爬到梯子的最上面。递归条件是这样的:如果我站在一个横档上,就能将脚放到上一个横档上。换言之,如果我站在第二个横档上,就能爬到第三个横档。这就是归纳条件。而基线条件是这样的,即我已经站在第一个横档上。因此,通过每次爬一个横档,我就能爬到梯子最顶端。对于快速排序,可使用类似的推理。在基线条件中,我证明这种算法对空数组或包含一个元素的数组管用。在归纳条件中,我证明如果快速排序对包含一个元素的数组管用,对包含两个元素的数组也将管用;如果它对包含两个元素的数组管用,对包含三个元素的数组也将管用,以此类推。因此,我可以说,快速排序对任何长度的数组都管用。这里不再深入讨论归纳证明,但它很有趣,并与D&C协同发挥作用。 · 快速·排序 快速排序的独特之处在于,其速度取决于选择的基准值。 · 散列·函数 散列函数“将输入映射到数字”。 在平均情况下,散列表的查找(获取给定索引处的值)速度与数组一样快,而插入和删除速度与链表一样快,因此它兼具两者的优点!但在最糟情况下,散列表的各种操作的速度都很慢。因此,在使用散列表时,避开最糟情况至关重要。为此,需要避免冲突。而要避免冲突,需要有: ❑ 较低的填装因子; ❑ 良好的散列函数。 安全散列算法(secure hash algorithm, SHA)函数。给定一个字符串,SHA返回其散列值。 SHA是一个散列函数,它生成一个散列值——一个较短的字符串。用于创建散列表的散列函数根据字符串生成数组索引,而SHA根据字符串生成另一个字符串。对于每个不同的字符串,SHA生成的散列值都不同。 你可使用SHA来判断两个文件是否相同,这在比较超大型文件时很有用。假设你有一个4 GB的文件,并要检查朋友是否也有这个大型文件。为此,你不用通过电子邮件将这个大型文件发送给朋友,而可计算它们的SHA散列值,再对结果进行比较。 当前,最安全的密码散列函数是bcrypt,但没有任何东西是万无一失的。 希望散列函数是局部敏感的。在这种情况下,可使用Simhash。如果你对字符串做细微的修改,Simhash生成的散列值也只存在细微的差别。这让你能够通过比较散列值来判断两个字符串的相似程度,这很有用! ❑ Google使用Simhash来判断网页是否已搜集。 ❑ 老师可以使用Simhash来判断学生的论文是否是从网上抄的。 ❑ Scribd允许用户上传文档或图书,以便与人分享,但不希望用户上传有版权的内容!这个网站可使用Simhash来检查上传的内容是否与小说《哈利·波特》类似,如果类似,就自动拒绝。需要检查两项内容的相似程度时,Simhash很有用。 · 缓存 这就是缓存的工作原理:网站将数据记住,而不再重新计算。 · 广度优先·搜索 你经常要找出最短路径,这可能是前往朋友家的最短路径,也可能是国际象棋中把对方将死的最少步数。解决最短路径问题的算法被称为广度优先搜索。要确定如何从双子峰前往金门大桥,需要两个步骤。 (1) 使用图来建立问题模型。 (2) 使用广度优先搜索解决问题。 · 队列-栈 队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队,如果你排在他前面,你将先上车。队列的工作原理与此相同。队列类似于栈,你不能随机地访问队列中的元素。队列只支持两种操作:入队和出队。 队列是一种先进先出(First In First Out, FIFO)的数据结构,而栈是一种后进先出(Last In First Out, LIFO)的数据结构。 · 检查 检查一个人之前,要确认之前没检查过他,这很重要。为此,你可使用一个列表来记录检查过的人。 · 迪克斯特拉·算法·权重·有向·无环 如果你要找出最快的路径(如第二个图所示),该如何办呢?为此,可使用另一种算法——狄克斯特拉算法(Dijkstra's algorithm)。 狄克斯特拉算法包含4个步骤。 (1) 找出“最便宜”的节点,即可在最短时间内到达的节点。 (2) 更新该节点的邻居的开销。 (3) 重复这个过程,直到对图中的每个节点都这样做了。 (4) 计算最终路径。 狄克斯特拉算法用于每条边都有关联数字的图,这些数字称为权重(weight)。 带权重的图称为加权图(weighted graph),不带权重的图称为非加权图(unweighted graph)。 在无向图中,每条边都是一个环。狄克斯特拉算法只适用于有向无环图(directed acyclic graph, DAG)。 这就是狄克斯特拉算法背后的关键理念:找出图中最便宜的节点,并确保没有到该节点的更便宜的路径! · 贪婪·算法 很多人都跟我说,这个算法太容易、太显而易见,肯定不对。但这正是贪婪算法的优点——简单易行!贪婪算法很简单:每步都采取最优的做法。在这个示例中,你每次都选择结束最早的课。用专业术语说,就是你每步都选择局部最优解,最终得到的就是全局最优解。信不信由你,对于这个调度问题,上述简单算法找到的就是最优解! 在有些情况下,完美是优秀的敌人。有时候,你只需找到一个能够大致解决问题的算法,此时贪婪算法正好可派上用场,因为它们实现起来很容易,得到的结果又与正确结果相当接近。 · NP完全·问题 你需要计算所有的解,并从中选出最小/最短的那个。这两个问题都属于NP完全问题。 ❑ 元素较少时算法的运行速度非常快,但随着元素数量的增加,速度会变得非常慢。 ❑ 涉及“所有组合”的问题通常是NP完全问题。 ❑ 不能将问题分成小问题,必须考虑各种可能的情况。这可能是NP完全问题。 ❑ 如果问题涉及序列(如旅行商问题中的城市序列)且难以解决,它可能就是NP完全问题。 ❑ 如果问题涉及集合(如广播台集合)且难以解决,它可能就是NP完全问题。 ❑ 如果问题可转换为集合覆盖问题或旅行商问题,那它肯定是NP完全问题。 你可以合并两个子问题的解来得到更大问题的解。 · 费曼·框架 费曼算法(Feynman algorithm)。这个算法是以著名物理学家理查德·费曼命名的,其步骤如下。 (1) 将问题写下来。 (2) 好好思考。 (3) 将答案写下来。 有些算法并非精确的解决步骤,而只是帮助你理清思路的框架。 · 毕达哥拉斯·公式 要计算两点的距离,可使用毕达哥拉斯公式。 · 分类·回归·特征 你将使用KNN来做两项基本工作——分类和回归: ❑ 分类就是编组; ❑ 回归就是预测结果(如一个数字)。 使用KNN时,挑选合适的特征进行比较至关重要。所谓合适的特征,就是: ❑ 与要推荐的电影紧密相关的特征; ❑ 不偏不倚的特征(例如,如果只让用户给喜剧片打分,就无法判断他们是否喜欢动作片)。 · 训练·朴素贝叶斯·分类器 OCR的第一步是查看大量的数字图像并提取特征,这被称为训练(training)。大多数机器学习算法都包含训练的步骤:要让计算机完成任务,必须先训练它。 垃圾邮件过滤器使用一种简单算法——朴素贝叶斯分类器(Naive Bayes classifier),你首先需要使用一些数据对这个分类器进行训练。 朴素贝叶斯分类器能计算出邮件为垃圾邮件的概率,其应用领域与KNN相似。 · 二叉·查找树-数据结构 每当用户登录Facebook时,Facebook都必须在一个庞大的数组中查找,核实其中是否包含指定的用户名。前面说过,在这种数组中查找时,最快的方式是二分查找,但问题是每当有新用户注册时,都必须将其用户名插入该数组并重新排序,因为二分查找仅在数组有序时才管用。如果能将用户名插入到数组的正确位置就好了,这样就无需在插入后再排序。为此,有人设计了一种名为二叉查找树(binary search tree)的数据结构。 如果你对数据库或高级数据结构感兴趣,请研究如下数据结构:B树,红黑树,堆,伸展树。 · 反向索引 这是一种很有用的数据结构:一个散列表,将单词映射到包含它的页面。这种数据结构被称为反向索引(inverted index),常用于创建搜索引擎。如果你对搜索感兴趣,从反向索引着手研究是不错的选择。 · 傅里叶·变换 Better Explained是一个杰出的网站,致力于以通俗易懂的语言阐释数学,它就傅里叶变换做了一个绝佳的比喻:给它一杯冰沙,它能告诉你其中包含哪些成分。换言之,给定一首歌曲,傅里叶变换能够将其中的各种频率分离出来。 · 并行·算法 ❑ 并行性管理开销。假设你要对一个包含1000个元素的数组进行排序,如何在两个内核之间分配这项任务呢?如果让每个内核对其中500个元素进行排序,再将两个排好序的数组合并成一个有序数组,那么合并也是需要时间的。 ❑ 负载均衡。假设你需要完成10个任务,因此你给每个内核都分配5个任务。但分配给内核A的任务都很容易,10秒钟就完成了,而分配给内核B的任务都很难,1分钟才完成。这意味着有那么50秒,内核B在忙死忙活,而内核A却闲得很!你如何均匀地分配工作,让两个内核都一样忙呢?要改善性能和可扩展性,并行算法可能是不错的选择! · 分布式·算法-映射·归并·函数 MapReduce是一种流行的分布式算法,你可通过流行的开源工具Apache Hadoop来使用它。 假设你有一个数据库表,包含数十亿乃至数万亿行,需要对其执行复杂的SQL查询。在这种情况下,你不能使用MySQL,因为数据表的行数超过数十亿后,它处理起来将很吃力。相反,你需要通过Hadoop来使用MapReduce!又假设你需要处理一个很长的清单,其中包含100万个职位,而每个职位处理起来需要10秒。如果使用一台计算机来处理,将耗时数月!如果使用100台计算机来处理,可能几天就能完工。分布式算法非常适合用于在短时间内完成海量工作,其中的MapReduce基于两个简单的理念:映射(map)函数和归并(reduce)函数。 归并函数可能令人迷惑,其理念是将很多项归并为一项。映射是将一个数组转换为另一个数组。 · 近似 HyperLogLog近似地计算集合中不同的元素数,与布隆过滤器一样,它不能给出准确的答案,但也八九不离十,而占用的内存空间却少得多。面临海量数据且只要求答案八九不离十时,可考虑使用概率型算法! · 加密·算法 Diffie-Hellman算法解决了如下两个问题。 ❑ 双方无需知道加密算法。他们不必会面协商要使用的加密算法。 ❑ 要破解加密的消息比登天还难。Diffie-Hellman使用两个密钥:公钥和私钥。顾名思义,公钥就是公开的,可将其发布到网站上,通过电子邮件发送给朋友,或使用其他任何方式来发布。你不必将它藏着掖着。有人要向你发送消息时,他使用公钥对其进行加密。加密后的消息只有使用私钥才能解密。只要只有你知道私钥,就只有你才能解密消息!Diffie-Hellman算法及其替代者RSA依然被广泛使用。 · 线性·规划 线性规划用于在给定约束条件下最大限度地改善指定的指标。例如,假设你所在的公司生产两种产品:衬衫和手提袋。衬衫每件利润2美元,需要消耗1米布料和5粒扣子;手提袋每个利润3美元,需要消耗2米布料和2粒扣子。你有11米布料和20粒扣子,为最大限度地提高利润,该生产多少件衬衫、多少个手提袋呢?在这个例子中,目标是利润最大化,而约束条件是拥有的原材料数量。 所有的图算法都可使用线性规划来实现。线性规划是一个宽泛得多的框架,图问题只是其中的一个子集。 线性规划使用Simplex算法。
回应 2020-02-13 23:22
当前版本有售 · · · · · ·
购买二手书 · · · · · ·
-
暂时无货,预计2天到货
这本书的其他版本 · · · · · · ( 全部3 )
-
Manning Publications (2015)8.9分 104人读过
-
松崗電腦圖書資料股份有限公司 (2017)暂无评分 2人读过
以下书单推荐 · · · · · · ( 全部 )
谁读这本书?
二手市场
订阅关于算法图解的评论:
feed: rss 2.0
4 有用 赖爆炸💥 2018-09-09
囫囵吞枣
2 有用 Chain 2019-07-03
递归,分而治之DC, 快速排序 散列表 广度有限搜索DFS,图 => 求最短路径 Dijkstra算法 => 求最短加权路径(不带负边),Bellman-Ford算法(带负边) 贪婪算法,集合覆盖,NP完全 动态规划DP => 背包问题,最长公共子串 KNN算法 => 分类,回归,机器学习 树,二叉树查找,二分查找 平衡 => 红黑树 B树,红黑树,伸展树,堆 => 数据库结构 反向索引 傅里叶变... 递归,分而治之DC, 快速排序 散列表 广度有限搜索DFS,图 => 求最短路径 Dijkstra算法 => 求最短加权路径(不带负边),Bellman-Ford算法(带负边) 贪婪算法,集合覆盖,NP完全 动态规划DP => 背包问题,最长公共子串 KNN算法 => 分类,回归,机器学习 树,二叉树查找,二分查找 平衡 => 红黑树 B树,红黑树,伸展树,堆 => 数据库结构 反向索引 傅里叶变换 分布式算法,MapReduce, 布隆过滤器,HyperLogLog => 概率型数据结构 SHA算法 => 比较文件,局部敏感 Simhash算法 => 判断相似度,局部不敏感 Diffie-Hellman加密算法 => 公钥密钥 线性规划 => Simplex算法 (展开)
8 有用 盲刺客·大河魂 2018-07-03
虎头蛇尾了,前面的内容讲得还可以,后面基本上都让人很费解,图很多但是实例都不当,代码很少,几乎可以忽略不计。从狄克斯特拉算法的第七章开始就看不懂了。
1 有用 Rosecanoe 2018-06-16
超级棒,一直觉得很枯燥的数学竟然如此迷人?忽然重燃对数学的兴趣。
1 有用 Zhuo 2018-04-17
文科小白看图说话系列。感觉到了作者的苦心,已经尽可能讲的基础又简略了,即便如此,遇到代码部分还是愉快地跳过了。
0 有用 zyttt 2021-03-06
浅入浅出
0 有用 MaxinAn 2021-03-05
此书的定位适合为:兴趣型阅读、了解型阅读,用于判断这个领域是否感兴趣。从这个角度讲,编排也蛮合理。如果严肃学习需要的,自然不能采用。
0 有用 hit9 2021-02-23
非常通俗易懂的算法书,可以很快读完。讲的内容比较浅。不过,把复杂的事情,讲明白、讲简单,是非常可贵的。
0 有用 Minazuki Haku 2021-02-23
作者力求易懂,通过各种生活中的例子,图文并茂的讲解了众多经典算法,是一本不错的入门书!
0 有用 NEVER SETTLE 2021-02-23
很基础,很棒,很推荐,挺适合入门算法和数据结构的。门槛的话,多少还是需要一点计算机基础(如果是大佬的话请自动忽视)。