散列表
最有用的基本数据结构之一。查找时间都为O(1),O(1)被称为常量时间,即所需的时间都相同。
散列函数将输入映射到数字。它需要满足下列几个条件:
1)他必须是一致的,即你不管什么时候每次输入相同时,输出都要一样。如果不是这样,散列表将毫无用处。
2)它应将不同的输入映射到不同的数字。
散列表在Python语言中时用字典dict{}来表示。
冲突
有可能不同的输入会映射到同一个位置,这就叫冲突。因此可以在同一个位置储存一个链表,这样才不会发生冲突。解决冲突的方法:
1)散列函数很重要。理想的散列函数将键均匀的映射到散列表的不同位置。
2)散列函数用的好,链表就不会很长。
性能
散列表的查找速度与数组一样快,而插入与删除速度与链表一样快,因此它兼具两者的优点。而要避免冲突,需要有:
1)较低的填装因子;2)良好的散列函数
填装因子=散列表包含的元素数/位置总数。
填装因子越低,发生冲突的可能性越小,散列表的性能越高。一个不错的经验规则是:一旦填装因子大于0.7,就调整散列表的长度。
广度优先搜索算法
广度优先算法能让你找出两样东西之间最短的距离。使用广度优先搜索可以:
1)编写国际跳棋A,计算最少走多少步就可以获胜
2)编写拼写检查器,计算最少编辑多少个地方就可将错拼的单词改成正确的单词
3)根据你的人际关系网络找到关系最近的医生
图算法是广度优先算法最有用的
图由节点和边组成。一个节点可能与众多节点直接相连,这些节点被称为邻居。广度优先搜索是一种用于图的查找算法,可帮助回答两类问题:
第一类:从节点a出发,有前往b的路径吗
第二类:从节点a出发,前往节点b的哪条路径最短
队列是一种先进先出(First In First Out FIFO)的数据结构,可用于广度优先搜索算法。
实现图的算法是由散列表表示
有向图用箭头表示,关系是单向的,无向图没有箭头,直接相连的节点叫做邻居。例如下面的两个图是等价的。
实现算法
fromcollectionsimportdequegraph={} graph["you"]=["alice","Bob","claire"] #我的一度关系defperson_is_seller(name): #判断是否是销售的returnname[-1]=='m'#名字末尾为m说明是销售的defsearch(name): search_queue=deque() #创建一个队列search_queue+=graph[name] #将你的邻居都加入这个搜索队列中searched=[] #已经检查过的人whilesearch_queue: #只要队列不为空person=search_queue.popleft() #就取出其中的第一个人ifpersonnotinsearched: ifperson_is_seller(person): #检查这个人是不是销售的print(person+' is a mango seller!') returnTrueelse: search_queue+=graph[person] #表示销售商就将这个人的朋 友都加入搜索队列searched.append(person) #将这个人标记为检查过returnFalse#如果达到这里就说明队列中没有人是销售商search("you")
算法执行过程如下图
运行时间
如果在你的整个人际网络中搜索销售商,就意味着你将沿着每条边前行(边是从一个人到另外一个人的箭头或连接),因此运行时间至少为O(边数)。
你还使用了一个队列,其中包含要检查每一个人。将一个人添加到队列的时间是固定的,即为O(1),因此对每个人都这样做的时间为O(人数)。所以广度优先搜索的运行时间为O(人数+边数),通常为O(V+E),其中V为顶点数,E为边数。
有序列表中,如果任务A依赖于任务B,在列表中任务A就必须在任务B后面,这种被称为拓扑排序,使用它可以根据图创建一个有序列表。如下图就是拓扑顺序。
下面的图被称为树。树是一种特殊的图,其中没有往后指的边