Another RayJune

纸上谈兵-算法与数据结构小记

《纸上谈兵: 算法与数据结构》作者:Vamei 出处:http://www.cnblogs.com/vamei

觉得这个教程系列理解起来非常顺畅,这次倒没有逐字敲,而是看完后用自己的理解记录下来,就有了这篇笔记。
当然这只是入门,要想进一步掌握数据结构和算法,啃经典、敲代码是必不可少的。

前言

算法研究解决问题的方法,而数据结构则是设计一种更好的组织数据和使用数据的方式。两者有很强的相互依赖关系,所以往往放在一起讨论。

一个数据结构的实现有两方面: 1. 数据结构的内存表达方式; 2. 定义在该数据结构上的操作。

表(lsit)

表(lsit):内存中离散分布的有序节点

表的功能与数组(array)很类似,数组也是有序的元素集合,但数组在内存中为一段连续内存,而表的每个节点占据的内存可以是离散的。在数组中,我们通过跳过固定的内存长度来寻找某个编号的元素。但在表中,我们必须沿着指针联系起的长链,遍历查询元素。此外,数组有固定的大小,表可以根据运行情况插入或者删除节点,动态的更改大小。表插入节点时需要从进程空间的堆中开辟内存空间,用以储存节点。删除节点可以将节点占据的内存归还给进程空间。

栈(stack)

LIFO (Last In, First Out, 后进先出)

LIFO (Last In, First Out, 后进先出)

栈的操作

栈中的每个元素称为一个frame。而最上层元素称为top frame

栈只支持三个操作,

  • pop
  • top
  • push

pop取出栈中最上层元素,栈的最上层元素变为早先进入的元素。

top查看栈的最上层元素

push将一个新的元素放在栈的最上层。

栈不支持其他操作。如果想取出栈底下的元素, 必须进行n次pop操作。

栈的应用

栈最经典的计算机应用是函数调用。每个进程都会有一个栈,每个frame中记录了调用函数的参数,自动变量和返回地址。当该函数调用一个新的函数时,栈中会 push一个frame。当函数执行完毕返回时,该frame会pop,从而进入调用该函数的原函数,继续执行。

实际使用的栈并不一定符合数据结构的栈。比如说,有的语言允许被调用函数查看非top frame的记录。

栈的实现

由于栈是限定了操作有序的元素集合,所以我们既可以在数组的基础上来实现栈,也可以在表的基础上来实现栈。如果使用数组来实现栈,我们需要预留充足的空间供栈使用,并需要一个下标来记录最上层元素的位置。

队列(queue)

First In, First Out (FIFO,先进先出)

First In, First Out (FIFO,先进先出)

队列操作

队列支持两个操作

  • 队首的元素离开队列(dequeue)
  • 新元素加入队尾(enqueue)。

队列的应用

队列在计算机中应用很广泛。一个经典的应用是消息队列(参考Linux进程间通信),实际上就是利用队列来分配有限的进程。还有FIFO文件(哦,你可以看到,这种文件叫做FIFO,肯定是和队列有关),用以实现管道传输。再比如,我们将多个打印任务发送给打印机,打印机也是使用队列来安排任务的顺序。

树(tree)

基本性质

  • 树有一个没有父节点的节点,称为根节点(root)
  • 没有子节点的节点称为叶节点(leaf)。
  • 树中节点的最大层次被称为深度。
  • 孤立的一个节点也是一棵树。
  • 拥有同一父节点的两个节点互为兄弟节点(sibling)。

严格的定义树的方法:

  1. 树是元素的集合。

  2. 该集合可以为空。这时树中没有元素,我们称树为空树 (empty tree)。

  3. 如果该集合不为空,那么该集合有一个根节点,以及0个或者多个子树。根节点与它的子树的根节点用一个边(edge)相连。

树的应用

计算机的文件系统是树的结构。在UNIX的文件系统中,每个文件(文件夹同样是一种文件),都可以看做是一个节点。非文件夹的文件被储存在叶节点。文件夹中有指向父节点和子节点的指针(在UNIX中,文件夹还包含一个指向自身的指针,这与我们上面见到的树有所区别)。在git中,也有类似的树状结构,用以表达整个文件系统的版本变化。

特殊的树

二叉树(binary)

  • 二叉树的每个节点最多只能有2个子节点
  • 每个节点有一个左子节点(left children)和右子节点(right children)。
  • 左子节点是左子树的根节点,右子节点是右子树的根节点。

二叉搜索树(bianry search tree)

如果我们给二叉树加一个额外的条件,就可以得到一种被称作二叉搜索树(binary search tree)的特殊二叉树。

二叉搜索树要求:每个节点都不比它左子树的任意元素小,而且不比它的右子树的任意元素大

(如果我们假设树中没有重复的元素,那么上述要求可以写成:每个节点比它左子树的任意节点大,而且比它右子树的任意节点小)

二叉搜索树可以方便的实现搜索算法。在搜索元素x的时候,我们可以将x和根节点比较:

  1. 如果x等于根节点,那么找到x,停止搜索 (终止条件)

  2. 如果x小于根节点,那么搜索左子树

  3. 如果x大于根节点,那么搜索右子树

二叉搜索树所需要进行的操作次数最多与树的深度相等。n个节点的二叉搜索树的深度最多为n,最少为log(n)

二叉搜索树的懒惰删除

有一种简单的关于二叉搜索树的删除替代操作,称为懒惰删除(lazy deletion)。在懒惰删除时,我们并不真正从二叉搜索树中删除该节点,而是将该节点标记为“已删除”。这样,我们只用找到元素并标记,就可以完成删除元素了。如果有相同的元素重新插入,我们可以将该节点找到,并取消删除标记。

懒惰删除的实现比较简单,可以尝试一下。树所占据的内存空间不会因为删除节点而减小。懒惰节点实际上是用内存空间换取操作的简便性。

性能的权衡-AVL树

我们在树, 二叉树, 二叉搜索树中提到,一个有n个节点的二叉树,它的最小深度为log(n),最大深度为n。

虽然完全二叉树的的时间复杂度最小,只有log(n)。但是这样的二叉树实现插入算法会比较复杂。我们将介绍一种思路相似,但比较容易实现的树状数据结构——AVL树

AVL树简介

AVL树一种特殊的二叉搜索树。AVL树要求: 任一节点的左子树深度和右子树深度相差不超过1
(空树的深度为0。注意,有的教材中,采用了不同的深度定义方法,所以空树的深度为-1)

AVL树的特性让二叉搜索树的节点实现平衡(balance):节点相对均匀分布,而不是偏向某一侧。因此,AVL树的搜索算法复杂度是log(n)的量级

AVL实现

我们在二叉搜索树中定义的操作,除了插入,都可以用在AVL树上 (假设使用懒惰删除)。如果进行插入操作,有可能会破坏AVL树的性质,但是

我们可以通过单旋照(single rotation)和双旋转(double rotation)来修正因为插入一个元素而引起的堆AVL性质的破坏

伸展树(splay tree)

前言

我们讨论过,树的搜索效率与树的深度有关。二叉搜索树的深度可能为n(即它不是完全二叉树),这种情况下,每次搜索的复杂度为n的量级。AVL树通过动态平衡树的深度,单次搜索的复杂度为log(n) (以上参考 AVL树)。

伸展树的解决方案

我们下面看伸展树(splay tree),它对于m次连续搜索操作有很好的效率。

伸展树会在一次搜索后,对树进行一些特殊的操作。这些操作的理念与AVL树有些类似,即通过旋转,来改变树节点的分布,并减小树的深度。但伸展树并没有AVL的平衡要求,任意节点的左右子树可以相差任意深度。与二叉搜索树类似,伸展树的单次搜索也可能需要n次操作。但伸展树可以保证,m次的连续搜索操作的复杂度为mlog(n)的量级,而不是mn量级。

伸展树的另一个好处是将最近搜索的节点放在最容易搜索的根节点的位置。在许多应用环境中,比如网络应用中,某些固定内容会被大量重复访问(比如江南style的MV)。伸展树可以让这种重复搜索以很高的效率完成。

堆(heap)

优先队列(priority queue)

堆(heap)又被称为优先队列(priority queue)。尽管名为优先队列,但堆不是队列

回忆一下,在队列中,我们可以进行的限定操作是dequeue(入队列)和enqueue(出队列)。dequeue是按照进入队列的先后顺序来取出元素。而在堆中,我们不是按照元素进入队列的先后顺序取出元素的,而是按照元素的优先级取出元素。

这就好像候机的时候,无论谁先到达候机厅,总是头等舱的乘客先登机,然后是商务舱的乘客,最后是经济舱的乘客。每个乘客都有头等舱、商务舱、经济舱三种个键值(key)中的一个。头等舱->商务舱->经济舱依次享有从高到低的优先级。

堆的应用

Linux内核中的调度器(scheduler)会按照各个进程的优先级来安排CPU执行哪一个进程。计算机中通常有多个进程,每个进程有不同的优先级(该优先级的计算会综合多个因素,比如进程所需要耗费的时间,进程已经等待的时间,用户的优先级,用户设定的进程优先程度等等)。内核会找到优先级最高的进程,并执行。如果有优先级更高的进程被提交,那么调度器会转而安排该进程运行。优先级比较低的进程则会等待。“堆”是实现调度器的理想数据结构。

堆的经典实现

二叉堆(binary heap)

用完全二叉树(complete binary tree)实现的堆称为二叉堆(binary heap)。

完全二叉树是增加了限定条件的二叉树。假设一个二叉树的深度为n。为了满足完全二叉树的要求,该二叉树的前n-1层必须填满,第n层也必须按照从左到右的顺序被填满。

为了实现堆的操作,我们额外增加一个要求:

  • 任意节点的优先级不小于它的子节点

主要操作

堆的主要操作是插入删除最小元素(元素值本身为优先级键值,小元素享有高优先级)。

在插入或者删除操作之后,我们必须保持该实现应有的性质:

  1. 完全二叉树
  2. 每个节点值都小于或等于它的子节点。

左倾堆(leftist heap)

知识回顾

我们之前讲解了堆(heap)的概念。堆是一个优先队列(queue)。每次从堆中取出的元素都是堆中优先级最高的元素。

在之前的文章中,我们基于完全二叉树(complete binary tree)实现了堆,这样的堆叫做二叉堆(binary heap)。binary heap有一个基本要求: 每个节点的优先级大于两个子节点的优先级。在这一要求下,堆的根节点始终是堆的元素中优先级最高的元素。此外,我们实现了delete_min()操作,从堆中取出元素;insert()操作,向堆中插入元素。

现在,我们考虑下面的问题: 如何合并(merge)两个堆呢? 一个方案是从第一个堆中不断取出一个元素,并插入到第二个堆中。这样,我们需要量级为n的操作。我们下面要实现更有效率的合并。

左倾堆

左倾堆基于二叉树(binary tree)。左倾堆的节点满足堆的基本要求,即(要求1)每个节点的优先级大于子节点的优先级

与二叉堆不同,左倾堆并不是完全二叉树。二叉堆是非常平衡的树结构,它的每一层都被填满(除了最下面一层)。左倾堆则是维持一种不平衡的结构: 它的左子树节点往往比右子树有更多的节点

哈希表(hash)

前言

哈希表(hash table)是从一个集合A到另一个集合B的映射(mapping)。映射是一种对应关系,而且集合A的某个元素只能对应集合B中的一个元素。但反过来,集合B中的一个元素可能对应多个集合A中的元素。如果B中的元素只能对应A中的一个元素,这样的映射被称为一一映射

A中元素a对应B中元素b,a被称为键值(key),b被称为a的hash值(hash value)。

应用

哈希表在计算机科学中应用广泛。比如:

  • Ethernet中的FCS(校验序列)
  • IP协议中的checksum(校验码)
  • git中的hash值

上述应用中,我们用一个hash值来代表键值。比如在git中,文件内容为键值,并用SHA算法作为hash function,将文件内容对应为固定长度的字符串(hash值)。如果文件内容发生变化,那么所对应的字符串就会发生变化。git通过比较较短的hash值,就可以知道文件内容是否发生变动。

再比如计算机的登陆密码,一般是一串字符。然而,为了安全起见,计算机不会直接保存该字符串,而是保存该字符串的hash值(使用MD5、SHA或者其他算法作为hash函数)。当用户下次登陆的时候,输入密码字符串。如果该密码字符串的hash值与保存的hash值一致,那么就认为用户输入了正确的密码。这样,就算黑客闯入了数据库中的密码记录,他能看到的也只是密码的hash值。上面所使用的hash函数有很好的单向性:很难从hash值去推测键值。因此,黑客无法获知用户的密码。

(之前有报道多家网站用户密码泄露的时间,就是因为这些网站存储明文密码,而不是hash值)

注意,hash只要求从A到B的对应为一个映射,它并没有限定该对应关系为一一映射。因此会有这样的可能:两个不同的键值对应同一个hash值。这种情况叫做hash碰撞(hash collision)。比如网络协议中的checksum就可能出现这种状况,即所要校验的内容与原文并不同,但与原文生成的checksum(hash值)相同。再比如,MD5算法常用来计算密码的hash值。已经有实验表明,MD5算法有可能发生碰撞,也就是不同的明文密码生成相同的hash值,这将给系统带来很大的安全漏洞。

HASH与搜索

hash表被广泛的用于搜索。设定集合A为搜索对象,集合B为存储位置,利用hash函数将搜索对象与存储位置对应起来。这样,我们就可以通过一次hash,将对象所在位置找到。一种常见的情形是,将集合B设定在数组下标。由于数组可以根据数组下标进行随机存取(random access,算法复杂度为1),所以搜索操作将取决于hash函数的复杂程度

如果不采用hash,而只是在一个数组中搜索的话,我们需要依次访问每个记录,直到找到目标记录,算法复杂度为n。我们可以考虑一下为什么会有这样的差别。数组虽然可以随机读取,但数组下标是随机的,它与元素值没有任何关系,所以我们要逐次访问各个元素。通过hash函数,我们限定了每个下标位置可能存储的元素。这样,我们利用键值和hash函数,就可以具备相当的先验知识,来选择适当的下标进行搜索。在没有hash碰撞的前提下,我们只需要选择一次,就可以保证该下标指向的元素是我们想要的元素。

解决HASH冲突

hash函数需要解决hash冲突的问题。举个例子,”RayJune”和”Ray”有相同的hash值,发生冲突。我们如何解决呢?

  • 一个方案是将发生冲突的记录用链表储存起来,让hash值指向该链表,这叫做open hashing。

    我们在搜索的时候,先根据hash值找到链表,再根据key值遍历搜索链表,直到找到记录。我们可以用其他数据结构代替链表。

  • open hashing需要使用指针。我们有时候想要避免使用指针,以保持随机存储的优势,所以采用closed hashing的方式来解决冲突。

    即把冲突的值放在空余的数组位置中。

图(graph)

松散的数据结构

图(graph)是一种比较松散的数据结构。它有一些节点(vertice),在某些节点之间,由边(edge)相连。节点的概念在树中也出现过,我们通常在节点中储存数据。边表示两个节点之间的存在关系。在树中,我们用边来表示子节点和父节点的归属关系。树是一种特殊的图,但限制性更强一些。

图的定义

严格的说,图G = (V,E)是由节点的集合V边的集合E构成的。一个图的所有节点构成一个集合V。一个边可以表示为(v1,v2),其中v1/v2属于V,即两个节点。如果(v1,v2)有序,即(v1,v2)与(v2,v1)不同,那么图是有向的(directed)。有序的边可以理解为单行道,只能沿一个房向前进。如果(v1,v2)无序,那么图是无向的(undirected)。
无序,那么图是无向的(undirected)。无序的边可以理解成双向都可以行进的道路。一个无序的边可以看作连接相同节点的两个反向的有序边,所以无向图可以理解为有向图的一种特殊情况。

图的一个路径(path)是图的一系列节点w1,w2,…,wn,且对于1≤i<n,有(wi,wi+1)∈E。也就是说,路径是一系列的边连接而成,路径的两端为两个节点。路径上边的总数称为路径的长度。乘坐地铁时,我们会在选择某个路径,来从A站到达B站。这样的路径可能有不止一条,我们往往会根据路径的长度以及沿线的拥挤状况,来选择一条最佳的路线。如果存在一条长度大于0的路径,该路径的两端为同一节点,那么认为该图中存在环路(cycle)。很明显,上海的地铁系统中存在环路。

如果从每个节点,到任意一个其它的节点,都有一条路径的话,那么图是连通的(connected)。对于一个有向图来说,这样的连通称为强连通(strongly connected)。如果一个有向图不满足强连通的条件,但将它的所有边都改为双向的,此时的无向图是连通的,那么认为该有向图是弱连通(weakly connected)。

如果将有火车站的城市认为是节点,铁路是连接城市的边,这样的图可能是不连通的。比如北京和费城,北京有铁路通往上海,费城有铁路通往纽约,但北京和费城之间没有路径相连。

图的应用

这样的一种数据结构是很常见的。比如计算机网络,就是由许多节点(计算机或者路由器)以及节点之间的边(网线)构成的。城市的道路系统,也是由节点(路口)和边(道路)构成的图。地铁系统也可以理解为图,地铁站可以认为是节点。基于图有许多经典的算法,比如求图中两个节点的最短路径,求最小伸展树等。

七桥问题中的图是无向的。城市中的公交线路可以是无向的,比如存在单向环线

图的经典研究是柯尼斯堡七桥问题(Seven Bridges of Königsberg)。柯尼斯堡是现今的加里宁格勒,城市中有一条河流过,河中有两个小岛。有七座桥桥连接河的两岸和两个小岛。送信员总想知道,有没有一个办法,能不重复的走过7个桥呢?

柯尼斯堡的可以看作由7个边和4个节点构成的一个图

这个问题最终被欧拉巧妙的解决。七桥问题也启发了一门新的数学学科——图论(graph theory)的诞生。欧拉的基本思路是,如果某个节点不是起点或者终点,那么连接它的边的数目必须为偶数个(从一个桥进入,再从另一个桥离开)。对于柯尼斯堡的七桥,由于4个节点都为奇数个桥,而最多只能有两个节点为起点和终点,所以不可能一次走完。

图的实现

用二维数组

一种简单的实现图的方法是使用二维数组。让数组a的每一行为一个节点,该行的不同元素表示该节点与其他节点的连接关系。如果(u,v)∈E,那么a[u][v]记为1,否则为0。

这种实现方式所占据的空间为O(|V|2)为节点总数。所需内存随着节点增加而迅速增多。如果边不是很密集,那么很多数组元素记为0,只有稀疏的一些数组元素记为1,所以并不是很经济。

用邻接表

更经济的实现方式是使用邻接表(adjacency list),即记录每个节点所有的相邻节点。对于节点m,我们建立一个链表。对于任意节点k,如果有(m,k)∈E,就将该节点放入到对应节点m的链表中。邻接表是实现图的标准方式。

拓扑排序

背景

以《文明》系列游戏背景来展开,该游戏有科技树这个概念,即完成了某个科技才能完成与之对应的下一个科技

一个有趣的问题是,如何找到合法的序列呢?当我们在设计计算机玩家时,很可能需要解决这样一个问题。

图(graph)中的拓扑排序算法(Topological Sort)可以给出一个合法序列。虽然在游戏中被称为“科技树”,但“科技树”并不符合数据结构中的树结构。在数据结构中,树的每个节点只能由一个父节点,整个树只有一个根节点。因此,“科技树”是一个不折不扣的图结构。此外,该树是一个有向的无环(acyclic)图。图中不存在环 (cycle, 环是一个长度大于0的路径,其两端为同一节点)。

应用

拓扑排序利用了一个事实,即在一个无环网络中,有一些节点是没有箭头指入的,比如科技树中的一神教、封建主义、工程。它们可以作为序列的起点。

  • 选择没有箭头指入的节点中的任一个,可以作为合法序列的起点,放入序列。
  • 当我们将某个节点放入序列后,去掉该节点以及从该节点指出的所有箭头。在新的图中,选择没有箭头指向的节点,作为序列中的下一个点。
  • 重复上面的过程,直到所有的节点都被放入序列。

对于每个节点,我们可以使用一个量入度(indegree),用来表示有多少个箭头指入该节点。当某个节点被删除时,图发生变化,我们需要更新图中节点的入度。

对于每个节点,我们可以使用一个量————入度(indegree),用来表示有多少个箭头指入该节点。当某个节点被删除时,图发生变化,我们需要更新图中节点的入度。

最短路径与贪婪

前言

图是由节点和连接节点的边构成的。节点之间可以由路径,即边的序列。根据路径,可以从一点到达另一点。在一个复杂的图中,图中两点可以存在许多路径。

那么问题来了,我们如何确定哪条路径最短呢?

这个问题又异常复杂,因为网络的构成状况可能很复杂。

一个最简单的思路,是找出所有可能的从A到B的路径,再通过比较,来寻找最短路径。然而,这并没有将问题简化多少。因为搜索从A到B的路径,这本身就是很复杂的事情。而我们在搜索所有路径的过程中,有许多路径已经绕了很远,完全没有搜索的必要。比如从上海到纽约的路线,完全没有必要先从上海飞到南极,再从南极飞到纽约,尽管这一路径也是一条可行的路径。

所以,我们需要这样一个算法:它可以搜索路径,并当已知路径包括最短路径时,即停止搜索。我们先以无权网络为例,看一个可行的最短路径算法。

无权网络

无权网络(unweighted network)是相对于加权网络的,这里的”权”指的是权重

每条边的耗费相同,都为1。路径的总耗费即为路径上边的总数。

这种情况很简单,就不再多说了。

加权网络

在加权网络中(weighted network),每条边有各自的权重。当我们选择某个路径时,总耗费为路径上所有边的权重之和

加权网络在生活中很常见,比如从北京到上海,可以坐火车,也可以坐飞机。但两种选择耗费的时间并不同。再比如,我们打出租车和坐公交车,都可以到市区,但车资也有所不同。在计算机网络中,由于硬件性能不同,连接的传输速度也有所差异。加权网络正适用于以上场景。无权网络是加权网络的一个特例。

这个问题看起来和无权网络颇为类似。但如果套用上面的方法,我们会发现,记录中的节点并不一定是最短距离

这里要用到的算法是经典的Dijkstra算法。本质上,每个邻接点记录的,是基于已知点的情况下,最好的选择,也就是所谓的“贪婪算法”(greedy algorithm)。当我们贪婪时,我们的决定是临时的,并没有做出最终的决定。转换某个点成为已知点后,我们增加了新的可能性,贪婪再次起作用。根据对比。随后,某个邻接点成为新的“贪无可贪”的点,即经由其它任意邻接点,到达该点都只会造成更高的成本; 经由未知点到达该点更不可能,因为未知点还没有开放,必然需要经过现有的邻接点到达,只会更加绕远。好吧,该点再也没有贪婪的动力,就被扔到“成功人士”里,成为已知点。成功学不断传染,最后感染到目标节点B,我们就找到了B的最短路径。

RSA加密与破解

核心就是:RSA安全的关键在于很难对一个大的整数进行因子分解

最起码是在量子计算机出现之前~

由此可以看出数学与编程的联系。数学可以是程序员军火库中有力的武器。加密、解密这一事关IT安全的大课题,却和数论这一纯粹数学学科发生奇妙的关系。RSA算法的数学基础在于欧拉定理。这一诞生了几百年没有什么实用性的数学理论,却在网络时代,找到自己的栖身之处

文章标题:纸上谈兵-算法与数据结构小记

文章作者:RayJune

时间地点:又玄图书馆

原始链接:http://www.rayjune.xyz/2017/03/07/algorithm-data-structure-note/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。