下载链接：算法图解 带完整书签：
二分法查找对于区间[a，b]上连续不断且f（a）·f（b）<0的函数y=f（x），通过不断地把函数f（x）的零点所在的区间一分为二，使区间的两个端点逐步逼近零点。 适用于提高大列表查询速度，对于包含n个元素的列表，时间复杂度为:O(log2n)。 列表必须有序，并且当列表中存在多个相同元素时并非返回列表中第一次出现元素，不同实现算法获取到元素索引也不一定相同。 代码实现1/// <summary>/// 递归实现元素查找/// <para>集合长度不变，...
广度优先搜索的应用场景，如下:(1)编写国际跳棋AI，计算最少走多少步就可获胜;(2)编写拼写检查器，计算最少编辑多个地方就可将错拼的单词改为正确的单词，如将READED改为READER需要编辑一个地方;(3)根据你的人际关系网络找到关系最近的医生; 图简介假设你居住在旧金山，要从双子峰前往金门大桥。你想乘公交车前往，并希望换乘最少。可乘坐的公交车如下:由图可知，换乘最少的路线是:步行->44路公交车->28路公交车(一共三步,这种问题...
算法简介 二分查找 数组和链表的操作的运行时间 选择排序 数组和链表总结 算法简介二分查找到速度比简单查找快得多 O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多 算法运行时间并不以秒为单位 算法运行时间是从其增速的角度度量的 算法运行时间用大O表示法表示二分查找O(log n)，也叫对数时间，这样的算法包括二分查找。O(n)，也叫线性时间，这样的算法包括简单查找。O(n * log n)，这样的算法包括第4章将介绍的快速...
狄克斯特拉算法(Dijkstra’s algorithm) 狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重（weight）。带权重的图称为加权图（weighted graph），不带权重的图称为非加权图（unweighted graph）。要计算非加权图中的最短路径，可使用广度优先搜索。要计算加权图中的最短路径，可使用狄克斯特拉算法。 狄克斯特拉算法包含4个步骤：找出最便宜的节点，即可在最短时间内前往的节点。 对于该节点的邻居，检查是否有前往它们...
散列函数(hash table) 散列函数是这样的函数，即无论你给它什么数据，它都还你一个数字。散列函数“将输入映射到数字”。数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素的存储位置。 Python提供的散列表实现为字典，你可使用函数 dict 来创建散列表。例如：book = dict() 还提供了一种创建散列表的快捷方式——使用一对大括号。例如：book = {} 散列表应用 1.查找 当你访问网站，其网址都必须转换为IP地...
1. 散列函数 散列函数就是将输入映射到数字。它必须满足两个条件：输出必须一致，每次输出同一个key，都应得到同样的value。 将不同的输入映射到不同的数字，也就是不能输入什么key都得到同样的value。如下图所示： 散列函数可以准确的指出价格的存储位置，具体原因如下：散列函数总是将同样的输入映射到相同的索引。也就是说apple永远在第四个格子上 散列函数将不同的输入映射到不同的索引。apple的索引为3，milk的索引...
什么是大O表示法 大O表示法可以告诉我们算法的快慢。 大O比较的是操作数，它指出了算法运行时间的增速。 O(n) 括号里的是操作数。 举例 画一个16个格子的网格，下面分别列举几种不同的画法，并用大O表示法表示 1. 一次画一个格子。O(n) 2. 折叠纸张，折叠四次就能出现16个格子。O(log n) 大O表示法所表示的是一个算法在最糟糕情况下的运行时间。 一些常见的大O运行时间O(log n)，也叫对数时间，二分查找。O(n)，也叫线性时间...
这是《算法图解》的第一篇读书笔记，内容关于表示算法复杂度的渐近表示法以及一个简单但高效的算法：二分法。 1 .渐近表示法 1.1定义 算法的运行需要时间，这就需要衡量算法运行时间即时间复杂度的方式。这个衡量方式就被成为渐近表示法（大O表示法）。 渐近表示法用于描述算法在最糟糕情况下的运行时间，同时也表示了算法运行时间随问题规模扩大而增长的幅度。 1.2如何使用渐近表示法确定时间复杂度 一般而言，算法复杂度可用一个...
杨白劳先用喜儿的公钥将将明文加密，生成密文 杨白劳再将密文用哈希算法生成摘要，将摘要用自己的私钥加密，生成摘要的密文，与密文一起传送给喜儿。 喜儿用杨白劳的公钥才能解密摘要的密文，然后用HASH函数对收到的密文产生一个摘要信息，与解密的摘要信息对比。 如果相同，则说明收到的信息是完整的，在传输过程中没有被修改，否则说明信息被修改过，因此数字签名能够验证信息的完整性。 确认完整性后，喜儿再用自己的密钥解密密...
源码地址：https://github.com/egonSchiele/grokking_algorithms 参考书籍：https://book.douban.com/subject/26979890/目录算法简介选择排序递归快速排序分而治之散列表广度优先搜索狄克斯特拉算法贪婪算法NP完全问题动态规划 算法简介 二分法查找，输入一个有序列表，返回元素位置或null。 一般而言，对于包含n个元素的列表，用二分法查找最多需要log2nlog_2 nlog2?n def binary_search(list, item):low = 0high = len(list) - 1...
一.分而治之 分而治之（divide and conquer,D&C）是一种解决问题的重要的策略。它不仅是一种递归式的解决方法，更是一种分析问题的思维模式，尤其在程序设计中反映着一个人的算法内功，其重要性不言而喻。 下面我们先来假设这样一个场景：你要给自己的卧室铺瓷砖，卧室的地面空间是一个矩形，瓷砖是正方形，要求你将尽可能大的瓷砖均匀的铺在地面上，你会怎么做？ 这个问题有三个核心的关键点，首先要是正方形，然后要尽可能大，最...