某算法的时间代价递推关系为T(n)=2T(n/2)+n，T(1)=1，则该算法的时间复杂度为______。

admin2010-12-17 23

问题某算法的时间代价递推关系为T(n)=2T(n/2)+n，T(1)=1，则该算法的时间复杂度为______。

选项 A、O(n)
B、

C、O(n²)
D、O(1)

答案B

解析由时间代价严格推出时间复杂度比较复杂，对于这种题，可用特例验证，不过需要注意的是特例不能取太少，至少n取到5，这样规律基本就可以确定了。
T(1)=1
T(2)=2T(1)+2=4
T(3)=2T(1)+3=5
T(4)=2T(2)+4=12
T(5)=2T(2)+5=13
很容易排除D选项，其递增速率介于O(n)和O(nsup>2)之间，故选B。

转载请注明原文地址:https://kaotiyun.com/show/74xZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

ODQDB同时支持(33)两种服务。DQDB子网的双总线结构由(34)总线以及接在这两条总线上的大量的节点组成。DQDB网络为双总线提供了(35)访问控制方式，其中能够提供非等时服务是(36)，它用于(37)业务。
图1是曼彻斯特编码，它表示的数据可能为(26)，这种编码适用的网络是(27)。为了在广域网上高速传输数字信号，一般编码方法是(28)，其编码效率为(29)。设某编码体制的编码方法为：输入数据am(m＝1,2,…)，发送时，首先计算bm＝(am+bm-1)M
DES加密算法采用的密码技术是(61)，它采用(62)bit密钥对传输的数据进行加密，著名的网络安全系统Kerberos采用的是(63)加密技术。公钥密码是(64)，常用的公钥加密算法有(65)，它可以实现加密和数字签名。
在网络体系结构中，第N层协议利用(24)提供的服务向(25)提供服务，对等实体是指(26)，数据在同一个系统自上层传到下层，这种数据格式称为(27)，某层实体接收到上层传来的数据后，一般要(28)才能使接收方知道如何处理。
下面给出了一些软件编码的原则，其中错误的是(9)。
网络隔离技术的目标是确保把有害的攻击隔离，在保证可信网络内部信息不外泄的前提下，完成网络间数据的安全交换。下列隔离技术中，安全性最好的是()。
以下ACL语句中，含义为“允许172.168.0.0/24网段所有PC访问10.1.0.10中的FTP服务”的是______。
MIB对象标识符分级树根未命名，但是有3个直接后裔，分别由ISO、(1)及(2)进行管理。分级树中关于MIB-Ⅱ节点下包括10个功能组，共171个对象。在这些功能组中是一个联系各种接口的特殊节点，与接口组相配合，提供与子网类型有关的专用信息的功能组是(3)

随机试题

简要说明社会促进、社会惰化及它们的特征。
女性，30岁，已婚，持续性右下腹痛12小时来院急诊。腹痛发作前曾有性生活史，当时觉下腹隐痛，30分钟后疼痛加剧，并伴有肛门坠胀，上厕所时曾晕厥1次。末次月经在2周前。最大可能的诊断为
患者，男，66岁。肾病综合征，血IgG，IgA，IgM均降低，首先怀疑
下列哪些疾病可引起呕吐?()
天津某单层钢结构厂房工程，基础部分采用锤击打人预应力管桩、部分采用泥浆护壁灌注桩。桩承台上预埋地脚螺栓与钢柱连接。预应力管桩打入过程中，发现桩身突然倾斜错位，经查桩尖处土质条件没有特殊变化，而贯人度突然增大；同时，当桩锤跳起后，桩身随之出现回弹现象。泥
甲公司将其一栋写字楼租赁给乙公司使用，并一直采用成本模式进行后续计量。2018年1月1日，该项投资性房地产具备了采用公允价值模式计量的条件，甲公司决定对该投资性房地产从成本模式转换为公允价值模式计量。该写字楼的原价为3000万元，已计提折旧1500万元
根据支付结算法律制度的规定，存款人发生的下列情况中，可以开立临时存款账户的有()。
下图是我国某地区等高线地形图。读图完成问题。图中山峰与甲村的相对高度可能是()。
《计算机软件保护条例》规定：对于在委托开发软件活动中，委托者与受委托者没有签订书面协议，或者在协议中未对软件著作权归属做出明确的约定，其软件著作权归(70)。
某高校学生会计划举办一场“大学生网络创业交流会”的活动，拟邀请部分专家和老师给在校学生进行演讲。因此，校学生会外联部需制作一批邀请函，并分别递送给相关的专家和老师。请按如下要求，完成邀请函的制作：在“尊敬的”和“(老师)”文字之间，插入拟邀请

最新回复(0)

某算法的时间代价递推关系为T(n)=2T(n/2)+n，T(1)=1，则该算法的时间复杂度为______。

软件设计师上午基础知识考试

软考中级

ODQDB同时支持(33)两种服务。DQDB子网的双总线结构由(34)总线以及接在这两条总线上的大量的节点组成。DQDB网络为双总线提供了(35)访问控制方式，其中能够提供非等时服务是(36)，它用于(37)业务。

DES加密算法采用的密码技术是(61)，它采用(62)bit密钥对传输的数据进行加密，著名的网络安全系统Kerberos采用的是(63)加密技术。公钥密码是(64)，常用的公钥加密算法有(65)，它可以实现加密和数字签名。

在网络体系结构中，第N层协议利用(24)提供的服务向(25)提供服务，对等实体是指(26)，数据在同一个系统自上层传到下层，这种数据格式称为(27)，某层实体接收到上层传来的数据后，一般要(28)才能使接收方知道如何处理。

下面给出了一些软件编码的原则，其中错误的是(9)。

网络隔离技术的目标是确保把有害的攻击隔离，在保证可信网络内部信息不外泄的前提下，完成网络间数据的安全交换。下列隔离技术中，安全性最好的是()。

以下ACL语句中，含义为“允许172.168.0.0/24网段所有PC访问10.1.0.10中的FTP服务”的是______。

简要说明社会促进、社会惰化及它们的特征。

女性，30岁，已婚，持续性右下腹痛12小时来院急诊。腹痛发作前曾有性生活史，当时觉下腹隐痛，30分钟后疼痛加剧，并伴有肛门坠胀，上厕所时曾晕厥1次。末次月经在2周前。最大可能的诊断为

患者，男，66岁。肾病综合征，血IgG，IgA，IgM均降低，首先怀疑

下列哪些疾病可引起呕吐?()

根据支付结算法律制度的规定，存款人发生的下列情况中，可以开立临时存款账户的有()。

下图是我国某地区等高线地形图。读图完成问题。图中山峰与甲村的相对高度可能是()。

《计算机软件保护条例》规定：对于在委托开发软件活动中，委托者与受委托者没有签订书面协议，或者在协议中未对软件著作权归属做出明确的约定，其软件著作权归(70)。