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://rayjune.xyz/2017/03/07/algorithm-data-structure-note/

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