首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
求解两个长度为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
80
问题
求解两个长度为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
嵌入式系统设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明,回答问题。【说明】针对电子商务软件开发建设项目,建设单位甲与承建单位乙签订了项目实施合同,与监理单位丙签订了项目监理合同。在项目实施过程中发生了如下事件。【事件1】合同生效后,承建单位项目经理在短时间内即完成了项目计划的编制并提交监理
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某省政府根据整体战略规划部署,拟建设统一身份认证系统。该系统为用户提供注册、实名验证、身份鉴别等服务,实现可信注册、实名验证以及安全登录等功能,支撑政务服务的有序运行。完成开发任务后,项目进
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某省计划2020年初步建成信息共享的生态环境监测网络。通过招标,建设单位确认了A单位为承建单位,B单位为监理单位。随着项目建设任务的推进,B单位根据项目建设的总体进度计划,要求A单位在合同规定
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】为推进“互联网+政务服务”,某建设单位拟建设省级政务服务平台,使平台能够支撑一网通办、汇聚数据信息、实现交换共享、强化动态监管。通过公开招标确定了承建单位和监理单位。在准备验收时,承建单位完成
在某校园网工程项目监理过程中,监理方在工程设计阶段对网络设计方案进行评审,监理工作过程中不包括(47);在工程实施过程中,监理工程师收到承建单位的隐蔽工程检验申请后,首先对质量证明资料进行审查,并在规定的时间内到现场检查,此时(48)应随同一起到现场。
运行Web浏览器的计算机与网页所在的计算机要建立(33)连接,采用(34)协议传输网页文件。
在仲裁协议中,(31)是必须约定的内容。
计算机性能评测分为评估和测试两种方法,其中评估是基于一些原始数据进行推算。(42)用于评价同一厂商生产的同一计算机系统的定点运算速度比较正确;(43)可用于比较和评价在同一系统上求解同一问题的不同算法的性能;(44)是美国用来限制计算机出口的系统性能指标估
某公司使用包过滤防火墙控制进出公司局域网的数据,在不考虑使用代理服务器的情况下,下面描述错误的是“该防火墙能够(8)”。
在入侵检测技术中,______负责判断并产生警告信息。
随机试题
2006年3月20日,上海的甲公司与北京的乙公司签订了一份买卖合同,约定:甲公司向乙公司购买1000吨化工原料,总价款为200万元;乙公司在合同签订后1个月内交货,甲公司在验货后7日内付款。双方没有明确约定履行地点。合同签订后,甲公司以其办公用房作抵押向丙
在Windows7中,如果误删了重要文件则无法恢复,只能重做。()
不属于眼球内容物的结构是
脑内具有生命中枢之称的部位是
有关上颌牙列的纵胎曲线,说法正确的有
患者,男性,77岁。因脑出血入院,患者大小便失禁,需加铺橡胶单,其上端距床头约
依法定方式签发票据并将票据交付给收款人的人是()。
技能是一种活动方式,属于动作经验,与属于认知经验的知识是相同的。()
下列属于无效的民事行为的是()
Muchoftheworldshouldgoonadietin2014.Morethanathirdofadults【C1】______wereestimatedtobe【C2】______orobesein20
最新回复
(
0
)