东南大学算法设计与分析复习题 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,
东南大学算法设计与分析复习题_理学_高等教育_教育专区。算法设计与分析期末考试提纲的参考资料。什么是基本运算? 什么是基本运算? 答:基本运算是解决问题时占支配...
算法设计与分析复习题_IT/计算机_专业资料。算法设计与分析复习题算法设计与分析复习题 1、 一个算法应有哪些主要特征? 又穷性,确定性,可行性,0 个或多个输入...
算法设计与分析复习题_工学_高等教育_教育专区。算法设计与分析复习题 1 一个... 算法设计与分析期末试题... 3页 免费 东南大学算法设计与分析... 22页 ...
算法设计与分析复习题_计算机软件及应用_IT/计算机_专业资料。西南交大 算法 ... 东南大学算法设计与分析... 22页 免费 算法设计与分析期末试题... 3页 ...
算法设计与分析复习题 1、 一个算法应有哪些主要特征? 又穷性,确定性,可行性... 东南大学算法设计与分析... 22页 免费 算法设计与分析试题(A) 3页 免费 ...
算法设计与分析复习题目及答案(物联班)_IT认证_资格考试/认证_教育专区。一。选择题 1、二分搜索算法是利用( A、分治策略 B、动态规划法 )实现的算法。 C...
算法设计与分析复习题 1、分治法的基本思想:是将一个规模为 N 的问题分解为 K 个规模较小的子问题,这些子问题互相独立且与原问 、分治法的基本思想: 题相同...
算法设计与分析考试复习题_工学_高等教育_教育专区。该文档用于算法设计与分析考试的复习,文档中有选择填空和知识点总结,涵盖了大量的考点信息,适合大学本科生复习...
算法分析与设计—部分复习题答案_计算机软件及应用_IT/计算机_专业资料。西南交大 算法考试题目算法设计与分析复习题 1、 一个算法应有哪些主要特征? 有限性、确定...
计算机算法设计与分析复习题_工学_高等教育_教育专区。选填,简要介绍文档的主要内容,方便文档被更多人浏览和下载。《算法分析与设计》期末复习题一、 选择题 1....
热门文档