首页
登录
从业资格
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCA
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCA
最全题库
2022-08-02
41
问题
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为( )。经分析发现该问题具有最优子结构,可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为C[i,j],如下式所示。
采用自底向上的方法实现该算法,则时间复杂度为( )。问题1选项A.O(n2)B.O(n2lgn)C.O(n3)D.O(n2n)问题2选项A.O(n2)B.O(n2lgn)C.O(n3)D.O(n2n)
选项
答案
DA
解析
1.X、Y的所有子序列都检查过后即可求出X、Y的最长公共子序列。X的一个子序列相应于下标序列1,2,…,n的一个子序列。因此,X共有2n个子序列。当然,Y也有2m个子序列。判断一个子序列是否也是Y的子序列的时间是n,因此时间复杂度为O(n2n)
2.动态规划的一个计算最长公共子序列的方法如下,两个序列X、Y:
设有二维数组c
[j]表示X的i位和Y的j位之前的最长公共子序列的长度,则有题干给定的函数表现形式:
其中,c(i,j)当X的第i位与Y的第j位完全相同时为”1“,否则为”0“。
此时,c
[j]中最大的数便是X和Y的最长公共子序列的长度,依据该数组回溯,便可找出最长公共子序列。该算法的空间、时间复杂度均为O(n2)。
转载请注明原文地址:https://tihaiku.com/congyezige/2410404.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
DES是一种(请作答此空)加密算法,其密钥长度为56位,3DES是基于DES的加
DES是一种()加密算法,其密钥长度为56位,3DES是基于DES的加密方式,
以下关于并发调度的说法中,正确的是()。A.以不同串行方式调度执行两个事务,
一个栈的输入序列为1,2,3,4,5,不可能得到的输出序列是()。A.2,3
对于给定的关键字序列{47,34,13,12,52,38,33,27,5},若用
将一个关系r分解成两个关系r1和r2,再将分解之后的两个关系r1和r2进行自然连
假定用户A、B分别从I1、I2两个CA取得了各自的证书,下面( )是A、B互信
数据挖掘的分析方法可以划分为关联分析、序列模式分析、分类分析和聚类分析四种。如果
数据字典中“数据项”的内容包括:名称、编号、取值范围、长度和( )。A.处理频
有两个关系模式R(A,B,C,D)和S(A,C,E,G),则X=RxS的关系模式
随机试题
A.equipmentB.maintainC.forexampleD.contact
Crimehasitsowncycles,amagazinereportedsomeyearsago.Police【B1】___
Scientistssayitmaybefiveorsixyears_____thismedicineistestedonhuma
[originaltext]Goodafternoon,everybody,todayIamgoingtotellyousome
[originaltext]M:Hi,Sarah.What’sup?W:Oh,hi,Ijustgotoutofahistoryc
马克思认为,人的劳动能力是()的总和。A.知识与能力 B.智力与能力 C.体
A.风疹病毒 B.麻疹病毒 C.狂犬病毒 D.流感病毒 E.水痘一带状疱
政府公共产品体系构成中,不属于社会类公共产品的是()。A.环境保护与环境卫
按照动机产生的根源可把动机划分为()。A.生理性动机和社会性动机 B.有意识
女,35岁。腹胀、腹部隐痛伴低热3个月。突发脐周绞痛6小时,呕吐数次,无排气,排
最新回复
(
0
)