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

admin2018-11-21 58

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

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

软考中级

图像文件格式分为静态图像文件格式和动态图像文件格式，(16)属于静态图像文件格式。以下文件格式中，(17)不是声音文件。

在信息系统项目知识产权保护的监理工作中，下面有关知识产权监理措施中(52)的描述是错误的。

若某计算机系统是由500个元器件构成的串联系统，且每个元器件的失效率均为　10-7/h，在不考虑其他因素对可靠性的影响时，该计算机系统的平均故障间隔时间为(5)h。

不属于干扰素的生物学作用的是

下列属于P3e的特点是()。

山区公路跨过山谷的路堤较高，泄洪涵洞埋置较深，根据泄洪流量可以选用的泄洪涵洞形式有()。

保险基金属于《证券投资基金法》的调整对象。()

下列各项中，属于事业单位净资产类科目的有()。

一份购销合同中所载购销金额100万元，实际执行结果为120万元，签订合同时已按100万元计算缴纳了印花税，因未修改合同，所以不再补交印花税。()

英国议会在1689年通过了《权利法案》，其中规定()。

公安工作具有鲜明的阶级性，所谓阶级性，即警察与国家一致的特点。国家要求警察必须与国体一致，与政体一致，与国家意志一致。（）

Beforethe20thcenturythehorseprovideddaytodaytransportationintheUnitedStates.Trainswereusedonlyforlong-distan

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

软考中级

图像文件格式分为静态图像文件格式和动态图像文件格式，(16)属于静态图像文件格式。以下文件格式中，(17)不是声音文件。

在信息系统项目知识产权保护的监理工作中，下面有关知识产权监理措施中(52)的描述是错误的。

若某计算机系统是由500个元器件构成的串联系统，且每个元器件的失效率均为 10-7/h，在不考虑其他因素对可靠性的影响时，该计算机系统的平均故障间隔时间为(5)h。

不属于干扰素的生物学作用的是

下列属于P3e的特点是()。

山区公路跨过山谷的路堤较高，泄洪涵洞埋置较深，根据泄洪流量可以选用的泄洪涵洞形式有()。

保险基金属于《证券投资基金法》的调整对象。()

下列各项中，属于事业单位净资产类科目的有()。

一份购销合同中所载购销金额100万元，实际执行结果为120万元，签订合同时已按100万元计算缴纳了印花税，因未修改合同，所以不再补交印花税。()

英国议会在1689年通过了《权利法案》，其中规定()。

公安工作具有鲜明的阶级性，所谓阶级性，即警察与国家一致的特点。国家要求警察必须与国体一致，与政体一致，与国家意志一致。（）

Beforethe20thcenturythehorseprovideddaytodaytransportationintheUnitedStates.Trainswereusedonlyforlong-distan

若某计算机系统是由500个元器件构成的串联系统，且每个元器件的失效率均为　10-7/h，在不考虑其他因素对可靠性的影响时，该计算机系统的平均故障间隔时间为(5)h。