首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(62)。经分析
求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(62)。经分析
admin
2019-07-12
66
问题
求解两个长度为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层图中的全部可选起点(第0层图和第1层图中均未给出)。打印分户账清单时,必须以下列哪一组数据作为关键字进行排序,才能满足需求?请从下面选项中选择。①储蓄所②账号⑧开户日
阅读以下说明和图,填补流程图中的空缺。【说明】在一条农村公路的一边稀疏地分布着房子,其分布如图10-5所示。某电信公司需要在某些位置放置蜂窝电话基站,由于基站的覆盖范围是6公里,因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化
根据[说明]中的描述,使用参与者列表的英文名称,给出ORS用例图中A1~A4所对应的参与者。根据[说明]中的描述,使用用例名称列表和活动名称列表中的英文名称,给出提交稿件过程的活动图中Actionl~Action4对应的活动。
根据[说明]中的描述,使用参与者列表的英文名称,给出ORS用例图中A1~A4所对应的参与者。根据[说明]中的描述,给出ORS用例图中(1)和(2)所对应的关系。
【说明】一个图书馆信息管理系统的分析与建模。下面是某图书馆的有关介绍。图书馆雇有若干管理员,各自具有编码、姓名等属性。管理员可上岗,也可下岗。图书馆中备有若干图书,每本图书有书号、书名、出版社、价格等属性。图书馆不定期地购买并注册新
指出算法的流程图中(1)~(3)处的内容。指出测试用例设计中(4)~(9)处的内容。
仔细分析系统的用例说明和用例图,从功能要求角度来看,该系统的用例并不完善。请根据功能要求补充至少两个用例,并作简单说明。根据SteveCook和JohnDanils的观点,类图可以分为三个层次:概念层(Conseptual)、说明层(Specifi
多媒体技术的关键在于解决动态图像和声音的存储与传输问题。若不经压缩,以 VGA640×480点阵存储一幅256色的彩色图像大约需(56)MB存储空间,以9600bit/s的速度传输这幅图像大约需(57)秒,按我国电视PAL标准每秒25幅,一张650MB的光
随机试题
考生文件夹下有一个数据库文件“samp3.accdb”,其中存在已经设计好的表对象“tEmp”、窗体对象“fEmp”、报表对象“rEmp”和宏对象“mEmp”。请在此基础上按照以下要求补充设计:将表对象“tEmp”中“聘用时间”字段的格式调整为“长日
管理心理学形成的理论准备包括()
一黄疸患者肝内胆管扩张,肝外胆管未显示,胆囊未充盈,其梗阻部位最可能为
根据会计法律制度的规定,下列各项中,单位出纳人员不得兼任的工作有()。
申请独立董事的任职资格,应当具备的条件有()。
关于筹建中的公司的法律地位表述正确的是()。
男性,20岁,未婚,某大学四年级学生,家在农村,排行老二,上有一姐,下有一弟。自我陈述:近一年来记忆力下降,没精神看书,逻辑分析能力下降,紧张。害怕考试,害怕老师为难我,睡不好觉,晚上睡不着,白天没精神,食欲下降,身体也比以前瘦了,曾去医院检查过内
“神九”任务乘组发回首条面向公众的太空短信。2012年6月25日16时43分,女航天员刘洋代表神舟九号航天员飞行乘组,利用地面与天宫一号目标飞行器电子邮件传输系统,发回了第一条面向公众的太空短信,通过“天宫一号”科普微博,向祖国致敬!向全国人民问好!这条来
窗体中有图片框(Picture1)和计时器(Timer1)两个控件。程序运行时,将图片加载到图片框中,然后图片框以每秒一次的速度向窗体的右下角移动,每次向左、向右移动300twip。请在程序空白处填入适当内容使程序完整。PrivateSub
Manystudentsdonotliketostudyhistory(历史).Theysaythatthereare【41】manynamesanddatesto【42】.Butifwedonotkno
最新回复
(
0
)