搜索

[[ 其他百度资源综合 ]] 算法导论视频教程

[复制链接]
查看: 10474|回复: 232

1541

主题

2

好友

8966

积分

神功绝世

Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20

积分
8966
发表于 2018-8-17 08:00:03 | 显示全部楼层 |阅读模式
教程目录:
1.课程简介及算法分析
2.渐近符号、递归及解法
3.分治法(1)
4.快排及随机化算法
5.线性时间排序
6.顺序统计、中值
7.哈希表
8.全域哈希和完全哈希
9.二叉搜索树
10.平衡搜索树
树的结构,如果不能保持平衡,那么其搜索性能会大大打折扣,而本节课介绍了几种经典的平衡树,如AVL,2-3-4tree,红黑树等等,然后着重讲了红黑树,接下来就红黑树的基本性质,作一些简短的总结。

首先,红黑树除了具有BST的基本性质外,还额外拥有以下的五大基本性质:

1)每个结点有一个色域,一个结点要么为黑结点,要么为红结点

2)根节点为黑结点

3)每个叶子结点都为黑结点(无键值)

4)每个红结点的父亲都为黑结点,即不可能出现两个红色结点相连的情况

5)从根节点到任意叶节点的路径中的黑色结点数目相等,这个数目也称为黑高度

由以上5点性质,可以保证红黑树的高度为O(lgn),证明如下:

将红黑树的所有红结点,都与其父节点(由性质四得其父节点必定为黑)合并,可以得到一颗2-3-4 tree(即每个结点的子节点数目为2~4个),由数据结构知识可得,原红黑树的叶子结点个数为带键值结点个数n+1,假设整棵树高度为h,那么叶子结点数应为h^2~h^4,因此有h^2<=n+1<=h^4,即此时树高度最高也只有log n+1,即树的黑高度为log n+1,根据性质3,树最高情况也不过是红黑相间的时候,因此其高度最高只有2log n+1 ,即树的高度为O(lgn)。

红黑树的查询操作和普通BST一样,而删除和插入操作则相对复杂,因为我们要保证红黑树的5大性质,为什么需要保证这五大性质呢?因为这五大性质是红黑树为平衡树的保证,能够保证红黑树的高度为Olgn,这样红黑树的基本操作(删,插,查)都可以保证在Olgn的时间复杂度内完成。

接下来简单介绍一下插入操作是如何完成的,删除操作思路类似:

插入操作的原理就是插入一个红结点,然后通过向上重染色和旋转的方式维持红黑树的性质

这里有三种情况

case1  直线型 且祖父结点为黑,父节点和父亲兄弟结点为红 将祖父结点的黑传递到两个红子节点   每次向上传      递2个结点,树高度2lgn 所以操作为O(lgn)
case2  zigzag Z型 父亲兄弟结点为黑 旋转为case3   O(1)的旋转
case3  zigzig直线型 旋转

由以上三种情况可得,插入的时间复杂度为重染色的Olgn+不超过3次的O(1)的旋转操作

这里值得一提的是,在实际的运用中,虽然向上重染色理论上花费的时间多于旋转,但是当多个用户并发查询访问红黑树的时候,重染色并不会影响查询,因为用户并不关心每个结点的颜色,但是旋转需要锁定该子树及其结点,可能会影响并发查询的操作。

最后,就AVL和红黑树做一下比较,就平衡程度而言,AVL是追求的绝对平衡,任意叶子结点的深度不会多于其他叶子结点深度+1,而红黑树只要求局部平衡,其红黑性保证了其平衡性,因此在维护平衡方面,红黑树只需要不超过3次旋转即可,这一点是AVL树所做不到的,但查询方面,由于AVL是绝对平衡,因此效率会略高于红黑树,实际应用中这一点并不明显,就统计性能而言,红黑树会优于AVL,而C++ STL中的set、multiset、map、multimap等,都是红黑树的一种变体。

值得一提的是,平衡树都是动态的数据结构,其优势在于动态操作下,也能保持优越的查询效率,如果是静态数据,那么使用hash表效率会更高一些。

11.扩充的数据结构、动态有序统计和区间树
本节课主要讲了如何构造自己想要的数据结构,或者扩充已有数据结构的功能,以实现想要的特定功能

比如设计一个动态结构,满足功能寻找第k大的数

其做法是维护每个结点的子结点个数来推导其秩,而不维护其秩,因为动态操作会使得其难以维护
红黑树的插入操作 1.树插入 2.rebalance

构造自己需要的扩充数据结构的基本流程

1.选择一个基本的数据结构 例如红黑树
2.决定要添加到结点的基本信息  例如实现查询第k大数功能,应添加的基本信息为所有子树结点之和,而非直接保存该结点键值的秩
3 维持 插入+旋转/删除+旋转
4 封装为函数,实现其功能

12.跳跃表
跳跃表是一种简单又有趣的动态搜索数据结构,其主要优点在于其易于实现,而且很好的保证了其具有高效的性能,即2*O(lgn)的搜索性能

在此之前我想首先谈谈链表,链表的优点在于其插入和删除只需要常数项的时间(加上查找该元素需要额外的O(n)时间),但是其查找效率只有O(n),这里顺带补充一下链表类的问题,以下先给出两个BAT公司面试时热衷于考的两个链表经典问题:

1.如何快速查找单向链表倒数第m个元素

2.如何快速判断一个单向链表是否存在环

对于链表类问题,其核心思想不外乎两点,1是开双指针(甚至多指针),2是开双链表(甚至多链表),其实以上两个问题开双指针便能巧妙地解决,第一个问题,先开一个指针走m步,然后再开一个指针同步走,当前一个指针走到链表末端时,后一个指针就正好指向倒数第m个元素了,第二个问题,开一个快指针和一个慢指针,快指针每次移动两步,慢指针每次移动一步,如果存在环,那么快指针一定会追到慢指针,可以想象两个人在操场赛跑,快的人跑了很久之后会超慢的人一圈。

接下来我们继续谈跳跃表,其实跳跃表用到的就是第二个思路,开双链表甚至多个链表

首先考虑建立两个链表L1和L2,L1为快表,即只保存部分元素,L2为慢表保存全部元素,注意,以下提到的链表均为排好序的链表

当我们要搜索某一元素时,我们先走快表,因为快表只保留了部分元素,所以是跳跃前进的,直到快表走过该元素,我们再退回快表前一个结点换到慢表继续走,这样效率显然比在慢表上进行线性查找要好一些,这里的快慢表就像美国地铁的快慢线地铁一样,快线的地铁只在几个站停顿,而慢线会在所有站停顿,乘客可以先乘快线到一个最接近目的地的前一个站,再转乘慢线到达该地

那么问题来了?
如何建表L1和 L2呢?L2无疑是一条包含所有结点的单向链表,那么L1应该设置多少个结点最为合理呢,直观上感受L1应该是均匀分布最好,那么是以怎样的密度分布最合适呢?

我们不难得出查找时间上界为|L1|+|L2|/|L1|+换乘的常数,这里|L1|表示L1的长度(最坏情况就是L1走到末端后,走回一个节点然后进入L2,因为L2可以看做被L1分成了L1个段,所以每段长度为|L2|/|L1|,所以为|L1|+|L2|/|L1|+换乘的常数),因为L2长度为n(包括整个链表),换乘即链表L1向下走到L2的时间,为常数,所以我们的目标是要使得|L1|+n/|L1|最小,即|L1|为sqrt(n)时最优(可以求导得出或者通过其他数学方法,证明略),此时时间消耗为2*sqrt(n),即每隔sqrt(n)设立一个快表的结点,共sqrt(n)个快表结点

什么?sqrt(n)还不过瘾?

那么我们还能做怎样的优化呢?答案是加更多的链表,我们看看三条链表应是多少,直觉告诉我们是3*n的1/3次方
其实,可以证明k条链表的时候为k*n的1/k次方

因为n是常数,那么k多大比较合适呢?lgn! 让我们看看k取lgn的时候为多少,即lgn*n^(1/lgn)为多少,即求lgn*n^logn(2),还记得我们计算递归时间复杂度时的换底公式吗?这里n^logn(2)即2^logn(n)即2^1,即2,所以整个时间复杂度为2*lgn,这是一个非常好的性能。

这种情况下的跳跃表称为理想跳跃表,每一层数量减少一半,总共lgn层链表,从最上级链表开始搜,搜不到就向下,最多下logn层,每层最多搜2个元素,所以搜索复杂度为O(2lgn)

那么问题又来了,如何动态维护这样一个跳跃表呢?
先看删除功能,删除功能只要从上级链表搜到之后,就可以直接删除,并向下将所有链表的该结点都删除,这个比较简单,那么插入呢?

插入(x) 先search(x)在底表的位置然后插入该元素,是否结束了呢?不,因为在某一段连续插入若干个结点后,这一段会变得非常长,整个跳跃表的平衡结构无疑会被打破,那么如何维护理想线段表的结构呢?
1.保持每段之间的理想距离,如果距离过大,就从中间分割,然后将中点上升一层结点

这个方法从直观上看非常巧妙,但是实行起来却有一定难度,因为你必须实时记录每一段的长度

2.采用我们最喜欢的随机化算法,抛硬币 如果正面,就把这个结点提升一个level(即把该结点也加入上一级的链表中),再抛硬币(看是否持续提升level),因为两个相邻链表的长度之比为1:2,而硬币出正面的概率也是50%,事实证明这样做是可行的,这里值得一提的是,老师在这节课发了两个硬币给同学,一个利用抛硬币产生随机数,一个利用抛硬币决定当前插入结点是否需要提升level,在课堂上直接做起了实验,整个课程氛围也很好,也让同学们都对该算法有了直观的理解,这一种教学方式很值得借鉴

注意,这里需要考虑一个特殊情况,就是当我们插入的元素为最小的元素时,如果它没有提升一个level,那么上级链表的开头就不是第一个元素,这样也会打乱整个跳跃表的理想结构,因此我们需要打个补丁:即把一个负无穷值插到所有链表头,这样就算插入了一个最小的元素也能保证每个表是以负无穷开始,即每个链表都可以从最左边开始。

在课堂上,通过实验表明算法2似乎在平均情况下可以得到一个很好的跳跃表,其实不仅仅是平均情况可以得到一个好的跳跃表,在绝大多数情况都可以得到一个好的跳跃表.

可以证明,得到一个好的跳跃表的概率P>=1-O(1/n^a)  这里a是一个介于0到1的参数,与n有关,在课堂的最后,老师花了尽20分钟的时间来证明,具体证明方式我们这里略过(其实是我根本没看懂其证明过程 逃~~)

13.平摊分析,表的扩增,势能方法
先通过表的扩增这一例子来引入今天的主题——平摊分析和势能分析

一个哈希表的大小应该为多少比较合适?

theta(n)比较合适
可是万一我们不知道n是多大呢
使用动态表解决  溢出就建立一个大小翻倍的空间,然后复制过去
这样做插入的最坏时间复杂度为n

让我们看看平均的时间复杂度,每次基本插入操作为1,空间溢出时需要开一个更大一倍的空间,并复制当前的元素过去,所以空间溢出时所需要的时间为2的i次方(i为第几次溢出)

所以其真实的时间消耗为n+sigma(2^i)   0<=i<=lg(n+1)  即3n
因此其实插入的时间复杂度为O(1)

尽管有时会有巨大开销,但是会被平均的开销平摊掉,这就是平摊分析

平摊分析:平均操作复杂度不高,尽管有些操作会有较高的复杂度

三种类型的平摊方法:
1.聚集分析
2.记账方法(accounting)
3.势能分析
2.3它们为每一个操作分配了特点的平摊代价

记账方法:
想象自己担任了一个会记
对第i个操作收费为ci
收益个虚构的平摊代价
每一步运算需要花费1$
未用到的余款就被存到银行,用于偿付以后的操作

如每次插入收费为3,插入消耗1,剩下的2存入银行为表翻倍时做准备,要始终保证银行的金额为正

即提前平摊,总能支付扩充表的费用,这样某一个高开销的操作会被平摊掉

势能方法:
算法分析里最漂亮的产物之一
刚开始数据结构状态为D0
操作i的代价为ci
操作i可以看作把数据结构由Di-1转化为Di

定义势能函数
将数据结构的集合定位实数值
D0 = 0 初始的势为0
所有Di >=0,我们不能让势低于0
定义平摊代价为Ai,对势能Di有Ai=Ci+Di-Di-1
Di-Di-1 部分是势能的改变量,如果其>=0 那么Ai>ci 我收取的费用超过了实际的花费,即操作i储存了后面数据结构所需的功
如果势能的改变量<0,即我们用存储的势能转化为能量来帮助完成操作i

记账方法考虑的是平摊代价
而势能分析考虑的是银行存款(存储势能)

有sigmaAi=sigma(ci+Di-Di-1)=sigma(ci+Dn-D0)
D0为0,Dn大于等于0,所以左边大于右边,是实际代价的一个上界

我们再次以表的扩增为例感受一下势能分析
我们的势能函数为2i-2^ceil(lgi)  
如何推导出这样的势能函数的?
定义势能函数难度低于定义平摊代价
Di>=0
第i个操作的平摊代价Ai=Ci+Di-Di-1=  i+2i-2^ceil(lgi)-(2i-2-2^ceil(lgi-1))(刚好i是2的幂)
  1+2i-2^ceil(lgi)-(2i-2-2^ceil(lgi-1))

case1 i-1是2的幂,那么Ai=i+2-2(i-1)+(i-1)=3
case2 i-1不是2的幂 那么Ai=1+2i-2^ceil(lgi)-(2i-2-2^ceil(lgi-1))=3
这样得到的平摊代价也为3

不关注实时性能只关注聚集性能

14.竞争性分析,自组织表
15.动态规划,最长公共子序列
16.贪婪算法,最小生成树
17.最短路径算法:Dijkstra算法,广度优先搜索
18.最短路径算法:Bellman和差分约束系统
19.最短路径算法:点的最短路径
20.高级课题 并行算法(一)
21.高级课题 并行算法(二)
22.高级课题 缓存参数无关算法


下载地址:

游客,如果您要查看本帖隐藏内容请回复

输入你的邮箱订阅论坛最新动态,还有机会免费获得VIP会员的机会哦~

回复

使用道具 举报

13

主题

0

好友

601

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
601
发表于 2018-8-17 08:08:31 | 显示全部楼层

第i个操作的平摊代价Ai=Ci+Di-Di-1=  i+2i-2^ceil(lgi)-(2i-2-2^ceil(lgi-1))(刚好i是2的幂)
  1+2i-2^ceil(lgi)-(2i-2-2^ceil(
回复 支持 反对

使用道具 举报

5

主题

3

好友

190

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
190
发表于 2018-8-17 08:09:14 | 显示全部楼层
楼主发贴辛苦了,谢谢楼主分享!我觉得龙天论坛是注册对了!
回复 支持 反对

使用道具 举报

5

主题

0

好友

680

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
680
发表于 2018-8-17 08:12:56 | 显示全部楼层
非常感谢楼主提供资源
非常感谢楼主提供资源
非常感谢楼主提供资源
非常感谢楼主提供资源
非常感谢楼主提供资源
回复 支持 反对

使用道具 举报

8

主题

0

好友

176

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
176
发表于 2018-8-17 08:25:27 | 显示全部楼层
4.竞争性分析,自组织表
15.动态规划,最长公共子序列
16.贪婪算法,最小生成树
17.最短路径算法:Dijkstra算法,广度优先搜索
18.最短路径算法:Bellman和差分约束系统
19.最短路径算法:点的最短路径
20.高级课题 并行算法(一)
21.高级课题 并行算法(二)
22.高级课题
回复 支持 反对

使用道具 举报

4

主题

4

好友

450

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
450
发表于 2018-8-17 08:27:58 | 显示全部楼层
       
电梯直达
跳转到指定楼层 1#
发表于 27 分钟前 | 只看该作者 回帖奖励
教程目录:
1.课程简介及算法分析
2.渐近符号、递归及解法
3.分治法(1)
4.快排及随机化算法
5.线性时间排序
6.顺序统计、中值
7.哈希表
8.全域哈希和完全哈希
9.二叉搜索树
10.平衡搜索树
树的结构,如果不能保持平衡,那么其搜索性能会大大打折扣,而本节课介绍了几种经典的平衡树,如AVL,2-3-4tree,红黑树等等,然后着重讲了红黑树,接下来就红黑树的基本性质,作一些简短的总结。

首先,红黑树除了具有BST的基本性质外,还额外拥有以下的五大基本性质:

1)每个结点有一个色域,一个结点要么为黑结点,要么为红结点

2)根节点为黑结点

3)每个叶子结点都为黑结点(无键值)

4)每个红结点的父亲都为黑结点,即不可能出现两个红色结点相连的情况

5)从根节点到任意叶节点的路径中的黑色结点数目相等,这个数目也称为黑高度

由以上5点性质,可以保证红黑树的高度为O(lgn),证明如下:

将红黑树的所有红结点,都与其父节点(由性质四得其父节点必定为黑)合并,可以得到一颗2-3-4 tree(即每个结点的子节点数目为2~4个),由数据结构知识可得,原红黑树的叶子结点个数为带键值结点个数n+1,假设整棵树高度为h,那么叶子结点数应为h^2~h^4,因此有h^2<=n+1<=h^4,即此时树高度最高也只有log n+1,即树的黑高度为log n+1,根据性质3,树最高情况也不过是红黑相间的时候,因此其高度最高只有2log n+1 ,即树的高度为O(lgn)。

红黑树的查询操作和普通BST一样,而删除和插入操作则相对复杂,因为我们要保证红黑树的5大性质,为什么需要保证这五大性质呢?因为这五大性质是红黑树为平衡树的保证,能够保证红黑树的高度为Olgn,这样红黑树的基本操作(删,插,查)都可以保证在Olgn的时间复杂度内完成。

接下来简单介绍一下插入操作是如何完成的,删除操作思路类似:

插入操作的原理就是插入一个红结点,然后通过向上重染色和旋转的方式维持红黑树的性质

这里有三种情况

case1  直线型 且祖父结点为黑,父节点和父亲兄弟结点为红 将祖父结点的黑传递到两个红子节点   每次向上传      递2个结点,树高度2lgn 所以操作为O(lgn)
case2  zigzag Z型 父亲兄弟结点为黑 旋转为case3   O(1)的旋转
case3  zigzig直线型 旋转

由以上三种情况可得,插入的时间复杂度为重染色的Olgn+不超过3次的O(1)的旋转操作

这里值得一提的是,在实际的运用中,虽然向上重染色理论上花费的时间多于旋转,但是当多个用户并发查询访问红黑树的时候,重染色并不会影响查询,因为用户并不关心每个结点的颜色,但是旋转需要锁定该子树及其结点,可能会影响并发查询的操作。

最后,就AVL和红黑树做一下比较,就平衡程度而言,AVL是追求的绝对平衡,任意叶子结点的深度不会多于其他叶子结点深度+1,而红黑树只要求局部平衡,其红黑性保证了其平衡性,因此在维护平衡方面,红黑树只需要不超过3次旋转即可,这一点是AVL树所做不到的,但查询方面,由于AVL是绝对平衡,因此效率会略高于红黑树,实际应用中这一点并不明显,就统计性能而言,红黑树会优于AVL,而C++ STL中的set、multiset、map、multimap等,都是红黑树的一种变体。

值得一提的是,平衡树都是动态的数据结构,其优势在于动态操作下,也能保持优越的查询效率,如果是静态数据,那么使用hash表效率会更高一些。

11.扩充的数据结构、动态有序统计和区间树
本节课主要讲了如何构造自己想要的数据结构,或者扩充已有数据结构的功能,以实现想要的特定功能

比如设计一个动态结构,满足功能寻找第k大的数

其做法是维护每个结点的子结点个数来推导其秩,而不维护其秩,因为动态操作会使得其难以维护
红黑树的插入操作 1.树插入 2.rebalance

构造自己需要的扩充数据结构的基本流程

1.选择一个基本的数据结构 例如红黑树
2.决定要添加到结点的基本信息  例如实现查询第k大数功能,应添加的基本信息为所有子树结点之和,而非直接保存该结点键值的秩
3 维持 插入+旋转/删除+旋转
4 封装为函数,实现其功能

12.跳跃表
跳跃表是一种简单又有趣的动态搜索数据结构,其主要优点在于其易于实现,而且很好的保证了其具有高效的性能,即2*O(lgn)的搜索性能

在此之前我想首先谈谈链表,链表的优点在于其插入和删除只需要常数项的时间(加上查找该元素需要额外的O(n)时间),但是其查找效率只有O(n),这里顺带补充一下链表类的问题,以下先给出两个BAT公司面试时热衷于考的两个链表经典问题:

1.如何快速查找单向链表倒数第m个元素

2.如何快速判断一个单向链表是否存在环

对于链表类问题,其核心思想不外乎两点,1是开双指针(甚至多指针),2是开双链表(甚至多链表),其实以上两个问题开双指针便能巧妙地解决,第一个问题,先开一个指针走m步,然后再开一个指针同步走,当前一个指针走到链表末端时,后一个指针就正好指向倒数第m个元素了,第二个问题,开一个快指针和一个慢指针,快指针每次移动两步,慢指针每次移动一步,如果存在环,那么快指针一定会追到慢指针,可以想象两个人在操场赛跑,快的人跑了很久之后会超慢的人一圈。

接下来我们继续谈跳跃表,其实跳跃表用到的就是第二个思路,开双链表甚至多个链表

首先考虑建立两个链表L1和L2,L1为快表,即只保存部分元素,L2为慢表保存全部元素,注意,以下提到的链表均为排好序的链表

当我们要搜索某一元素时,我们先走快表,因为快表只保留了部分元素,所以是跳跃前进的,直到快表走过该元素,我们再退回快表前一个结点换到慢表继续走,这样效率显然比在慢表上进行线性查找要好一些,这里的快慢表就像美国地铁的快慢线地铁一样,快线的地铁只在几个站停顿,而慢线会在所有站停顿,乘客可以先乘快线到一个最接近目的地的前一个站,再转乘慢线到达该地

那么问题来了?
如何建表L1和 L2呢?L2无疑是一条包含所有结点的单向链表,那么L1应该设置多少个结点最为合理呢,直观上感受L1应该是均匀分布最好,那么是以怎样的密度分布最合适呢?

我们不难得出查找时间上界为|L1|+|L2|/|L1|+换乘的常数,这里|L1|表示L1的长度(最坏情况就是L1走到末端后,走回一个节点然后进入L2,因为L2可以看做被L1分成了L1个段,所以每段长度为|L2|/|L1|,所以为|L1|+|L2|/|L1|+换乘的常数),因为L2长度为n(包括整个链表),换乘即链表L1向下走到L2的时间,为常数,所以我们的目标是要使得|L1|+n/|L1|最小,即|L1|为sqrt(n)时最优(可以求导得出或者通过其他数学方法,证明略),此时时间消耗为2*sqrt(n),即每隔sqrt(n)设立一个快表的结点,共sqrt(n)个快表结点

什么?sqrt(n)还不过瘾?

那么我们还能做怎样的优化呢?答案是加更多的链表,我们看看三条链表应是多少,直觉告诉我们是3*n的1/3次方
其实,可以证明k条链表的时候为k*n的1/k次方

因为n是常数,那么k多大比较合适呢?lgn! 让我们看看k取lgn的时候为多少,即lgn*n^(1/lgn)为多少,即求lgn*n^logn(2),还记得我们计算递归时间复杂度时的换底公式吗?这里n^logn(2)即2^logn(n)即2^1,即2,所以整个时间复杂度为2*lgn,这是一个非常好的性能。

这种情况下的跳跃表称为理想跳跃表,每一层数量减少一半,总共lgn层链表,从最上级链表开始搜,搜不到就向下,最多下logn层,每层最多搜2个元素,所以搜索复杂度为O(2lgn)

那么问题又来了,如何动态维护这样一个跳跃表呢?
先看删除功能,删除功能只要从上级链表搜到之后,就可以直接删除,并向下将所有链表的该结点都删除,这个比较简单,那么插入呢?

插入(x) 先search(x)在底表的位置然后插入该元素,是否结束了呢?不,因为在某一段连续插入若干个结点后,这一段会变得非常长,整个跳跃表的平衡结构无疑会被打破,那么如何维护理想线段表的结构呢?
1.保持每段之间的理想距离,如果距离过大,就从中间分割,然后将中点上升一层结点

这个方法从直观上看非常巧妙,但是实行起来却有一定难度,因为你必须实时记录每一段的长度

2.采用我们最喜欢的随机化算法,抛硬币 如果正面,就把这个结点提升一个level(即把该结点也加入上一级的链表中),再抛硬币(看是否持续提升level),因为两个相邻链表的长度之比为1:2,而硬币出正面的概率也是50%,事实证明这样做是可行的,这里值得一提的是,老师在这节课发了两个硬币给同学,一个利用抛硬币产生随机数,一个利用抛硬币决定当前插入结点是否需要提升level,在课堂上直接做起了实验,整个课程氛围也很好,也让同学们都对该算法有了直观的理解,这一种教学方式很值得借鉴

注意,这里需要考虑一个特殊情况,就是当我们插入的元素为最小的元素时,如果它没有提升一个level,那么上级链表的开头就不是第一个元素,这样也会打乱整个跳跃表的理想结构,因此我们需要打个补丁:即把一个负无穷值插到所有链表头,这样就算插入了一个最小的元素也能保证每个表是以负无穷开始,即每个链表都可以从最左边开始。

在课堂上,通过实验表明算法2似乎在平均情况下可以得到一个很好的跳跃表,其实不仅仅是平均情况可以得到一个好的跳跃表,在绝大多数情况都可以得到一个好的跳跃表.

可以证明,得到一个好的跳跃表的概率P>=1-O(1/n^a)  这里a是一个介于0到1的参数,与n有关,在课堂的最后,老师花了尽20分钟的时间来证明,具体证明方式我们这里略过(其实是我根本没看懂其证明过程 逃~~)

13.平摊分析,表的扩增,势能方法
先通过表的扩增这一例子来引入今天的主题——平摊分析和势能分析

一个哈希表的大小应该为多少比较合适?

theta(n)比较合适
可是万一我们不知道n是多大呢
使用动态表解决  溢出就建立一个大小翻倍的空间,然后复制过去
这样做插入的最坏时间复杂度为n

让我们看看平均的时间复杂度,每次基本插入操作为1,空间溢出时需要开一个更大一倍的空间,并复制当前的元素过去,所以空间溢出时所需要的时间为2的i次方(i为第几次溢出)

所以其真实的时间消耗为n+sigma(2^i)   0<=i<=lg(n+1)  即3n
因此其实插入的时间复杂度为O(1)

尽管有时会有巨大开销,但是会被平均的开销平摊掉,这就是平摊分析

平摊分析:平均操作复杂度不高,尽管有些操作会有较高的复杂度

三种类型的平摊方法:
1.聚集分析
2.记账方法(accounting)
3.势能分析
2.3它们为每一个操作分配了特点的平摊代价

记账方法:
想象自己担任了一个会记
对第i个操作收费为ci
收益个虚构的平摊代价
每一步运算需要花费1$
未用到的余款就被存到银行,用于偿付以后的操作

如每次插入收费为3,插入消耗1,剩下的2存入银行为表翻倍时做准备,要始终保证银行的金额为正

即提前平摊,总能支付扩充表的费用,这样某一个高开销的操作会被平摊掉

势能方法:
算法分析里最漂亮的产物之一
刚开始数据结构状态为D0
操作i的代价为ci
操作i可以看作把数据结构由Di-1转化为Di

定义势能函数
将数据结构的集合定位实数值
D0 = 0 初始的势为0
所有Di >=0,我们不能让势低于0
定义平摊代价为Ai,对势能Di有Ai=Ci+Di-Di-1
Di-Di-1 部分是势能的改变量,如果其>=0 那么Ai>ci 我收取的费用超过了实际的花费,即操作i储存了后面数据结构所需的功
如果势能的改变量<0,即我们用存储的势能转化为能量来帮助完成操作i

记账方法考虑的是平摊代价
而势能分析考虑的是银行存款(存储势能)

有sigmaAi=sigma(ci+Di-Di-1)=sigma(ci+Dn-D0)
D0为0,Dn大于等于0,所以左边大于右边,是实际代价的一个上界

我们再次以表的扩增为例感受一下势能分析
我们的势能函数为2i-2^ceil(lgi)  
如何推导出这样的势能函数的?
定义势能函数难度低于定义平摊代价
Di>=0
第i个操作的平摊代价Ai=Ci+Di-Di-1=  i+2i-2^ceil(lgi)-(2i-2-2^ceil(lgi-1))(刚好i是2的幂)
  1+2i-2^ceil(lgi)-(2i-2-2^ceil(lgi-1))

case1 i-1是2的幂,那么Ai=i+2-2(i-1)+(i-1)=3
case2 i-1不是2的幂 那么Ai=1+2i-2^ceil(lgi)-(2i-2-2^ceil(lgi-1))=3
这样得到的平摊代价也为3

不关注实时性能只关注聚集性能

14.竞争性分析,自组织表
15.动态规划,最长公共子序列
16.贪婪算法,最小生成树
17.最短路径算法:Dijkstra算法,广度优先搜索
18.最短路径算法:Bellman和差分约束系统
19.最短路径算法:点的最短路径
20.高级课题 并行算法(一)
21.高级课题 并行算法(二)
22.高级课题 缓存参数无关算法
回复 支持 反对

使用道具 举报

15

主题

0

好友

208

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
208
发表于 2018-8-17 08:31:28 | 显示全部楼层
楼主发贴辛苦了,谢谢楼主分享!我觉得龙天论坛是注册对了!
回复 支持 反对

使用道具 举报

1

主题

0

好友

32

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
32
发表于 2018-8-17 08:38:27 | 显示全部楼层

楼主发贴辛苦了,谢谢楼主分享!我觉得龙天论坛是注册对了!
回复 支持 反对

使用道具 举报

9

主题

2

好友

479

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
479
发表于 2018-8-17 08:57:13 | 显示全部楼层
算法导论视频教程 [修改]
高级模式
BColorImageLinkQuoteCodeSmilies
回复 支持 反对

使用道具 举报

10

主题

0

好友

517

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
517
发表于 2018-8-17 09:08:16 | 显示全部楼层
楼主发贴辛苦了,谢谢楼主分享!我觉得龙天论坛是注册对了!
回复 支持 反对

使用道具 举报

3

主题

0

好友

383

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
383
发表于 2018-8-17 09:10:33 | 显示全部楼层
这个帖子不回对不起自己!我想我是一天也不能离开龙天论坛
回复 支持 反对

使用道具 举报

6

主题

0

好友

262

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
262
发表于 2018-8-17 09:14:55 | 显示全部楼层
既然你诚信诚意的推荐了,那我就勉为其难的看看吧!龙天论坛不走平凡路。
回复 支持 反对

使用道具 举报

6

主题

0

好友

276

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
276
发表于 2018-8-17 09:16:28 | 显示全部楼层
case2 i-1不是2的幂 那么Ai=1+2i-2^ceil(lgi)-(2i-2-2^ceil(lgi-1))=3
这样得到的平摊代价也为3

不关注实时性能只关注聚集性能

14.竞争性分析,自组织表
15.动态规划,最长公共子序列
16.贪婪算法,最小生成树
17.最短路径算法:Dijkstra算法,广度优先搜索
18.最短路径算法:Bellman和差分约束系统
19.最短路径算法:点的最短路径
20.高级课题 并行算法(一)
21.高级课题 并行算法(二)
22.高级课题 缓存参数无关算法
回复 支持 反对

使用道具 举报

12

主题

0

好友

1231

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
1231
发表于 2018-8-17 09:18:39 | 显示全部楼层
这个帖子不回对不起自己!我想我是一天也不能离开龙天论坛
回复 支持 反对

使用道具 举报

7

主题

1

好友

291

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
291
发表于 2018-8-17 09:41:32 | 显示全部楼层
论视频论视频论视频
回复 支持 反对

使用道具 举报

4

主题

0

好友

273

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
273
发表于 2018-8-17 09:47:44 | 显示全部楼层
既然你诚信诚意的推荐了,那我就勉为其难的看看吧!龙天论坛不走平凡路。
回复 支持 反对

使用道具 举报

1

主题

0

好友

149

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
149
发表于 2018-8-17 09:48:15 | 显示全部楼层
算法导论视频教程算法导论视频教程
回复 支持 反对

使用道具 举报

4

主题

4

好友

212

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
212
发表于 2018-8-17 10:08:43 | 显示全部楼层
RE: 算法导论视频教程 [修改]
RE: 算法导论视频教程 [修改]
RE: 算法导论视频教程 [修改]
RE: 算法导论视频教程 [修改]
RE: 算法导论视频教程 [修改]
RE: 算法导论视频教程 [修改]
RE: 算法导论视频教程 [修改]
回复 支持 反对

使用道具 举报

8

主题

2

好友

1081

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
1081
发表于 2018-8-17 10:15:32 | 显示全部楼层
谢谢分享,好好学习
回复 支持 反对

使用道具 举报

5

主题

3

好友

277

积分

赞助会员

Rank: 14Rank: 14Rank: 14Rank: 14

积分
277
发表于 2018-8-17 10:17:54 | 显示全部楼层
楼主发贴辛苦了,谢谢楼主分享!我觉得龙天论坛是注册对了!
回复 支持 反对

使用道具 举报

 懒得打字嘛,点击右侧快捷回复【左侧自定义内容】 
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表