首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。 经分析发现该问题具有最优子结构,可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j],
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。 经分析发现该问题具有最优子结构,可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j],
admin
2018-11-21
79
问题
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。
经分析发现该问题具有最优子结构,可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j],如下式所示。
采用自底向上的方法实现该算法,则时间复杂度为_____________。
选项
A、O(n
2
)
B、O(n
2
lgn)
C、O(n
3
)
D、O(n2
n
)
答案
A
解析
本题考查算法设计与分析的基本知识。要求考生熟悉典型的算法设计技术及其典型的问题的求解。
应用蛮力法求解最长公共子序列时,其思路在题干已经给出。对X的每一个子序列,判断其是否也是Y的子序列,那么长度为n的序列X的子序列数是2
n
,而判断一个子序列是否也是Y的子序列的时间是n,因此时间复杂度为O(n2
n
)。
而采用动态规划自底向上的方法求解时,题干也给出了最优子结构和递归式的定义,因此很容易看出算法的时间复杂度实际上就是i和j的两重循环,时间复杂度为O(n
2
)。
转载请注明原文地址:https://kaotiyun.com/show/fRWZ777K
本试题收录于:
嵌入式系统设计师上午基础知识考试题库软考中级分类
0
嵌入式系统设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明,回答以下问题,将解答填入答题纸的对应栏内。【说明】某信息化工程项目,主要涉及机房工程、综合布线及应用软件系统开发。其中,应用软件系统开发项目的计划工期为40周,预算成本为500万元。建设单位通过公开招标选择了承建单位和监理单位。在项目建设
阅读下列说明,回答问题,将解答填入对应栏内。【说明】X大学准备建设一栋创新探索实验大楼,其中信息系统工程总投资额约2000万元,主要包括网络平台建设和机房建设。该项目涉及计算机设备、网络设备、通信设备的采购和集成。【事件1】建设单位拟通过公开招标方式
阅读下列说明,回答问题,将解答填入对应栏内。【说明】X省通信运营商拟开发运营支撑系统应用软件,管理企业的业务流程和基础资源。建设单位通过公开招标方式选择了监理单位,以便协助建设单位做好全过程的监理工作。该项目承建单位采用瀑布模型进行软件开发。在项目开发
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。[说明]某省政府根据整体战略规划部署,拟建设统一身份认证系统。该系统为用户提供注册、实名验证、身份鉴别等服务,实现可信注册、实名验证以及安全登录等功能,支撑政务服务的有序运行。完成开发任务后,项目进
TCP/IP协议分为四层,分别为应用层、传输层、网际层和网络接口层。不属于应用层协议的是(62),属于网际层协议的是(63)。
以下关于信息库(Repository)的叙述中,最恰当的是(18);(19)不是信息库所包含的内容。
在计算机中,最适合进行数字加减运算的数字编码是(1)。如果主存容量为16M字节,且按字节编址,表示该主存地址至少应需要(2)位。
在编制监理规划时,有关监理措施的内容应突出(58)。
存储技术是在服务器附属存储SAS和直接附属存储DAS基础上发展起来的,表现为两大技术SAN和NAS。下面对SAN和NAS描述不正确的是:_____________。
数据流程图(DFD)是一种能全面地描述信息系统逻辑模型的主要工具,在数据流程图中方框表示(28),(29)不属于数据流程图的基本成分。(29)
随机试题
钻孔时的背吃刀量,就是钻头的直径尺寸。()
阳湖派古文和常州词派的开创者是【】
一类高层建筑内走道吊顶应采用()。
溢油在海面上的变化是极其复杂的,溢油动力学过程一般划分为()。
根据动机所起作用的大小,我们可以把学习动机区分为()
大多数国家的高等学校可分为三个层次,分别是:__________、大学和专门学院、研究生院。
很早以前科学家就发现有些人对于某些药物的反应和其他病人不同。例如,某种麻醉用肌肉松弛剂会导致特定的人无法呼吸。后来,科学家发现产生这种现象的原因在于这类人拥有特定的基因。这也就带来了一个问题:研究人们之间的遗传差异是否可以促进医学发展出更高级的治疗手段,也
下列诗句的作者及时代,对应正确的一项是:①但使龙城飞将在,不教胡马度阴山②池塘生春草,园柳变鸣禽③王师北定中原日,家祭无忘告乃翁④天街小雨润如酥,草色遥看近却无⑤我自横刀向天笑,去留肝胆两昆仑
激进建构主义的原则是什么?
设循环队列的存储空间为Q(1:100),初始状态为空。现经过一系列正常操作后front=49,则循环队列中的元素个数为()
最新回复
(
0
)