首页
登录
从业资格
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCA
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCA
资格题库
2022-08-02
73
问题
求解两个长度为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/2424780.html
本试题收录于:
中级 嵌入式系统设计师题库软件水平考试初中高级分类
中级 嵌入式系统设计师
软件水平考试初中高级
相关试题推荐
女,51岁。绝经5年,阴道脱出肿物3年。近两个月阴道脱出肿物增大,不能自行还纳,
两个月小儿,发育良好,营养中等,近日身体健康,家长带其来儿保门诊健康咨询。该疫苗
两个月小儿,发育良好,营养中等,近日身体健康,家长带其来儿保门诊健康咨询。护士应
IPv6地址长度为()bit。A.32 B.64 C.128 D.256
通过局域网接入因特网,图中箭头所指的两个设备是()。 A.二层交换机 B.路
某商场的部门和商品两个实体之间的关系如下图所示。假设每个部门负责销售若干种商品,
不能打开HTML源码文件的软件为()。若在网页中需要增加“提交”和“重置”两个
不能打开HTML源码文件的软件为()。若在网页中需要增加“提交”和“重置”两个
在以太网的帧结构中,帧首定界符的长度为一个字节,其值为()。当以太网中数据传输
在以太网的帧结构中,帧首定界符的长度为一个字节,其值为()。当以太网中数据传输
随机试题
TheQUIK-FRYTMElectronicWok[img]2012q2/ct_eyyjsbz2011a_eyyjsbreadb_0038_2
Morethan100000internationalstudentswillspendthissummerworkingand
肺炎喘嗽风寒闭肺型首选是A.羚角钩藤汤 B.三拗汤合葱豉汤 C.麻杏石甘汤
A.分层 B.絮凝 C.转相 D.破裂 E.酸败乳剂中加入抗氧剂的目的是
Thechangeinthatvillagewasmiraculou
增进公共组织领导有效性的方法是()。A.提高领导者素质 B.加强干部队
一个完整的测量结果应包含()。 A.测得的原始数据及分析 B.被测量Y的最
对民用建筑进行防火检查时,检查人员应注意特殊场所的平面布置和安全疏散是否符合要求
若不考虑财务风险,利用每股收益无差别点进行企业资本结构分析时,以下说法中错误的是
根据《建设工程安全生产管理条例》的规定,工程监理单位未对施工组织设计中的安全技术
最新回复
(
0
)