首页
登录
从业资格
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCA
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCA
最全题库
2022-08-02
44
问题
求解两个长度为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的关系模式
随机试题
Whatistheprojectofthisbid?[br]Howmuchshouldbepaidforthebiddingdo
Marketplaceorpeer-to-peer(P2P)lendingmatchesborrowersandlendersonlow
Thefloodofwomenintothejobmarketboostedeconomicgrowthandchangedt
[originaltext]Almost20,000whaleshavebeenslaughteredsinceabanoncom
下图是甲、乙两个家族系谱图。甲家族有Z遗传病患者,乙家族有红绿色盲(B-b)患
药品存放的库房内,其通道宽度应不小于A.30cm B.150cm C.50c
从“又快又好”到“又好又快”,简单的词序变化,对当前经济社会发展新形式认识的
关于生效裁判执行,下列哪一做法是正确的?()A.甲被判处管制1年,由公安机关执
某普通住宅项目的建设单位委托招标代理机构,采用公开招标的方式,办理该建设项目的招
投资项目决策分析与评价的基本要求包括贯彻落实科学发展观、资料数据准确可靠和()
最新回复
(
0
)