散列函数“将输入映射到数字”。这个用python字典比较好理解，每次给定key都得到的是同一个数字，每个key都对应一个value。

　　? 散列函数总是将同样的输入映射到相同的索引。

　　? 散列函数将不同的输入映射到不同的索引。

　　? 散列函数知道数组有多大，只返回有效的索引。

　　说到字典你可能根本不需要自己去实现散列表，任一优秀的语言都提供了散列表实现。Python提供的散列表实现就是字典，你可使用函数dict来创建散列表。

　　这样散列表的概念就非常好理解了，散列表通常用于查找，在网站投票中还可以过滤掉已经投过票的人，也就是去重，还有就是对于一些经常访问的网站进行缓存也使用了散列表。缓存是一种常用的加速方式，所有大型网站都使用缓存，而缓存的数据则存储在散列表中。

　　间接描述了散列表的性能，冲突就是：给两 个键分配的位置相同。处理冲突的方式 很多，最简单的办法如下：如果两个键映射到了同一个位置，就在这个位置存储一个链表。如果一个散列表所有的值都放在第一个内存中呢，那和一个链表又有什么区别呢？最理想的情况是， 散列函数将键均匀地映射到散列表的不同位置。如果散列表存储的链表很长，散列表的速度将急剧下降。

　　在平均情况下，散列表执行各种操作的时间都为O(1)。我们来将 散列表同数组和链表比较一下。

　　用来描述性能的参数，值为散列表的元素数/位置总数。填装因子大于1时意味元素数大于位置数，这个时候可能就是要考虑调整散列表长度了。调整散列表长度的工作需要很长时间！你说得没错，调整长度的开销很大，因 此你不会希望频繁地这样做。但平均而言，即便考虑到调整长度所需的时间，散列表操作所需的时间也为O(1)。

　　如果你要从A点去往B点，这种问题被称为最短路径问题需要两个步骤。

　　 (1) 使用图来建立问题模型。

　　(2) 使用广度优先搜索解决问题。

　　图是由节点和边组成的，图用于模拟不同的东西是如何相连的。

　　广度优先搜索是一种用于图的查找算法，可帮助回答两类问题。

　　? 第一类问题：从节点A出发，有前往节点B的路径吗？

　　? 第二类问题：从节点A出发，前往节点B的哪条路径最短？

　　广度优先的工作原理图

　　要看你的认识的人中有没有芒果销售员，从你的朋友开始查每查一个朋友就把他的朋友加入你的查找列表队列的末尾，直到查完为止或者找到的第一个芒果销售员。在此过程中对于已经查过的人单独拿出来，因为重复查无意义甚至导致无限循环。

　　注： 有向图中的边为箭头，箭头的方向指定了关系的方向，例如，rama→adit表示rama欠adit钱。 无向图中的边不带箭头，其中的关系是双向的，例如，ross - rachel表示“ross与rachel约 会，而rachel也与ross约会”。

　　还是解决最短路径的算法，不过他解决的是加权图的最短路径。也就是说在狄克斯特拉算法中，你给每段都分配了一个数字或权重，因此狄克斯特拉算法找出 的是总权重最小的路径。

　　狄克斯特拉算法包含4个步骤。

　　(1) 找出“最便宜”的节点，即可在最短时间内到达的节点。

　　(2) 更新该节点的邻居的开销。

　　(3) 重复这个过程，直到对图中的每个节点都这样做了。

　　(4) 计算最终路径。

　　要计算非加权图中的最短路径，可使用广度优先搜索。要计算加权图中的最短路径，可使用狄克斯特拉算法。

　　要注意的是狄克斯特拉算法只适用于无环图，并且狄克斯特拉算法无法计算负权的边。带负权的边要使用贝尔曼福德算法计算（这个我也不会）。

　　下面代码就实现了狄克斯特拉算法计算出最短路径的代码。

　　贪婪算法很简单：每步都采取最优的做法，最终得到的就是全局最优解。贪婪算法并非在任何情况下都行之有效，但它易于实现。

　　用一个简单的例子来解释一下。比如有下面一张课程表，你学要尽可能多的在一间教室里上最多的课。

　　(1) 选出结束最早的课，它就是要在这间教室上的第一堂课。

　　(2) 接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要在这间教室上的第二堂课。

　　(3)重复第二步。

　　这就是贪婪算法。虽然贪婪算法是万能的但是他往往不是最优的，但是对于一些没有更好的解决方法，贪婪算法往往是最有效的。

　　假设你办了一个电视节目你想在全国上映，但是每个电视台覆盖的范围都不一样，还可能有重复覆盖的区域。

　　(1) 列出每个可能的广播台集合，这被称为幂集（power set）。可能的子集有2n个。

　　(2) 在这些集合中，选出覆盖全美50个州的最小集合。问题是计算每个可能的广播台子集需要很长时间。由于可能的集合有2**n个，因此运行时间为 O(2**n )。

　　贪婪算法可化解危机！使用下面的贪婪算法可得到非常接近的解。

　　(1) 选出这样一个广播台，即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖的州，也没有关系。

　　(2) 重复第一步，直到覆盖了所有的州。

　　这是一种近似算法（approximation algorithm）。在获得精确解需要的时间太长时，可使用近似算法。

　　判断近似算法优劣的标准如下：

　　? 速度有多快；

　　? 得到的近似解与最优解的接近程度。

　　这个问题的算法代码：

　　贪婪算法还可以求出旅行商问题的简单答案。

　　NP完全问题的简单定义是，以难解著称的问题，如旅行商问题和集合覆盖问题。NP算法本身不难，但是界定哪些问题应该使用NP算法求解更优却是个难点。要判断问题是不是NP完全问题很难，易于解决的问题和NP完全问题的差别通常很小。

　　如何判断问题是不是NP完全问题：

　　? 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。

　　? 涉及“所有组合”的问题通常是NP完全问题。

　　? 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。

　　? 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。

　　? 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。

　　? 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。

　　一个小偷，背包容纳量为4，商店有三件商品可以偷，音响3000块重量4，电脑2000块重量3，吉他1500块重量1。

　　尝试一次次的试，时间为O（2**n），这种方法肯定可以使用NP算法啦，但是不是最优解。

　　动态规划先解决子问题，再逐步解决大问题。

　　每个动态规划算法都从一个网格开始，背包问题的网格如下。

　　第一行是吉他行，你只能选择拿不拿吉他，只能拿其他肯定会拿偷啊，这样利益最大化。

　　第二行是音箱行，你可以选择吉他或音箱。

　　第三行电脑行，三种都可以选择。

　　这里行排列的顺序变化了对结果没什么影响。并且最优解可能背包还没装满。

　　但仅当 每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。

　　抽取事物特征并在坐标轴上给出横纵坐标打分，这等于抽象出空间中的点，然后使用毕达哥拉斯公式计算与其他点的距离来判断与哪些点更为相似。

　　Priyanka和Morpheus的距离为24，所以可得出Priyanka的喜好更接近于Justin而不是Morpheus的结论。这样就可以依据Justin的喜好给Priyanka推荐电影啦。