首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(62)。经分析
求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(62)。经分析
admin
2019-07-12
62
问题
求解两个长度为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),入住日期,退房日期,预付款额)请给出问题1中住宿关系的
阅读下列说明和Java代码,将应填入(n)处的字句写在对应栏内。【说明】已知某企业的采购审批是分级进行的,即根据采购金额的不同由不同层次的主管人员来审批,主任可以审批5万元以下(不包括5万元)的采购单,副董事长可以审批5万元至10万元(不包括
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。A:待排序数组p,r:数组元素下标,从p到rq:划分的位置x:枢轴元素i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴
阅读下列程序说明和C++代码,将应填入(n)处。【说明】“背包问题”的基本描述是:有一个背包,能盛放的物品总重量为S,设有N件物品,其重量分别为w1;w2,……,wn,希望从N件物品中选择若干件物品,所选物品的重量之和恰能放入该背包,即所选物品
根据E-R图中给出的词汇,按照“有关模式名(属性1,属性2,…)”的格式,将此E-R图转换为关系模式,并指出每个关系模式中的主码和外码,其中模式名根据需要取实体名或联系名。要求其中的关系模式至少属于第三范式。假设这个银行有若干个节点,每个节点运行一个数
阅读以下关于某订单管理系统的技术说明、部分UML类图及C++代码,将C++程序中(1)~(5)空缺处的语句填写完整。[说明]某订单管理系统的部分UML类图如图5-15所示。图5-15中,Product表示产品,Produc
运行Web浏览器的计算机与网页所在的计算机要建立(66)连接,采用(67)协议传输网页文件。
多媒体技术的关键在于解决动态图像和声音的存储与传输问题。若不经压缩,以 VGA640×480点阵存储一幅256色的彩色图像大约需(56)MB存储空间,以9600bit/s的速度传输这幅图像大约需(57)秒,按我国电视PAL标准每秒25幅,一张650MB的光
传统的数据库基本上是由(38)组成的。(39)在技术和理论上已经成熟,成为当前商用数据库的主流。(40)技术是20世纪80年代中期引入的。目前,多媒体数据库基本上靠与关系模式相结合的(41)来支持。但当数据量大,数据结构复杂时,靠(41)很难适应。当前,在
随机试题
下列药材产地加工时采用蒸、煮或烫方法处理的有
A.G蛋白耦联受体B.化学门控通道C.电压门控通道D.机械门控通道E.酪氨酸激酶受体神经轴突膜上与动作电位的产生直接有关的蛋白质属于
甲公司于2008年7月依法成立,现有数名推荐的董事人选,依照《公司法》规定,下列哪些人员不能担任公司董事?(2008年试卷三第76题)
1790年在英国发生了一起案件,一对夫妇准备离婚,在孩子的抚养权问题上产生分歧。依据英国原来确定的一个先例,当时的情况下孩子归父亲抚养,但依据衡平法院的审判实践,孩子应当归母亲抚养。关于此案的处理哪一项是正确的?
[2008年第82题]图6.4.5所示直径为20mm,长5m的管道自水池取水井并泄入大气中,出口比水池低2m,已知沿程水头损失系数λ=0.02,进水局部水头损失系数ζ=0.5,则泄流量Q为()L/s。
对列入城建档案管理机构接收范围的工程,工程竣工验收后最多()个月内,向当地城建档案管理机构移交一套符合规定的工程档案。
万达外资公司无进出口经营权,2004年5月从意大利进口一批玩具样品,在向海关申报时,其报关单“贸易方式”栏立填写()。
劳动争议调解委员会的组成不包括()
根据资料,回答下列问题。2015年1—3月,G市A区全区完成固定资产投资84.17亿元,同比增长6.1%,增速比去年同期回落4.3个百分点。其中,房地产开发投资31.52亿元,同比增长1.6倍。分产业来看,第二产业完成投资0.54亿元,同比下降73.5%
幂级数的收敛半径为__________.
最新回复
(
0
)