当前位置:首页 >> 数学 >>

算法分析(3)-2016


算法分析(3)

重要的数据结构

二分查找(Binary Search)

1. 判定树
?判定树适合于描述具有层次结构的数据

树的定义
?

?

?

?

树(tree) t 是一个非空

的有限元素的集合.其 中一个元素为根(root),余下的元素(如果有的 话)组成t 的子树(subtree). 层数(Level):指定树根的层数为1,其子节点 (如果有)的层数为2,子节点的子节点的层数 为3,等等。 节点的度(degree of an element)是指其孩子 的个数。 树的度(degree of a tree)是其元素度的最大 值。

二叉树
?

?

?

二叉树(binary tree)t 是有限个元素的集合(可 以为空).当二叉树非空时,其中有一个称为根 的元素.余下的元素(如果有的话)被组成2个 二叉树,分别称为t的左子树和右子树. 二叉树的高度(height)或深度(depth)是指该 二叉树的层数. 从根节点到每个节点有唯一一条路径,路径上 的边数称为该路径的长度.

二叉树的数学性质
?

?

?

性质1 :包含n (n>0)个元素的树的边数为n-1. 性质2 :若二叉树的高度为h,h≥0,则该二叉树 最少有h个元素,最多有2h-1个元素. 性质3 :包含n个元素的二叉树的高度最大为n, 最小为「log2(n+ 1)?: n≤ 2h-1=>2h≥n+1 所以,h≥log2 (n+1),即: h≥「log2(n+ 1)?


?

扩充的二叉树:补齐外节点的二叉树.设n为其内节点 数,则外节点数为n+1;

?

?

有n个节点的扩充二叉树,当外节点分布在相邻两层 时其深度,外路和内路长度达到最小(平衡原理). 设扩充前深度为k,则有: 2k-1≤n<2k=>k= ?log n? +1


?

?

?

设E为根节点到外节点的路径长度之和; I为 根节点到内节点的路径长度之和. 对有n个内节点的扩充二叉树,用归纳法可证 明: E=I+2n (练习) 假定扩充二叉树的外节点分布在相邻两层 则:E=m(k-1)+(n+1-m)k,其中m为第k层上的 外节点数.又因外节点数n+1=m+2(2k-1-m), 所以:m=2k-(n+1), E=(k+1)(n+1)-2k

二分查找的平均复杂度
?

设I为内路长度,E为外路长度,则: 平均失败查找次数U(n)=E/(n+1); 平均成功查找次数S(n)=(I+n)/n 平均失败查找次数U(n)=E/(n+1)=Θ(logn) 平均成功查找次数S(n)=(I+n)/n= Θ(logn)

? ?

二分查找判定树
?

?

二分查找过程可用二叉树来描述:把当前查 找区间的中间位置上的结点作为根,左子表 和右子表中的结点分别作为根的左子树和右 子树。由此得到的二叉树,称为描述二分查 找的判定树(Decision Tree)或比较树 (Comparison Tree)。 注意: 判定树的形态只与结点个数n相关,而 与输入实例中R[1..n]关键字的取值无关。

? 具有11个结点的有序表可用下图所示的判定树来表示

?

二分查找判定树的组成 ①圆结点即树中的内部结点。树中圆结点内的数字表示该结 点在有序表中的位置。

②外部结点:圆结点中的所有空指针均用一个虚拟的方形结 点来取代,即外部结点。
③树中某结点i与其左(右)孩子连接的左(右)分支上的标记 "<"、"("、">"、")"表示:当待查关键字 K<R[i].key(K>R[i].key)时,应走左(右)分支到达i的左(右)孩 子,将该孩子的关键字进一步和K比较。若相等,则查找过 程结束返回,否则继续将K与树中更下一层的结点比较。


?

二分查找算法的判定树为有n个内节点的扩充二叉 树而且叶节点分布在相邻两层:二分查找算法最坏 和平均情形的时间复杂度为 ?(logn)

?

基于关键字比较的有序表查找算法至少要做?(logn) 次比较

2. 等价类问题
?

假定有一个具有n 个元素的集合U= { 1,2,. . .,n}, 另有一个具有r 个关系的集合R= { (i1, j1) ,(i2 , j2 ), ..., (ir , jr ) }。关系R是一个等价关系(equivalence relation),当且仅当如下条件为真时成立: ? 对于所有的a,有(a, a) ∈R 时(即关系是反身的) ? 当且仅当(b, a) ∈ R时(a, b) ∈ R(即关系是对称的) ? 若(a, b) ∈R且(b, c) ∈R,则有(a, c) ∈R(即关系是 传递的)

?

在给出等价关系R时,我们通常会忽略其中的 某些关系,这些关系可以利用等价关系的反 身、对称和传递属性来获得
例3-3 假定n= 1 4,R= { ( 1 , 11 ),( 7 , 11 ),( 2 , 1 2 ),( 1 2 , 8 ),( 11 , 1 2 ),( 3 , 1 3 ),( 4 , 1 3 ),( 1 3 , 1 4 ),( 1 4 , 9 ), ( 5 , 1 4 ),( 6 , 1 0 ) }。 我们忽略了所有形如( a , a )的关系,因为按照反身属性,这 些关系是隐含的。同样也忽略了所有的对称关系。 比如( 1 , 11) ∈R,按对称属性应有( 11,1) ∈ R。其他被忽略 的关系是由传递属性可以得到的属性。例如根据( 7 , 11) 和 ( 11 , 1 2 ),应有(7,12) ∈R。

?

?

?

?

?

?

等价类(equivalence class)是指相互等价 的元素的最大集合。 “最大”意味着不存在类以外的元素,与类内 部的元素等价。 考察例3-3中的等价关系。
?

?

由于元素1与11,11与1 2是等价的,因此,元素1 , 11 , 1 2是等价的,它们应属于同一个等价类。不过,这三个元素 还不能构成一个等价类,因为还有其他的元素与它们等价 (如7)。所以{ 1 , 11 , 1 2 }不是等价元素的最大集合。 集合{ 1 , 2 , 7 , 8 , 11 , 1 2 }才是一个等价类。 关系R还定义了另外两个等价类:{ 3 , 4 , 5 , 9 , 1 3 , 1 4 } 和{ 6 , 1 0 }。

?

?

离线等价类(offline equivalence class):已知n 和R, 确定所有的等价类。 在线等价类(online equivalence class):初始时有n 个元素,每个元素都属于一个独立的等价类。需要执 行以下的操作
? ?

Combine(a, b) 把包含a 和b 的等价类合并成一个等价类。 Find(e) 确定哪个类包含元素e,搜索的目的是为了确定给 定的两个元素是否在同一个类之中

?

?

可以利用两个F i n d操作和一个U n i o n操作产生一 个组合操作,该操作能把两个不同的类合并成一个类。 C o m b i n e ( a , b )等价于:i = Find(a); j = Find(b); if(i! = j) Union(i, j);

在线等价类
?

?

在线等价类问题也称作离散集合合并/搜索问 题(disjoint set union-find problem) Union-Find数据结构
? ?

? ? ?

设U={1,2,…,n},Ai是U的某些不交子集; union(Ai,Aj)指对这些子集中的Ai和Aj做并操作 Ai∪Aj; find(x),x∈U,指找x所在的子集Ai, 即,x∈Ai; 假定初始有n个单元素的子集Ai={i},1≤i≤n; 试图找一种表示集合的数据结构和算法,使得在线 (online)地执行任何n-1个union和m≥n个find操作的 混合序列的累积时间接近线性的.

第一种解决方案
? ? ?

? ?

在线等价类问题的一种简单解决办法是使用一个数 组E,并令E(e) 为代表包含元素e 的等价类。 完成初始化、合并及搜索操作的函数如程序3-46所 示。 N 是元素的数目,n 和E 均被定义为全局变量。为 了合并两个不同的类,可从类中任取一个元素,然 后把该类中所有元素的E 值修改成另一个类中元素 的E 值。 I n i t i a l i z e和U n i o n函数的复杂性均为Θ (n),F i n d的复杂性为Θ ( 1 )。 在应用这些函数时,通常执行一次初始化,u 次合 并和f 次搜索,故所需要的总时间为Θ ( n +u* n +f ) = Θ (u* n +f )。

第二种解决方案
?

针对每个等价类设立一个相应的链表,可以降低合并操作的 时间复杂性,可以沿着类j的链表找到所有E[k]=j 的元素, 而不必去检查所有的E值
?

?

?

在使用链表时,初始化和搜索操作的复杂性仍分别保持为Θ( n )和 Θ( 1 ) 。 每次合并操作的开销为(较小类的大小)。令i 表示合并操作中的较小 类。在合并期间, i 中的每个元素从类i 移向类j,因此u次合并的复 杂性由移动元素的总次数确定。移动类i 之后,新类的大小至少是类 i 的两倍(因为在移动前有s i z e [ i ]≤s i z e [ j ],而移动之后新类的 大小为s i z e [ i ] + s i z e [ j ])。因此,由于在操作结束时没有哪个 类的元素数会超过u+ 1,所以在u 次合并期间,没有哪个元素的移 动次数超过l o g2 (u+ 1 )。在u次合并过程中,最多可以移动2u 个元 素,所以,元素移动的总次数不会超过2u l o g2 (u+ 1 )。至此可以知 道执行u 次合并操作所需要的时间为O (ul o gu) 1次初始化、u次合并操作和f 次搜索的复杂性为O (n+u l o gu+f)

在线等价类的第三种解决方案
?

?
? ?

把每个集合(类)描述为一棵树 而树中每个非根节点都指向其父节点 用根元素作为集合标识符 如图8.15

Union-Find算法

集合的树表示

Union-Find算法

Program 8.15 Simple tree solution to union-find problem

算法复杂性
?

?

?

假设要执行u 次合并和f 次查找。因为每次合 并前都必须执行两次查找,因此可假设f>u。 每次合并所需时间为Θ ( 1 )。而每次查找所 需时间由树的高度决定。在最坏情况下,有 m个元素的树的高度为m。 若使用重量规则(高度规则),合并和查找序 列的代价(不包括初始化时间)为 O (u+f l o gu)

图8.17 Union

图8.18 Two sample trees

算法改进
?

?

?

使用加权规则 定义[重量规则] 若树i 节点数少于树j 节点数, 则将j 作为i 的父节点。否则,将i 作为j 的父 节点。 定义[高度规则] 若树i 的高度小于树j 的高度, 则将j 作为i 的父节点,否则将i 作为j 的父节 点。

加权规则(Weight rule)



Program 8.16 Unioning with the weight rule

Weight rule lemma
Lemma8.1 假定从单元素集开始执行加权并. 设t是上述过程产生的有p个节点的一棵树,则t的深 度不超过 ?log p? ? 1 ? 证明:设t1,t2为产生t的Union序列中最后一次合并前 的树. 设t1、t2的节点数为p1和p2,(均小于p),又设 p1≤p2 ,对p1和p2用归纳假设: d1 ? ?log p1 ? ? 1 d 2 ? ?log p2 ? ? 1 ? t的深度d=d2 或d1+1,无论何种情形都有 d≤ ?log p? ? 1 (1+logp1=log2p1≤log(p1+p2)=logp)
?

优先队列问题
?

优先队列中元素出队列的顺序由元素的优先级决定。 例:假设我们对机器服务进行收费。每个用户每次使用机 器所付费用都是相同的,但每个用户所需要服务时间都不 同。为获得最大利润,假设只要有用户机器就不会空闲, 我们可以把等待使用该机器的用户组织成一个最小优先队 列,优先权即为用户所需服务时间。当一个新的用户需要 使用机器时,将他/她的请求加入优先队列。一旦机器可用, 则为需要最少服务时间(即具有最高优先权)的用户提供 服务。 如果每个用户所需时间相同,但用户愿意支付的费用不同, 则可以用支付费用作为优先权,一旦机器可用,所交费用 最多的用户可最先得到服务,这时就要选择最大优先队列。

?

?

第一种方案
?

1)采用无序线性表描述最大优先队列
?

假设有一个具有n 个元素的优先队列,插入操作可以十分 容易地在表的右端末尾执行,插入所需时间为Θ( 1 )。删 除操作时必须查找优先权最大的元素,即在未排序的n 个 元素中查找具有最大优先权的元素,所以删除操作所需 时间为Θ(n)
删除时间均为Θ( 1 ),插入操作所需时间为Θ(n)

?

2)采用有序线性表
?

第二种方案
?

?

?

?

可以利用堆数据结构来高效地实现优先队列 定义[最大树(最小树)] 每个节点的值都大 于(小于)或等于其子节点(如果有的话) 值的树。 最大树不必是二叉树,最大树或最小树节点 的子节点个数可以大于2。 定义[最大堆(最小堆)] 最大(最小)的完 全二叉树。

Heaps

图9.3 Insertion into a max heap

图9.4 Deletion from a max heap

图9.5 Initializing a max heap

图9.5 Initializing a max heap(续)

堆排序分析
?

? ? ?

n个节点的完全二叉树的深度为 ?log(n ? 1)? k ? ?log n? ? 1 堆插入和删除需 ?(logn)即 堆排序时间为O(nlogn) 初始化:O(nlogn)


相关文章:
《算法分析》实验指导书(1)2015-2016
算法分析》实验指导书(1)2015-2016_数学_自然科学_专业资料。《算法分析》...三、实验提示 void chessBoard(int tr, int tc, int dr, int dc, int ...
2016年算法分析与设计练习题
2016算法分析与设计练习题一、 算法时间复杂度分析 1、渐进符号 几个常见的...而增长率大的算法 3、非递归算法的数学分析 决定用哪个(哪些)参数作为输入规模...
算法分析期末试题集2016年春
算法分析期末试题集2016年春_教育学_高等教育_教育专区。《算法分析与设计》期末...分析算法占用计算机资源的情况,对算法做出比较和评价,设计出额更好的算法。 3....
2016春《计算机算法设计与分析》实验作业
2016春《计算机算法设计与分析》实验作业_互联网_IT/计算机_专业资料。实验报告...三、实验内容 2.1 求最大最小元问题 2.2 归并排序 2.3 快速排序 2.4 ...
2015年算法分析与设计期末考试试卷A卷
西南交通大学 2015-2016 学年第(一)学期考试试卷课程代码 3244152 课程名称算法分析与设计考试时间 120 分钟题号 得分 阅卷教师签字: 一二三四五· 总成绩 一、...
程序设计算法题目说明-2016
程序设计算法题目说明-2016_计算机软件及应用_IT/计算机_专业资料。程序设计与...2016分析论证有效的审题... 暂无评价 3页 免费 2016年贵州省公务员考试... ...
2016.6《算法分析与设计实验》课程设计指导书
算法分析与设计实验》 课程设计指导书 2016 年 5 月 一.课程设计目的本课程...3 四.总体要求根据所给的实验指导书的要求,从中选择项目,应用所学的知识,完成...
c语言第三次实验报告2016
2016/4/13 成绩 李淮 专业班级 2015 级新能源 1 班学 批阅日期 指导教师 ...算法分析: 1、输入:通过键盘接收同学个数; 2、调用求平均分函数 3、输出平均...
2016淘师湾作业答案
2016淘师湾作业答案_其它课程_高中教育_教育专区。...“对比分析”中正数表示奥运成绩比 GDP 排名好,说明...(7-2)DABBB 算法与问题解决例举(7-3)BABDB ...
更多相关标签:
诛仙3职业分析2016 | 剑网3各职业分析2016 | 算法设计与分析基础 3 | 剑网3职业分析2016 | 2016年3季度财务分析 | 算法设计与分析第3版 | 百度算法调整2016 | 2016车损险算法 |