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

admin2018-11-21 79

问题求解两个长度为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)

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

软考中级

TCP/IP协议分为四层，分别为应用层、传输层、网际层和网络接口层。不属于应用层协议的是(62)，属于网际层协议的是(63)。

以下关于信息库(Repository)的叙述中，最恰当的是(18)；(19)不是信息库所包含的内容。

在计算机中，最适合进行数字加减运算的数字编码是(1)。如果主存容量为16M字节，且按字节编址，表示该主存地址至少应需要(2)位。

在编制监理规划时，有关监理措施的内容应突出(58)。

存储技术是在服务器附属存储SAS和直接附属存储DAS基础上发展起来的，表现为两大技术SAN和NAS。下面对SAN和NAS描述不正确的是：_____________。

数据流程图(DFD)是一种能全面地描述信息系统逻辑模型的主要工具，在数据流程图中方框表示(28)，(29)不属于数据流程图的基本成分。(29)

钻孔时的背吃刀量，就是钻头的直径尺寸。()

阳湖派古文和常州词派的开创者是【】

一类高层建筑内走道吊顶应采用()。

溢油在海面上的变化是极其复杂的，溢油动力学过程一般划分为()。

根据动机所起作用的大小，我们可以把学习动机区分为()

大多数国家的高等学校可分为三个层次，分别是：__________、大学和专门学院、研究生院。

下列诗句的作者及时代，对应正确的一项是：①但使龙城飞将在，不教胡马度阴山②池塘生春草，园柳变鸣禽③王师北定中原日，家祭无忘告乃翁④天街小雨润如酥，草色遥看近却无⑤我自横刀向天笑，去留肝胆两昆仑

激进建构主义的原则是什么？

设循环队列的存储空间为Q(1：100)，初始状态为空。现经过一系列正常操作后front=49，则循环队列中的元素个数为()