《图解算法》系列学习(二)

简介: 《图解算法》系列学习(二)

散列表

最有用的基本数据结构之一。查找时间都为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)的数据结构,可用于广度优先搜索算法。

实现图的算法是由散列表表示

7aa3e0fd46fe7e245cdccba71b36918b.jpg

有向图用箭头表示,关系是单向的,无向图没有箭头,直接相连的节点叫做邻居。例如下面的两个图是等价的。

e26f7ce143f96cf02b3ee1d0edeb7e56.png

实现算法

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

算法执行过程如下图

f177326691ece41dc5f66c3bce5b09da.jpg

运行时间

如果在你的整个人际网络中搜索销售商,就意味着你将沿着每条边前行(边是从一个人到另外一个人的箭头或连接),因此运行时间至少为O(边数)。

你还使用了一个队列,其中包含要检查每一个人。将一个人添加到队列的时间是固定的,即为O(1),因此对每个人都这样做的时间为O(人数)。所以广度优先搜索的运行时间为O(人数+边数),通常为O(V+E),其中V为顶点数,E为边数。

有序列表中,如果任务A依赖于任务B,在列表中任务A就必须在任务B后面,这种被称为拓扑排序,使用它可以根据图创建一个有序列表。如下图就是拓扑顺序。

244d608e894aa76c2d0d3570f5dc618e.png

下面的图被称为树。树是一种特殊的图,其中没有往后指的边

0d691f65666fd9b85998bdf060171353.jpg

相关文章
|
15天前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
30 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
15天前
|
算法 Java 数据库
数据结构与算法学习十五:哈希表
这篇文章详细介绍了哈希表的概念、应用实例、实现思路,并提供了使用Java实现的哈希表代码。
37 0
数据结构与算法学习十五:哈希表
|
12天前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
36 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
13天前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
40 2
动态规划算法学习三:0-1背包问题
|
15天前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
17 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
13天前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
48 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
13天前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
55 0
动态规划算法学习二:最长公共子序列
|
13天前
|
缓存 负载均衡 算法
nginx学习:配置文件详解,负载均衡三种算法学习,上接nginx实操篇
Nginx 是一款高性能的 HTTP 和反向代理服务器,也是一个通用的 TCP/UDP 代理服务器,以及一个邮件代理服务器和通用的 HTTP 缓存服务器。
19 0
nginx学习:配置文件详解,负载均衡三种算法学习,上接nginx实操篇
|
15天前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
13 1
|
15天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
14 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)