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

admin2018-11-21 83

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

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

软考中级

系统终验是系统投入正式运行前的重要工作，系统验收工作通常是在建设方主管部门的主持下，按照既定程序来进行，以下关于系统终验描述错误的是(46)。

路由选择协议是IP网络实用化的关键，它决定了数据包从“源”传送到“目的地”的路径：IP网络中最广泛使用的路由协议之一是(11)。能够实现路由选择功能的设备(12)。

在施工过程中，承包人应对自己采购的材料设备质量进行严格的控制，当承包人采购的材料设备与标准或者设计要求不符时，(68)的做法是错误的。

某工程分项的已完工程实际投资、拟完工程计划投资、己完工程计划投资，分别为50万元、30万元、40万元，则其投资偏差为(39)万元。

经营者不得以排挤竞争对手为目的，以低于成本的价格销售商品，下列(63)属于不正当竞争行为。

质检机构取得计量认证合格后，经()年要进行复查。

每个评价项目都有其自身的专业特点，因此，评价单位不可能事事依靠内部专家，还必须从社会上聘请一定数目的()来参加调查评价工作。

安全检查的内容不仅查管理、查隐患，还应查()。

发包人和承包人就有关工期、质量、造价等产生的建设工程合同争议，是建设工程领域最常见的()。

下列属于资产负债管理原则的有()。

流动性风险管理水平体现了商业银行的整体经营管理水平。()

旅游主管部门在作出行政处罚决定前，应当以()形式告知当事人作出行政处罚决定的事实、理由、依据和当事人依法享有的陈述、申辩权利。

不考虑价格因素，2011年与2003年相比，江苏金融业增加值增长的倍数是()。

TheplantspeciesthatDr.KinghorndiscoveredinPuertoRicoprovedtobe______tohismedicalresearch.