您好、欢迎来到现金彩票网!
当前位置:刘伯温论坛 > 图归约机 >

《算法(第四版)》读书笔记(完结)

发布时间:2019-05-20 20:43 来源:未知 编辑:admin

  大一下的时候学过数据结构,但是面试的时候发现一些基础知识都忘的差不多了,所以打算借这本书重新学习一下算法与数据结构.使用的语言是JAVA.IDE是Eclipse,相关设置请看以下两篇文章:

  注意数据文件如果直接用记事本看是不会显示换行的,可以用notepad++等软件查看.

  遇到右括号时,弹出一个运算符,弹出所需数量的操作数,并将运算结果压入操作数栈

  :先归并排序,然后对于a[i],在ji的范围内用二分查找寻找a[j]=-a[i],时间复杂度为O(NlogN)

  :先归并排序,然后对于a[i]和a[j](j从i+1开始遍历),在kj的的范围内用二分查找寻找a[k]=-a[i]-a[j],时间复杂度为O(N^2logN)

  :对于给定的两个触点,判断它们所在的连通分量是否相同,将查找连通分量称为

  :使用一个id数组,保证在同一连通分量中的所有触点在id数组中的值是全部相同的.

  :改变id数组的定义,每个触点所对应的id元素都是同一个分量中另一个触点的名称,这种联系称为

  ,即链接指向子集的触点.当且仅当两个触点的根触点相同时它们存在于同一个连通分量中.

  :分别对p和q进行find操作,如果对应值相等不做操作,不相等则将p的根触点链接到q的根触点上.

  :为了防止树极度不均衡,记录每一棵树的大小并总是将较小的树连接到较大的树上.在程序中引入size数组记录各个触点的根节点所对应的分量的大小.

  :分别对p和q进行find操作,如果对应值相等不做操作,不相等则判断对应值的根节点分量的大小,将小树的根触点链接到大树的根触点上.

  :为find函数添加一个循环,将在路径上遇到的所有节点都直接链接到根节点.

  .找到数组中最小的元素,将它和数组的第一个元素交换位置.然后在剩下的元素中重复这一步骤.特点是运

  .遍历数组中的每一个元素,将它与左边的元素比较并插入到合适的位置中,这会使该元素

  的.因为插入排序总需要找到某元素在其左边序列的位置,所以可以用二分查找进行这一过程,称为

  .插入排序的缺点在于只能交换相邻的元素.希尔排序的思想是使数组中任意间隔为h的元素都是有序的,即

  来决定h的值,最后一个h必须为1.具体步骤是对于每一个h,遍历数组中i=h~N的所有a[i],将a[i]与a[i-h],a[i-2h]......进行插入排序,然后按递增序列减小h,直到h=1为止.

  起来.在归并前可以添加判断条件,如果a[mid]=a[mid+1]则跳过归并.

  如果其中半边的元素大于另外半边的元素则放入另外半边的元素,并令另外半边的下标加1.

  :创建辅助数组,递归地对原数组的左半边和右半边排序后进行归并操作,终止条件为high=low.

  中方法的调用过于频繁,所以用不同的方法处理小规模问题能改进大多数递归算法的性能.使用

  处理小规模(比如长度小于15)的子数组一般可以将归并排序的运行时间缩短10%~15%.

  :创建辅助数组,从两两归并开始,每一轮归并中子数组的大小都会翻倍,直到可以将原数组分为两个子数组归并为止.这种方法很适合用

  可以证明没有任何排序算法能用少于NlgN次比较将数组排序,这意味着归并排序是一种渐进最优的基于比较排序的算法.

  变为两个子数组,将两部分独立地排序,使得切分点左边的所有元素都不大于它,右边的所有元素都不小于它.

  ,然后从数组的左端向右扫描,找到一个大于等于它的元素,再从数组的右端向左扫描,找到一个小于等于它的元素,交换它们的位置.如此继续,直到两个指针

  的办法,将数组分为小于切分元素,等于切分元素和大于切分元素三部分,它将排序时间降到了

  是一个空链接,或者是一个有左右两个链接的结点,每个链接都指向一棵子二叉树.

  堆的操作会进行一些简单的改动,打破堆的状态,然后再按照要求将堆的状态恢复.这个过程叫做堆的

  而被打破,可以通过交换它和它的两个子结点中的较大者来恢复堆.位置k的结点的子结点为

  :从堆顶删去最大的元素,并将最后一个元素放到顶端,减小堆的大小并让这个元素

  对于一个含有N个元素的基于堆的优先队列,插入元素和删除最大元素的时间复杂度都是

  :将最大的元素a[1]和末尾元素a[N]交换,将堆的大小-1,并对交换到堆顶的

  因为大多数在下沉排序期间重新插入堆的元素会被直接加入到堆底,所以可以使用

  的方法优化,即直接提升较大的子结点直至到达堆底,然后再使元素上浮到正确的位置.

  的,即不会改变重复元素的相对位置.选择排序,希尔排序,快速排序和堆排序则不是稳定的.

  :求两组数列的Kendalltau距离,即在两组排列中相对顺序不同的数字组数.某个排列和标准排列的Kendalltau距离就是其中逆序数对的数量.可以由其中一个排列确定一个标准索引,然后以这个标准索引为标准对两组数列进行

  ,当切分点j小于N/2时只用切分右数组,切分点j大于2/N时只用切分左数组,切分点j=N/2时a[j]即为中位数.如果是

  ,则可以将数据用二进制表示,根据最大位是0或1划分为两个文件,然后不断对包含中位数的那个文件做此操作,直到可以将剩余的数全部读进内存时再使用快速排序.

  ,它给出了以该结点为根的子树的结点总数.size(x)=size(x.left)+size(x.right)+1

  的二叉查找树表示.如果将一棵二叉查找树的所有键按从左到右的顺序投影到一条直线上,那么会得到一条

  指向一个含有被查找的键的新结点,并更新搜索路径上每个父结点中结点计数器的值.两者的时间复杂度都为

  :含有一个键和两条链接,左链接指向的2-3树中的键都小于该结点,右链接指向的2-3树中的键都大于该结点

  :含有两个键和三条链接,左链接指向的2-3树中的键都小于该结点,中链接指向的2-3树中的键都位于该结点的两个键之间,右链接指向的2-3树中的键都大于该结点

  :先将键和根结点中的键比较,如果它和其中任意一个相等,查找命中,否则根据比较的结果找到指向相应区间的链接,并在其指向的子树中

  ,再把中间插入到它的父结点中,此时父结点也为一个4-结点,在这个结点上进行相同的变换,一直向上直到遇到2-结点或根结点

  .2-3树的缺点是具有两种结构的结点,因此需要大量代码实现,额外开销很大

  是用来实现2-3树的一种简单的数据结构.它的基本思想是用标准的二叉查找树和一些额外的信息来表示2-3树.树中的链接被分为两种类型:

  红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树,满足这样定义的红黑树和相应的2-3树是一一对应的:

  (将由红链接相连的结点合并),所以能够同时实现二叉查找树中简洁高效的查找方法和2-3树中高效的平衡插入算法

  右链接也就是将两个键中较大者的左结点变为较小者的右结点,并将较大者作为根结点,较小者作为它的左结点.

  :如果新键小于老键,新增一个红链接的结点即可.如果新键大于老键,新增的结点会产生一条红色的右链接,将其左旋转.

  :新键被连接到3-结点的右链接,直接将3-结点的两条链接都由红变黑,就得到了一棵由3个结点组成的平衡树

  :新键被连接到最左边的空链接,即产生了两条连续的红链接,只需将上层的红链接右旋转即可变为情况2

  :此时产生一左一右两条连续的红链接,只需将下层的红链接左旋转即可变为情况3

  不断地将红链接由中间键传递给父结点,直至遇到一个2-结点或根结点时,插入就完成了

  是由一组顶点和一组能够将两个顶点相连的边组成的,一般用0至V-1表示一张含有V个顶点的图中的各个

  是一种能够将所有结点分为两部分的图,其中图的每条边所连接的两个顶点都分别属于不同的部分.

  来表示图.它将每个顶点的所有相邻顶点都保存在该顶点对应的元素所指向的一张链表中.它使用的

  的边组成的,每条有方向的边都连接着有序的一对顶点.在有向图中,一个顶点的

  为指向该顶点的边的总数.用vw表示有向图中一条由v指向w的边.

  由一系列顶点组成,对于其中的每个顶点都存在一条有向边从它指向序列中的下一个顶点.

  来表示有向图,用顶点v所对应的邻接链表中包含一个w顶点来表示边vw.每条边都只会在其中出现一次.DFS和BFS同样可用于有向图.

  :给定一幅有向图,将所有的顶点排序,使得所有的有向边均从排在前面的元素指向排在后面的元素.即有

  ,可以基于DFS,一旦找到一条边vw且w已经存在于栈中,就找到了一个环.

  的.如果一幅有向图中的任意两个顶点都是强连通的,则称这幅有向图也是强连通的.两个顶点是强连通的当且仅当它们都在一个普通的有向环中.

  :在一幅加权图中,给定任意的切分,它的横切边中的权重最小者必然属于图的最小生成树.

  的特殊情况.即找到一种切分,它产生的横切边均不为黑色,将它权重最小的横切边标记为黑色,直到标记了V-1条黑色边为止.不同之处在于

  一开始最小生成树只有一个顶点,然后会向它添加V-1条边.每次总是将下一条

  不仅删除失效的边,而是仅保存非树顶点到树顶点的边中权重最小的那条,并在每次加入新顶点后检查是否需要更新.所需

  处理它们,将边加入最小生成树中,加入的边不会与已经加入的边构成环,直到树中含有V-1条边为止.每一步总是连

  是指检查从顶点s到w的最短路径是否是先从s到v,然后再由v到w,即.如果是,则更新,如果不是,则称这条边

  :当且仅当对于从v到w的任意一条边e,这些值都满足distTo[w]=distTo[v]+e.weight()时它们是最短路径的长度.这证明了判断是否为最短路径的

  首先将distTo[s]初始化为0,distTo[]中的其他元素初始化为起点s到该顶点的距离,注意如果不相邻则为正无穷.

  重复2,直到所有的顶点都在树中或者所有的非树顶点的distTo[]值均为无穷大.

  中给定起点s,从s无法到达任何负权重环,可以解决其中的单点最短路径问题

  将distTo[s]初始化为0,其他distTo[]元素初始化为无穷大,以任意顺序放松有向图的所有边,重复V-1轮

  的简单排序方法.它要求数组a[]中的每个元素都保存一个字符串和一个组号,原来元素是依据字符串排列的,现在希望按组号排列,在组内保持原顺序.键索引计数法排序N个键为0到R-1之间的整数的元素需要访问数组

  :使用一个数组count[]计算每个键出现的频率.如果键为r,就将count[r+1]加1.

  :任意给定的键的起始索引均为所有较小的键所对应的出现频率之和,只需循环count[r+1]+=count[r]这个语句即可转换出一张索引表.

  :有了索引表后,将所有元素移动到一个辅助数组aux[]中进行排序.每次移动后将count[]中对应元素的值加1.这保证了这种排序的

  假设长度为W)排序可以通过从右向左以每个位置的字符作为键,用键索引计数法将字符串排序W次实现.这依赖于键索引计数法的稳定性.对于基于R个字符的字母表的N个以长为W的字符串为键的元素,LSD需要访问

  .对于基于R个字符的字母表的N个平均长度为w的字符串,MSD需要访问8N+3R到7wN+3wR之间次数组.

  ,仅在中间子数组的中的下一个字符继续递归排序.它能够很好地处理等值键,有较长公共前缀的键,取值范围较小的键和小数组.另外它不需要额外的空间.

  的每个结点都有R条链接,R为字母表的大小.但是一般其中都含有大量的空链接,可以被忽略.每条

  给定字符串键所对应的值的方式就是从根结点开始检查某条路径上的所有结点,这意味着到达树中表示尾字符的结点或者一个空链接.

  之前需要先进行一次查找,如果遇到了空链接则为键中还未被检查的每个字符创建一个对应结点,如果到达了尾字符结点则将该结点的值设为要插入的键所对应的值.

  ,方法的参数是结点和该结点关联的字符串.如果一个结点的值非空,就将它相关联的字符串加入队列,然后递归访问它的链接数组所指向的所有可能的字符结点.

  一个键值对,先找到键所对应的结点并将它的值设为空,如果它有指向子结点的非空链接则删除结束,如果它的所有链接均为空就从数据结构中删去这个结点,再检查它的父结点的所有链接是否为空.

  :用来避免R向单词查找树过度的空间消耗.每个结点都含有一个字符,三条链接和一个值.三条链接对应着当前字母小于,等于和大于结点字母的所有键.所需的空间在3N到3Nw之间.查找未命中平均需要比较字符~lnN次.

  就是遍历文本字符串,如果某字符和模式的第一个字符匹配则移动指向模式的指针,否则移动指向文本的指针.这种方法在最坏情况下需要

  (注:书中用确定有限状态自动机DFA的思想来讲解,个人感觉不好理解,本文用了大一学数据结构时的解释方法):

  :当出现不匹配时,就能知晓一部分文本的内容,可以利用这些信息避免将指针回退到所有已知字符之前.

  .其中next[0]=-1,next[1]=0,next[j]表示模式字符串中第0位到第j-1位中相同的最长前缀和最长后缀的长度.next数组可以用模式匹配的思想编程得到.

  :目标串的指针不变,若next[j]=0,则将模式字符串右移j-next[j]位个字符,用模式的第next[j]个字符与文本的第i个字符比较.若next[j]=-1,则将模式字符串右移j+1个字符,用第0个字符与文本的第i+1个字符比较.

  :如果根据next数组回退之后的位置的字符和现有字符相同,则必定是不匹配,仍要继续回退,因此建立nextval数组,将重复字符的回退位置都设为第一个该字符的回退位置.

  KMP算法适用于在重复性很高的文本中查找重复性很高的模式,它访问的字符不会超过

  使用数组right[]记录字母表中的每个字符在模式中出现的最靠右的地方,不存在则为-1.含义是如果该字符出现在文本中且在查找时造成了一次匹配失败,模式应该向右跳跃多远.

  如果造成匹配失败的字符不包含在模式中,则将模式字符串向右移动j+1个位置

  :这是一种基于散列的算法.长度为M的字符串对应着一个R进制的M位数,将该数除以一个随机的素数Q并取余就可以将它保存在大小为Q的散列表中.

  :在文本中将子字符串右移一位,对应的M位数操作就是将它减去第一个数字的值,乘上R,再加上最后一个数字的值.又因为在每次算数操作之后取余等价于在所有算数操作完成后取余,因此只需对上述操作的每一步先取余就可以得到下一位的子字符串的散列值.

  :为了避免有多个子字符串有相同散列值,可以将Q设为一个大于10^20的值,这样冲突的概率将小于10^-20.

  :如果文本中的当前字符和当前字母表中的字符匹配,NFA可以扫过文本中的字符并由

  集合,然后如果有字符匹配了集合中的状态,就将集合改为这个字符通过匹配转换后到达的状态,再加上这些状态通过转换可达的状态.

  判定一个长度为M的正则表达式所对应的NFA能否识别一段长度为N的文本所需的时间在最坏情况下和

  (将C(B)转化回B)组成,用B表示比特流中比特的数量,则C(B)/B称为

  不存在能够压缩任意比特流的算法,因此无损压缩算法必须尽量利用被压缩的数据流中的

  (小规模字母表,较长的连续相同的位或字符,频繁使用的字符,较长的连续重复的位或字符).

  的基本原理是用长度代替具有相同值的连续符号,连续符号构成了一段连续游程.适用于含有较长游程的数据,比如高分辨率的位图.

  的过程是:先找到频率最小的两个结点,然后创造一个以两者为子结点且频率为两者之和的新结点,不断重复这个过程知道所有结点被合并为一棵单词查找树.

  第六章介绍了一些较为复杂的算法,不再记录在此文中.由于比赛,考试等因素的影响,历时三个月总算把这本《算法》粗略地看了一遍,复习了数据结构的同时也了解了很多新算法.接下来准备通过leetcode来加深对算法的理解和编程能力,这一过程也会在博客中进行记录.

http://aw2400.net/tuguiyueji/1.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有