文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 东南大学算法设计与分析复习题
侵权投诉

东南大学算法设计与分析复习题

东南大学算法设计与分析复习题 2012年

pointer→leftson←Buildtree(i,k-1,r,A); /*建立最优左子树Ti,k-1*/

pointer→rightson←Buildertree(k,j,r,A); /*建立最优右子树Tk,j*/

return pointer;

}

Francis Yao的办法为什么会把算法时间复杂度从O(n3)降到O(n2)?

答:Th: 如果最小耗费树Ti,j-1和Ti+1,j的根分别为ap和aq,则必有

⑴p q ⑵最小耗费树Tij的根ak满足p k q。 (证明略。)

有了上述定理,我们无需在ai+1~aj之间去一一尝试,使得找到的ak为根时,

{ci,k-1+ckj+wij}为最小,而只要从ap~aq之间去找一个根即可。

算法时间复杂度为Θ(n2)的证明:

首先注意Ti,j-1和Ti+1,j的规模恰好比Ti,j小1。由于算法是按树中结点的个数(即规模)从小到大计算的,故在计算rij时,ri,j-1(即定理中的p)和ri+1,j(即定理中的q)

都已经计算出来了。一般地,设含有k个连续结点的最优二分搜索子树的根

r0k,r1(k+1), ,r(n-k),n已经计算出来。由Th知, 含有k+1个连续结点的最优二分搜索子树Ti, i+k+1的根 必在ri,i+k与ri+1,i+k+1之间。

故r0,k+1在r0,k与r1,k+1之间, 求出r0,k+1的搜索区间长度为r1,k+1-r0,k; r1,k+2在r1,k+1与r2,k+2之间,求出r1,k+2的搜索区间长度r2,k+2 -r1,k+1; r2,k+3在r2,k+2与r3,k+3之间,求出r2,k+3的搜索区间长度r3,k+3 -r2,k+2; r(n-k-1),n在r(n-k-1),n-1与r(n-k),n之间,

求出r(n-k-1),n的搜索区间长度为r(n-k),n-r(n-k-1),n-1;

于是,求出所有规模为k+1的最优二分搜索子树的根

r0,k+1, r1,k+2, ,r(n-k-1),n的搜索长度的总和=

(rn-k,n-rn-k-1,n-1)+ +( r3,k+3

-r2,k+2)+(r2,k+2-r1,k+1)+(r1,k+1-r0,k)=r(n-k),n-r0,k

∵rn-k,n最多为n,r0,k最小为1,

上一页第5页

你可能喜欢

  • 程序设计基础复习题
  • 系统分析设计复习题
  • 平法复习题
  • 道路勘测设计复习题
  • 算法分析设计复习题
  • 算法设计分析复习题
  • 电路分析基础复习题

热门文档

相关文档

  • 东南大学算法设计与分析复习题

    东南大学算法设计与分析复习题_理学_高等教育_教育专区。算法设计与分析期末考试提纲的参考资料。什么是基本运算? 什么是基本运算? 答:基本运算是解决问题时占支配...

  • 算法设计与分析复习题

    算法设计与分析复习题_IT/计算机_专业资料。算法设计与分析复习题算法设计与分析复习题 1、 一个算法应有哪些主要特征? 又穷性,确定性,可行性,0 个或多个输入...

  • 算法设计与分析复习题

    算法设计与分析复习题_工学_高等教育_教育专区。算法设计与分析复习题 1 一个... 算法设计与分析期末试题... 3页 免费 东南大学算法设计与分析... 22页 ...

  • 算法设计与分析复习题

    算法设计与分析复习题_计算机软件及应用_IT/计算机_专业资料。西南交大 算法 ... 东南大学算法设计与分析... 22页 免费 算法设计与分析期末试题... 3页 ...

  • 算法设计与分析复习题

    算法设计与分析复习题 1、 一个算法应有哪些主要特征? 又穷性,确定性,可行性... 东南大学算法设计与分析... 22页 免费 算法设计与分析试题(A) 3页 免费 ...

  • 算法设计与分析复习题目及答案(物联班)

    算法设计与分析复习题目及答案(物联班)_IT认证_资格考试/认证_教育专区。一。选择题 1、二分搜索算法是利用( A、分治策略 B、动态规划法 )实现的算法。 C...

  • 算法设计与分析复习题

    算法设计与分析复习题 1、分治法的基本思想:是将一个规模为 N 的问题分解为 K 个规模较小的子问题,这些子问题互相独立且与原问 、分治法的基本思想: 题相同...

  • 算法设计与分析考试复习题

    算法设计与分析考试复习题_工学_高等教育_教育专区。该文档用于算法设计与分析考试的复习,文档中有选择填空和知识点总结,涵盖了大量的考点信息,适合大学本科生复习...

  • 算法分析与设计—部分复习题答案

    算法分析与设计—部分复习题答案_计算机软件及应用_IT/计算机_专业资料。西南交大 算法考试题目算法设计与分析复习题 1、 一个算法应有哪些主要特征? 有限性、确定...

  • 计算机算法设计与分析复习题

    计算机算法设计与分析复习题_工学_高等教育_教育专区。选填,简要介绍文档的主要内容,方便文档被更多人浏览和下载。《算法分析与设计》期末复习题一、 选择题 1....

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email