首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(62)。经分析
求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(62)。经分析
admin
2019-07-12
55
问题
求解两个长度为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至问题4。【说明】某宾馆需要建立一个住房管理系统,部分的需求分析结果如下:(1)一个房间有多个床位,同一房间内的床位具有相同的收费标准,不同房间的床位收费标准可能不同;(2)每个房间有房间号(如201、20
表10-5所给出的类并不完整,根据[说明]和表10-4,将图10-4中的(a)~(c)处补充完整。识别关联的多重度是面向对象建模过程中的一个重要步骤。根据[说明]中给出的描述,完成图10-4中的(1)~(6)。
根据问题描述,填写图10-3实体联系图中(1)~(4)处联系的类型。根据实体联系图10-3,填写挂号单、门诊处方、处方明细和药品库关系模式中的空(5)~(8)处,并指出挂号单、门诊处方和处方明细关系模式的主键。
(1)nv[i-1][j]≥nv[i-1][j-p[i]]+v[i](2)nv[i][j]=nv[i-1][j](3)j=j-p[i]现有5项食物,每项食物的营养价值和价格如下表所示。食物营养价值及价格表 若要求总价格不超过100的营养
指出哪张图的哪个文件可以不必画出。指出数据流图4-1和数据流图4-2中错误的数据流。
阅读下列程序说明,将应填入(n)处的字句写在答卷纸的对应栏内。【程序说明】对于一个公司的雇员来说,无非有3种:普通雇员、管理人员和主管。这些雇员有共同的数据:名字、每小时的工资,也有一些共同的操作:数据成员初始化、读雇员的数据成员及计算雇员
指出哪张图的哪些文件可以不必画出。数据流图1口3中缺少3条数据流,请直接在图中添加。
仔细分析系统的用例说明和用例图,从功能要求角度来看,该系统的用例并不完善。请根据功能要求补充至少两个用例,并作简单说明。根据SteveCook和JohnDanils的观点,类图可以分为三个层次:概念层(Conseptual)、说明层(Specifi
阅读以下说明和图,回答问题1至问题3。[说明]图书馆藏书管理系统,完成用户信息管理,借阅归还信息管理,馆藏书目的信息管理,违规处罚管理和各种查询等功能。系统的用户可分为超级用户和普通用户两类,超级用户负责系统维护,包括对藏书信息,用户信
阅读下列说明和图,回答问题1至问题3。【说明】图书管理系统详细记录图书库存情况、读者信息及读者借阅记录(包括借书日期和还书日期)。新书入库时要为该书编制图书卡片,包括分类目录号、图书流水号(要保证每本书都有唯一的流水号,即使同类图书
随机试题
试述糖皮质激素分泌的调节机制。
《断魂枪》开头的社会环境描写,对后文人物性格的展现所起的主要作用是()
窃以为过矣。过:
A、>2500mlB、>2000mlC、<1500mlD、1000mlE、500ml基础补液量()
甲企业有一项专利权,最初入账价值为100000元,有效使用期限为5年;企业在使用2年后将其对外出售,取得转让收入80000元。甲企业除转让收入按5%缴纳营业税外无其他支出,则甲企业转让该项专利权能使其税前利润增加()元。
下列有关无形资产转让所发生的收支中,其会计处理正确的有()。
国际货币基金组织
Whosebirthdaypartyisthewomangoingto?
OnecountrythatiscertainoftheeffectoffilmsontourismisAustralia.TheTouristOfficeofQueenslandsaythatCrocodile
JapanisintheeastofChina.
最新回复
(
0
)