首页
登录
从业资格
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCA
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCA
最全题库
2022-08-02
59
问题
求解两个长度为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的关系模式
随机试题
SummaryListentothepassage.Forquestions26—30,completethenotesusingno
某工程公司在一大厦广场基础工程进行护坡桩锚杆作业。当天工地主要负责人、安全员、电
Routersperformthedecisionprocesstha
智能具有感知、记忆、自适应等特点,能够存储感知到的外部信息及由思维产生的知识,同
《中国药典》2015年版规定,血竭用高效液相色谱法测定,血竭素含量不得少于A.1
共用题干 RelievingthePain"Exercisemaybe
关于站用变运行规定中描述错误的有()。树脂绝缘干式站用变宜安装在室内。安装在室外
甲公司2×19年12月3日与乙公司签订产品销售合同。合同约定,甲公司向乙公司销售
(2020年真题)根据现行《标准设计施工总承包招标文件》工程总承包项目合同中的暂
(2015年真题)杨某曾在多个金矿从事风钻作业十多年,最近被诊断患有尘肺病。杨某
最新回复
(
0
)