首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。 经分析发现该问题具有最优子结构,可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j],
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。 经分析发现该问题具有最优子结构,可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j],
admin
2018-11-21
30
问题
求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。
经分析发现该问题具有最优子结构,可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j],如下式所示。
采用自底向上的方法实现该算法,则时间复杂度为_____________。
选项
A、O(n
2
)
B、O(n
2
lgn)
C、O(n
3
)
D、O(n2
n
)
答案
A
解析
本题考查算法设计与分析的基本知识。要求考生熟悉典型的算法设计技术及其典型的问题的求解。
应用蛮力法求解最长公共子序列时,其思路在题干已经给出。对X的每一个子序列,判断其是否也是Y的子序列,那么长度为n的序列X的子序列数是2
n
,而判断一个子序列是否也是Y的子序列的时间是n,因此时间复杂度为O(n2
n
)。
而采用动态规划自底向上的方法求解时,题干也给出了最优子结构和递归式的定义,因此很容易看出算法的时间复杂度实际上就是i和j的两重循环,时间复杂度为O(n
2
)。
转载请注明原文地址:https://kaotiyun.com/show/fRWZ777K
本试题收录于:
嵌入式系统设计师上午基础知识考试题库软考中级分类
0
嵌入式系统设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某事业单位需要在新建办公楼内建设办公网络系统,内容主要包括综合布线系统、网络机房建设等。建设方通过公开招标与承建单位签订合同。同时为了规范管理,建设方聘请了监理单位参与项目管
阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】国家某部委针对宏观经济大数据决策支持系统建设项目,通过公开招标选择某监理公司对项目实施全过程监理。在项目招标过程中发生了如下事件:【事件1】由于是部委级项目,根据
阅读下列说明,回答问题,将解答填入对应栏内。【说明】某单位甲进行企业信息化工程建设,主要包括网络基础平台的建设、综合布线系统的建设、网络安全平台的建设等工作,甲以邀请招标的方式委托了监理公司单位丙承担该工程项目的监理工作。施工前,丙与甲及承建单位乙一起
阅读下列说明,回答问题,将解答填入对应栏内。【说明】某电信项目建设单位甲通过公开招标选择单位乙为承建单位,承担某大型信息网络系统工程的实施任务,并委托监理单位丙对项目实施全过程监理。该工程涉及机房建设、系统集成和应用软件开发等内容。在建设过程中,发生了
阅读下列说明,回答问题,将解答填入对应栏内。【说明】X省通信运营商拟开发运营支撑系统应用软件,管理企业的业务流程和基础资源。建设单位通过公开招标方式选择了监理单位,以便协助建设单位做好全过程的监理工作。该项目承建单位采用瀑布模型进行软件开发。在项目开发
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某省计划2020年初步建成信息共享的生态环境监测网络。通过招标,建设单位确认了A单位为承建单位,B单位为监理单位。随着项目建设任务的推进,B单位根据项目建设的总体进度计划,要求A单位在合同规定
应用系统开发所需要的成本和资源估算属于可行性研究中的(54)研究内容。
为了指导计算机网络的互连、互通,ISO颁布了OSI参考模型,其基本结构分为(1)。网卡(网络适配器)的主要功能不包括(2)。
下面对于业主单位实施工程监理招标过程顺序的描述,正确的是________。
随机试题
作业活动分析后应使治疗师了解该项活动
建筑安装工程一切险投保费在国外建筑安装工程费用中记入()。
隧道施工中,应对地面、地层和支护结构进行动态监测,并及时()。
计算应交所得税的依据是()。
下列不属于关税特征的是()。
以修改其他债务条件进行债务重组的,如果债务重组协议中附有或有应付金额的,该或有应付金额最终没有发生的,债务人应()。
社会化过度是指把成年人某些社会化的任务前移到了部分青少年身上。现在我们的教育过早及过多地给予孩子们社会规范、纪律约束和强求一律的认同,极易造成青少年的社会化过度。根据上述定义,下列行为中不属于社会化过度的是()。
近日,研究人员发现发烧可以促进淋巴细胞向感染部位转移。他们解释说,这是由于发烧会增加热休克蛋白90(Hsp90)在T淋巴细胞中的表达,这种蛋白质与整合素结合,促进T淋巴细胞黏附到血管上,最终加快迁移到感染的位置。以下除哪项外,均能支持上述结论?
学生在理解“力”概念的基础上,再来学习“重力”的概念。这种学习属于()。
设A=E一ααT,其中α为n维非零列向量.证明:(1)A2=A的充分必要条件是α为单位向量;(2)当α是单位向量时A为不可逆矩阵.
最新回复
(
0
)