首页
登录
从业资格
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCA
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCA
题库
2022-08-02
39
问题
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为( )。经分析发现该问题具有最优子结构,可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j],如下式所示。
采用自底向上的方法实现该算法,则时间复杂度为(请作答此空)A.O(n^2)B.O(n^21gn)C.O(n^3)D.O(n2^n)
选项
A.O(n^2)
B.O(n^21gn)
C.O(n^3)
D.O(n2^n)
答案
A
解析
蛮力法,对X的每一个子序列,判断是否也是Y的子序列,其中,长度为n的序列X共有2^n个子序列,判断其是否是Y的子序列时间是n,因此是n*2^n;采用动态规划法自底向上实现时,根据递归公式,实际是关于i和j的两重循环,因此时间复杂度是n^2.
转载请注明原文地址:https://tihaiku.com/congyezige/2424435.html
本试题收录于:
中级 嵌入式系统设计师题库软件水平考试初中高级分类
中级 嵌入式系统设计师
软件水平考试初中高级
相关试题推荐
两个月小儿,发育良好,营养中等,近日身体健康,家长带其来儿保门诊健康咨询。若患儿
两个月小儿,发育良好,营养中等,近日身体健康,家长带其来儿保门诊健康咨询。该疫苗
两个月小儿,发育良好,营养中等,近日身体健康,家长带其来儿保门诊健康咨询。护士应
按照重要性和紧迫性把事情分成两个维度,把所有事情纳入四个象限,按照顺序灵活而有序
设机器码的长度为8,x为带符号纯小数,y为带符号纯整数,[X]原=1111111
设有两个子网210.103.133.0/24和210.103.130.0/24,
不能打开HTML源码文件的软件为()。若在网页中需要增加“提交”和“重置”两个
不能打开HTML源码文件的软件为()。若在网页中需要增加“提交”和“重置”两个
在以太网的帧结构中,帧首定界符的长度为一个字节,其值为()。当以太网中数据传输
在以太网的帧结构中,帧首定界符的长度为一个字节,其值为()。当以太网中数据传输
随机试题
Wehavenoresponsibilityforthefailureofourcooperation.Itisyourcompany
图示均质圆轮,质量为m,半径为r,在铅垂图面内绕通过圆盘中心O的水平轴转动,角速
《继续教育暂行规定》和《住院医师制度化规范化培训条例(试行)》颁布于()
中医学治疗疾病及疗养调补的基本原则是()A.调整人体阴阳的平衡 B.损其有余
关于遗传对儿童生长发育影响的叙述哪项是错误的A.遗传决定了儿童生长发育的潜力
下列属于现代医学目的的是()A.重治疗轻预防 B.提高生命质量 C
Theexpeditionreachedthesummitat10:
临床牙冠与固定义齿功能直接有关的是A.连接强度 B.固位力 C.支持力 D
不同对象的培训与开发应包含()。A.决策管理层 B.监督管理层 C.专业技
交流系统用单芯电力电缆的(),应同时满足电缆金属护层正常或感应电压不超过允许值
最新回复
(
0
)