首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(62)。经分析
求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(62)。经分析
admin
2019-07-12
33
问题
求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(62)。经分析发现该问题具有最优子序列,可以定义序列成都分别为i和j的两个序列X和Y的最长公共子序列的成都为C[i,j]如下式所示。该方法的时间复杂度为(63)。
(63)
选项
A、O(n
2
)
B、O(n
2
lgn)
C、O(n
3
)
D、O(n2
n
)
答案
A
解析
第62题一个给定的序列的子序列,就是将给定序列中零个或多个元素去掉之后得到的结果。序列ABCBDAB去掉划线的字符ABCBDAB得到的BCBA就是它的一个子序列。一个序列的子序列有2
n
个,将X、Y的所有子序列都检查过后即可求出X、Y的最长公共子序列。这种方式的时间复杂度为O(n2
n
)。
第63题引进一个二维数组c
[j]表示X的i位和Y的j位之前的最长公共子序列的长度,按照公式将数值填入下表。
此时,c
[j]中最大的数就是X和Y的最长公共子序列的长度,等于4。该算法的时间复杂度为O(n
2
)。
转载请注明原文地址:https://kaotiyun.com/show/zQCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明和图,回答问题1至问题3。【说明】某房屋租赁公司欲建立一个房屋租赁服务系统,统一管理房主和租赁者的信息,从而快速地提供租赁服务。该系统具有以下功能:1.登记房主信息。对于每名房主,系统需登记其姓名、住址和联系电话,并将这些信息
根据说明中的描述,使用表3-1给出的类的名称,给出图3-1中的A~F所对应的类。根据说明中的描述,给山图3-1中(1)~(6)处的多重度。
阅读下列说明,回答问题1至问题4,将解答填入对应栏内。【说明】某汽车维修站拟开发一套小型汽车维修管理系统,对车辆的维修情况进行管理。1.对于新客户及车辆,汽车维修管理系统首先登记客户信息,包括:客户编号、客户名称、客户性质(个人、单位)
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。A:待排序数组p,r:数组元素下标,从p到rq:划分的位置x:枢轴元素i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴
图(a)中只有一个外部实体E1。使用【说明】中的词语,给出E1的名称。使用【说明】中的词语,给出图(b)中的数据存储D1~D4的名称。
阅读下列程序说明,将应填入(n)处的字句写在答卷纸的对应栏内。【程序说明】对于一个公司的雇员来说,无非有3种:普通雇员、管理人员和主管。这些雇员有共同的数据:名字、每小时的工资,也有一些共同的操作:数据成员初始化、读雇员的数据成员及计算雇员
根据E-R图中给出的词汇,按照“有关模式名(属性1,属性2,…)”的格式,将此E-R图转换为关系模式,并指出每个关系模式中的主码和外码,其中模式名根据需要取实体名或联系名。要求其中的关系模式至少属于第三范式。假设这个银行有若干个节点,每个节点运行一个数
阅读以下说明,回答问题。【说明】某公司要开发一个销售管理系统,该系统的主要功能是:处理客户和销售员送来的订单;工厂是根据订货安排生产的,交出货物同时开出发票,收到客户付款后,根据发票存根进行应收款处理。每张订单由订单号,若干头信息和订单细节组
阅读以下说明和c++码,将应填入(n)处的字名写在对应栏内。[说明]从键盘输入一个字符ch,输出该字符在文本文件input.txt的每一行中出现的次数。(必须调用函数鳋统计ch的出现次数,函数ff(str,ch)的功能是统计并返回字符ch在字符串
企业信息整合、共享需要一个代表企业身份的信息,该信息应该具有唯一性和易管理性,上述表格中信息项(1)代表企业身份最合适。请将以下叙述中(2)~(5)空缺处的内容填写完整。随着WebService的成熟,现在的(2)(SOA)已经有所发
随机试题
采用下向焊焊接时,可由多个焊工组成连续操作的流水作业班组,它特别适用于球形储罐的焊接施工。
COPD
常见的成果激励主要包括两类:物质激励和_____。
阿托品中毒时,不出现
汗证肺卫不固证,治疗原则是
银柴胡牛膝
甲股份有限公司(以下简称“甲公司”)为增值税一般纳税人,适用的增值税税率为17%。2014年甲公司自行建造一条生产线,相关业务的资料如下:(1)1月10日,购进为生产线准备的一批物资,价款为140万元,增值税税额为23.8万元。该批物资已验收入库;款项以
一个优秀项目团队的形成,一般需要经历5个阶段,按次序分别是(49)。
_____________方法是一种仅有方法头、没有具体方法体和操作实现的方法,该方法必须在抽象类之中定义。
Theprofessorrequeststhatwe______thetermpapersbytheendofthismonth.
最新回复
(
0
)