求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。经分析发现该问题具有最优子结构，可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j]，

admin2018-11-21 76

问题求解两个长度为n的序列X和Y的一个最长公共子序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。
经分析发现该问题具有最优子结构，可以定义序列长度分别为i和j的两个序列X和Y的最长公共子序列的长度为c[i,j]，如下式所示。

采用自底向上的方法实现该算法，则时间复杂度为_____________。

选项 A、O(n²)
B、O(n²lgn)
C、O(n³)
D、O(n2ⁿ)

答案A

解析本题考查算法设计与分析的基本知识。要求考生熟悉典型的算法设计技术及其典型的问题的求解。
应用蛮力法求解最长公共子序列时，其思路在题干已经给出。对X的每一个子序列，判断其是否也是Y的子序列，那么长度为n的序列X的子序列数是2ⁿ，而判断一个子序列是否也是Y的子序列的时间是n，因此时间复杂度为O(n2ⁿ)。
而采用动态规划自底向上的方法求解时，题干也给出了最优子结构和递归式的定义，因此很容易看出算法的时间复杂度实际上就是i和j的两重循环，时间复杂度为O(n²)。

转载请注明原文地址:https://www.kaotiyun.com/show/fRWZ777K

本试题收录于：嵌入式系统设计师上午基础知识考试题库软考中级分类

嵌入式系统设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

嵌入式系统设计师上午基础知识考试

软考中级

因承建单位违反合同导致工程竣工时间延长，监理单位(33)。关于信息工程实施合同工期的叙述，不正确的是(34)。由于承包商的原因导致监理单位延长了监理服务的时间，此工作内容应属于(35)。

关于网络安全服务的叙述中，(10)是错误的。

在合同的订立中，当事人一方向另一方提出订立合同的要求和合同的主要条款，并限定其在一定期限内做出答复，这种行为是(57)。

白盒法测试程序时常按照给定的覆盖条件选取测试用例。(50)覆盖比(51)覆盖严格，它使得每一个判定的每一条分支至少经历一次。(52)覆盖既是判定覆盖，又是条件覆盖，但它并不保证使各种条件都能取到所有可能的值。

在软件质量特性中，(53)是指在规定的一段时间和条件下，与软件维持其性能水平的能力有关的一组属性；(54)是指防止对程序及数据的非授权访问的能力。

心脏指数(CⅠ)直接反映

下列哪种化合物不是以胆固醇为原料合成的

下列关于心血管功能的叙述，错误的是

肺热咳嗽，甚则气急欲喘，皮肤蒸热，日晡尤甚，舌红苔黄，脉象细数者，治宜选用

房地产项目定位中属于客户定位要回答的问题有()。

(2014年)当天气由潮湿变为干燥时，建筑材料的热导率可能会出现()。

ABC会计师事务所负责审计甲公司2011年度财务报表，在制定采购与付款循环的审计计划时，注册会计师遇到下列事项，请代为做出正确的专业判断。A注册会计师在设计应付账款函证时的下列安排中恰当的是（）。

全陪应做好必要的物质准备，主要包括()。

自居易在听琵琶女的演奏后，写下来“同是天涯沦落人，相逢何必曾相识”的诗句，这是艺术鉴赏效应中的()。

EnglishBusinessLetterFormatI.Demandsofstationery—thefirstpageiswithaletterhead—otherpagesareof【T1】______and