用来描述性能的参数，值为散列表的元素数/位置总数。填装因子大于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) 计算最终路径。
要计算非加权图中的最短路径，可使用广度优先搜索。要计算加权图中的最短路径，可使用狄克斯特拉算法。
要注意的是狄克斯特拉算法只适用于无环图，并且狄克斯特拉算法无法计算负权的边。带负权的边要使用贝尔曼福德算法计算（这个我也不会）。
下面代码就实现了狄克斯特拉算法计算出最短路径的代码。
# 迪克斯塔拉算法求最短路径 graph = {}#先描述距离 graph["start"] = {} graph["start"]["a"] = 6 graph["start"]["b"] = 2 graph["a"] = {} graph["a"]["fin"] = 1 graph["b"] = {} graph["b"]["a"] = 3 graph["b"]["fin"] = 5 graph["fin"] = {} # 权重表 infinity = float("inf") costs = {} costs["a"] = 6 costs["b"] = 2 costs["fin"] = infinity # the parents table parents = {} parents["a"] = "start" parents["b"] = "start" parents["fin"] = None processed = []#已经算过的列表 def find_lowest_cost_node(costs): lowest_cost = float("inf")#终点无限大 lowest_cost_node = None # 遍历每一个节点 for node in costs: cost = costs[node] # 判断大小并且之前未计算�� if cost < lowest_cost and node not in processed: lowest_cost = cost#如果有更小距离则更新 lowest_cost_node = node return lowest_cost_node # 未处理的成本最低的节点. node = find_lowest_cost_node(costs) # 处理完所有节点时循环结束 while node is not None: cost = costs[node] # 通过节点的所有邻居 neighbors = graph[node] for n in neighbors.keys(): new_cost = cost + neighbors[n]#从此节点计算到下一节点的开销 # 如果是去这个邻居通过这个节点更便宜 if costs[n] > new_cost: # 更新此节点最小值 costs[n] = new_cost # 节点成为邻居最近的下一节点 parents[n] = node #节点标记为已处理 processed.append(node) #发现下一个节点与环 node = find_lowest_cost_node(costs) print("Cost from the start to each node:") print(costs) 运行结果： Cost from the start to each node: {'a': 5, 'fin': 6, 'b': 2}
贪婪算法贪婪算法很简单：每步都采取最优的做法，最终得到的就是全局最优解。贪婪算法并非在任何情况下都行之有效，但它易于实现。
用一个简单的例子来解释一下。比如有下面一张课程表，你学要尽可能多的在一间教室里上最多的课。
(1) 选出结束最早的课，它就是要在这间教室上的第一堂课。
(2) 接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要在这间教室上的第二堂课。
(3)重复第二步。