首页
登录
从业资格
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCA
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCA
最全题库
2022-08-02
20
问题
求解两个长度为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://www.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的关系模式
随机试题
TheTruthaboutLyingRickyGervais’snewfilm,TheInv
不侵入气管就能进行IPPV机械通气的人工气道有()A.异型气管导管 B.面
有一种新合成的化学物质,拟应用于化妆品中,在此之前需要进行安全性评价。毒理学安全
固体分散体具有速效作用是因为()。A:载体溶解度大 B:药物溶解度大 C:
A.吐物清稀无味 B.吐物秽浊不洁 C.吐物未化,味酸腐 D.呕吐黄绿苦水
从所给的四个选项中,选择最合适的一个填入问号处,使之呈现一定的规律性:
边缘计算指的是在网络边缘结点来处理、分析数据。边缘结点指的就是在数据产生源头和云
董事会应根据商业银行情况单独或合并设立其专门委员会,如()A.战略委员会
既清肝明目,又润肠通便的药是A.决明子 B.火麻仁 C.蔓荆子 D.青葙子
银行承兑汇票的承兑银行,应当按照票面金额向出票人收取()的手续费。A:千分之一
最新回复
(
0
)