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

admin2018-11-21 41

问题求解两个长度为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://kaotiyun.com/show/fRWZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

在下列存储管理方案中，(3)是解决内存碎片问题的有效方法。虚拟存储器主要由(4)组成。

对照①～⑤的描述，质量控制图(如下图所示)的用途是(64)。①过程分析②过程控制③分析判断质量分布状态④寻找影响质量的主次因素⑤评价过程能力

UML-basedtoolsareoftenusedforJ2EE/.NETapplicationanalysisanddesign,bothbecauseUML’sobjectorientationisidealfor

体外循环抗凝血，宜选用

某企业向银行贷款200万元，期限为1年，名义利率为12%，每季计息一次，则企业实际支付利息()万元。

以下关于报关企业跨关区申请设立分支机构条件的表述，正确的是：

下列关于最高限价的表述错误的是()。

根据《证券公司客户资产管理业务试行办法》的规定，在集合资产管理计划中，客户主要享有的权利有(　　)。

人力资源管理开发的基本手段包括()。

元认知是对自己认知活动的认知，它包括哪三个方面()

在下列进程调度算法中，可能引起进程长时间得不到运行的算法是()。

A、Itofferschancesformanytotrynewthings.B、Therearesomanyvolunteerjobstodo.C、Youhavetobeskillfulatthejoby

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

软考中级

在下列存储管理方案中，(3)是解决内存碎片问题的有效方法。虚拟存储器主要由(4)组成。

对照①～⑤的描述，质量控制图(如下图所示)的用途是(64)。①过程分析②过程控制③分析判断质量分布状态④寻找影响质量的主次因素⑤评价过程能力

UML-basedtoolsareoftenusedforJ2EE/.NETapplicationanalysisanddesign,bothbecauseUML’sobjectorientationisidealfor

体外循环抗凝血，宜选用

某企业向银行贷款200万元，期限为1年，名义利率为12%，每季计息一次，则企业实际支付利息()万元。

以下关于报关企业跨关区申请设立分支机构条件的表述，正确的是：

下列关于最高限价的表述错误的是()。

根据《证券公司客户资产管理业务试行办法》的规定，在集合资产管理计划中，客户主要享有的权利有( )。

人力资源管理开发的基本手段包括()。

元认知是对自己认知活动的认知，它包括哪三个方面()

在下列进程调度算法中，可能引起进程长时间得不到运行的算法是()。

A、Itofferschancesformanytotrynewthings.B、Therearesomanyvolunteerjobstodo.C、Youhavetobeskillfulatthejoby

根据《证券公司客户资产管理业务试行办法》的规定，在集合资产管理计划中，客户主要享有的权利有(　　)。