首页
登录
从业资格
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCA
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCA
免费题库
2022-08-02
81
问题
求解两个长度为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)
答案
D
解析
蛮力法,对X的每一个子序列,判断是否也是Y的子序列,其中,长度为n的序列X共有2^n个子序列,判断其是否是Y的子序列时间是n,因此是n*2^n;采用动态规划法自底向上实现时,根据递归公式,实际是关于i和j的两重循环,因此时间复杂度是n^2
转载请注明原文地址:http://tihaiku.com/congyezige/2424779.html
本试题收录于:
中级 嵌入式系统设计师题库软件水平考试初中高级分类
中级 嵌入式系统设计师
软件水平考试初中高级
相关试题推荐
两个月小儿,发育良好,营养中等,近日身体健康,家长带其来儿保门诊健康咨询。若患儿
小儿5岁时食管的长度为A.10cm B.12cm C.14cm D.16c
按照重要性和紧迫性把事情分成两个维度,把所有事情纳入四个象限,按照顺序灵活而有序
IPv6地址长度为()bit。A.32 B.64 C.128 D.256
两个带符号的数进行运算时,在()的情况下有可能产生溢出。A.同符号数相加 B.
设有两个子网210.103.133.0/24和210.103.130.0/24,
通过局域网接入因特网,图中箭头所指的两个设备是()。 A.二层交换机 B.路
不能打开HTML源码文件的软件为()。若在网页中需要增加“提交”和“重置”两个
不能打开HTML源码文件的软件为()。若在网页中需要增加“提交”和“重置”两个
在以太网的帧结构中,帧首定界符的长度为一个字节,其值为()。当以太网中数据传输
随机试题
Whichofthefollowingisclosestinmeaningtothestatementyou’vejustheard?
阅读以下说明和Java程序,填充程序中的空缺,将解答填入答题纸的对应栏内。
关于咬创伤,哪项是错误的()A.创伤可引起牙周炎症 B.急性创伤常
下面谱例中的旋律出自歌曲《山不转水转》,其旋律取材于哪首民歌? A.小白菜
下列法律部门中,属于行政法的是( )。A、《建筑法》 B、《城乡规划法》
奎尼丁禁用于A.糖尿病患者B.肾衰竭患者C.慢性阻塞性肺气肿患者D.孕妇及哺乳期
根据以上材料,回答96-100题; 2006年至2011年期间,平均
美国行为主义心理学家华生在《行为主义》一书中写道:“给我一打健康的婴儿,一个由我
滑坡的发展过程通常可分为蠕滑、滑动、剧滑和稳定四个阶段。但由于条件不同,有些滑坡
某男,8岁。发育迟缓,身材矮小,智力低下,动作迟笨,骨骼痿软。根据藏象理论,回答
最新回复
(
0
)