算法图解

https://mp.weixin.qq.com/mp/appmsgalbum?action=getalbum&album_id=1467508581766823939&__biz=MzU0OTc5NzY5NA==#wechat_redirect

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))

图解一般，但是举例还可以。内容确实浅显了点，代码量约等于无，但讲法比较直白易懂，适合和其他书并行看或者做补充工具吧。大O表示法实在不够清晰，是在每一章中逐步加深讲解的，直接用来入门的话可能会看懵。

【联读】#树读二进制# 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算法。