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

admin2018-11-21 31

问题求解两个长度为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://jikaoti.com/ti/hfI7FFFM

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

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

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

在选择多媒体数据压缩算法时需要综合考虑(62)。

减少指令执行周期数是RISC计算机性能提高的基础，它是通过(7)、指令控制部件(8)微代码和(9)等来实现的。

以下不属于服务器磁盘接口总线标准的是(20)。

A、麻疹病毒B、腮腺炎病毒C、痢疾杆菌D、百日咳杆菌E、乙型溶血性链球菌能够产生侵袭力很强外毒素的是（）

布鲁氏菌病的主要易感动物有

制备生产工艺用水的部门对水的检查应

票据出票日期使用小写的开户银行可以受理，但由此造成的损失由出票人自行承担。()

教育科学文化建设是精神文明建设不可缺少的基本方面，它包括()。

下列物品利用凸透镜透光原理的是：

某国家工作人员李某与社会上的张某勾结，由李某利用职务便利同张某共同骗取国家大量财物。对上述行为的定性为()。

AstrangethinghappenedtomelastSunday.Itwas(16)abeautifuldaythatIdrovetogoforalookinthecountry.Ont

Ishalltellhimthetruth,______.

Teachingchildrentoreadwellfromthestartisthemostimportanttaskofelementaryschools.Butrelyingoneducatorstoappr