首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(62)。经分析
求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(62)。经分析
admin
2019-07-12
23
问题
求解两个长度为n的序列X和Y的一个最长公共序列(如序列ABCBDAB和BDCABA的一个最长公共子序列为BCBA)可以采用多种计算方法。如可以采用蛮力法,对X的每一个子序列,判断其是否也是Y的子序列,最后求出最长的即可,该方法的时间复杂度为(62)。经分析发现该问题具有最优子序列,可以定义序列成都分别为i和j的两个序列X和Y的最长公共子序列的成都为C[i,j]如下式所示。该方法的时间复杂度为(63)。
(62)
选项
A、O(n
2
)
B、O(n
2
lgn)
C、O(n
3
)
D、O(n2
n
)
答案
D
解析
转载请注明原文地址:https://kaotiyun.com/show/sQCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
根据问题描述,填写图2-1中(1)~(4)处联系的类型。联系类型分为一对一、一对多和多对多三种,分别使用1:1,1:n或1:*,m:n或*:*表示。根据问题描述,写出客户、委托书和派工单这三个关系的主键。
(1)nv[i-1][j]≥nv[i-1][j-p[i]]+v[i](2)nv[i][j]=nv[i-1][j](3)j=j-p[i]现有5项食物,每项食物的营养价值和价格如下表所示。食物营养价值及价格表 若要求总价格不超过100的营养
指出哪张图的哪个文件可以不必画出。根据题中说明和数据流图分析,“查询处理”是否可以查询出剩余票的信息?为什么?
阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】本程序从正文文件text.in中读入一篇英文短文,统计该短文中不同单词及出现次数,并按词典编辑顺序将单词及出现次数输出到正文文件word.out中。程序用一棵有序二叉树存
请补充函数fun(),该函数的功能是将字符串tt中的大写字母都改为对应的小写字母,其他字符不变。例如,若输入“AreyoucomefromSichuan?”,则输入“areyoucomefromsi-chuan?”。注意:部分源程
(1)请说明流程图1中的文件F0、F1分别是哪个文件。(2)处理1和处理5分别按照哪些数据项进行分类?处理4能发现哪些错误(不需考虑设备故障错误)?
阅读下列说明和图,回答问题1至问题3。【说明】某汽车数字仪表板将完成下述功能:(1)通过模/数转换,实现传感器和微处理器的接口。(2)在发光二极管面板上显示数据。(3)指示速度(mph)、行驶里程、油耗(mpg)等。(4)指
利用存在的依赖关系构造一个图书馆的对象模型。张三到图书馆借阅一本书,两个月后,他把这本逾期的书返还给图书馆。画出这个场景的时序图。
国际标准MPEG—Ⅱ采用了分层的编码体系,提供了4种技术,它们是(46)。数字音频采样和量化过程所用的主要硬件是:(47)。AC-3数字音频编码提供了5个声道的频率范围是:(48)。要把一台普通的计算机变成多媒体计算机要解决的关键技术是:(
传统的数据库基本上是由(38)组成的。(39)在技术和理论上已经成熟,成为当前商用数据库的主流。(40)技术是20世纪80年代中期引入的。目前,多媒体数据库基本上靠与关系模式相结合的(41)来支持。但当数据量大,数据结构复杂时,靠(41)很难适应。当前,在
随机试题
急性胃炎的主要病损为
民法[浙工商2015年研]
砂石桩和水泥粉煤灰碎石桩对于()的地基加固效果最明显。
甲商店为增值税一般纳税人,主要从事副食品批发、零售业务,2017年11月发生如下业务:(1)向枣农收购一批红枣,农产品收购发票上注明买价30000元,该批红枣一部分用于销售、一部分无偿赠送关联企业、一部分用于职工个人消费;(2)销售烟酒商品取得含增值
个人贷款的额度可以根据以下哪几项确定?()
对购买联程或回程机票而在当地停留72小时以上的旅游者,导游应提醒其须在该联程或回程航班飞机离站前()以前办理座位再证实手续。
每次看到“月晕”就要“刮风”,地板“潮湿”就要“下雨”,就能得出“月晕而风,础润而雨”的结论这属于思维的哪种特点()
(2002)设向量组α1,α2,α3线性无关,向量β1可由α1,α2,α3线性表示,而向量β2不能由α1,α2,α3线性表示,则对任意常数k,必有()
实现数据库的哪个特性能够避免对未提交更新的依赖("脏数据"的读出)?
下列哪一个不是网络协议的要素?
最新回复
(
0
)