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

admin2010-12-17 40

问题某算法的时间代价递推关系为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://www.kaotiyun.com/show/74xZ777K

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

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

软考中级

相关试题推荐

ODQDB同时支持(33)两种服务。DQDB子网的双总线结构由(34)总线以及接在这两条总线上的大量的节点组成。DQDB网络为双总线提供了(35)访问控制方式，其中能够提供非等时服务是(36)，它用于(37)业务。
IEEE802定义的局域网参考模型中，只包括了物理层和数据链路层，其中LLC通过其LLC地址为高层提供服务访问的接口，这个接口是(20)，在LLC帧中，广播地址是通过(21)表示的，将数据链路层划分成LLC和MAC，主要目的是(22)。
TheBorderGatewayProtocol(BGP)isaninterautonomoussystem【S1】protoco1．TheprimaryfunctionofaBGPspeakingsystemistoexc
两个公司希望通过Internet传输大量敏感数据，从信息源到目的地之间的传输数据以密文形式出现，而且不希望由于在传输结点使用特殊的安全单元而增加开支，最合适的加密方式是()，使用会话密钥算法效率最高的是()。
某项目主要由A～I任务构成，其计划图(如下图所示)展示了各任务之间的前后关系以及每个任务的工期(单位：天)，该项目的关键路径是()。在不延误项目总工期的情况下，任务A最多可以推迟开始的时间是()天。
在软件项目管理中可以使用各种图形工具来辅助决策，下面对Gantt图的描述错误的是(5)。
根据以下RedhatLinux9.0操作系统的提示信息，空缺处的Apache服务操作命令是(59)。[root@gczroot]#servicehttpdstart[root@gczroot]#(59)httpd(pid
IPv6是下一代IP协议。IPv6的基本报头包含(27)B，此外还可以包含多个扩展报头。基本报头中的(28)字段指明了一个特定的源站向一个特定目标站发送的分组序列，各个路由器要对该分组序列进行特殊的资源分配，以满足应用程序的特殊传输需求。一个数据流由(29
在计算机系统中采用总线结构，便于实现系统的积木化构造，同时可以______。
BorderGatewayProtocol(BGP)isinter-autonomoussystem(71)protoc01．BGPisbasedonaroutingmethodcalledpathvectorrouting

随机试题

外用无效，口服治疗体表癣的药物：因毒性较大，不作注射应用的抗真菌药物：
男，20岁，发热20天，心悸、气短、乏力5天住院。体检：体温37.9℃，血压：17.3/12.0kPa(130/90mmHg)，两肺细湿啰音，心界扩大，心尖闻及S3，心率128次/分，下肢水肿。血CK、CK-MB增高以下治疗哪项错误
吡拉西坦为
以部位命名的外科疾病是以形态命名的外科疾病是
承包人不能按期开工，应在不迟于协议书约定的开工日期()，以书面形式向咨询工程师提出延期开工的理由和要求。
公司出现解散事由，应按规定进行清算。下列关于清算组活动规则的说法中，符合《公司法》规定的是()。
Drunkendriving,sometimescalledAmerica’ssociallyacceptedformofmurder,hasbecomeanationalepidemic.Everyhourofever
木卡姆又称“十二木卡姆”，是_______族的一种传统音乐。
下列有语病的一句是（）。
EnergyCycleDoyoufindgettingupinthemorningsodifficultthatit’spainful?Thismightbecalledlaziness,butDr.Kl

最新回复(0)

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

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

软考中级

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

IEEE802定义的局域网参考模型中，只包括了物理层和数据链路层，其中LLC通过其LLC地址为高层提供服务访问的接口，这个接口是(20)，在LLC帧中，广播地址是通过(21)表示的，将数据链路层划分成LLC和MAC，主要目的是(22)。

TheBorderGatewayProtocol(BGP)isaninterautonomoussystem【S1】protoco1．TheprimaryfunctionofaBGPspeakingsystemistoexc

两个公司希望通过Internet传输大量敏感数据，从信息源到目的地之间的传输数据以密文形式出现，而且不希望由于在传输结点使用特殊的安全单元而增加开支，最合适的加密方式是()，使用会话密钥算法效率最高的是()。

某项目主要由A～I任务构成，其计划图(如下图所示)展示了各任务之间的前后关系以及每个任务的工期(单位：天)，该项目的关键路径是()。在不延误项目总工期的情况下，任务A最多可以推迟开始的时间是()天。

在软件项目管理中可以使用各种图形工具来辅助决策，下面对Gantt图的描述错误的是(5)。

根据以下RedhatLinux9.0操作系统的提示信息，空缺处的Apache服务操作命令是(59)。[root@gczroot]#servicehttpdstart[root@gczroot]#(59)httpd(pid

在计算机系统中采用总线结构，便于实现系统的积木化构造，同时可以______。

BorderGatewayProtocol(BGP)isinter-autonomoussystem(71)protoc01．BGPisbasedonaroutingmethodcalledpathvectorrouting

外用无效，口服治疗体表癣的药物：因毒性较大，不作注射应用的抗真菌药物：

男，20岁，发热20天，心悸、气短、乏力5天住院。体检：体温37.9℃，血压：17.3/12.0kPa(130/90mmHg)，两肺细湿啰音，心界扩大，心尖闻及S3，心率128次/分，下肢水肿。血CK、CK-MB增高以下治疗哪项错误

吡拉西坦为

以部位命名的外科疾病是以形态命名的外科疾病是

承包人不能按期开工，应在不迟于协议书约定的开工日期()，以书面形式向咨询工程师提出延期开工的理由和要求。

公司出现解散事由，应按规定进行清算。下列关于清算组活动规则的说法中，符合《公司法》规定的是()。

Drunkendriving,sometimescalledAmerica’ssociallyacceptedformofmurder,hasbecomeanationalepidemic.Everyhourofever

木卡姆又称“十二木卡姆”，是_______族的一种传统音乐。

下列有语病的一句是（）。

EnergyCycleDoyoufindgettingupinthemorningsodifficultthatit’spainful?Thismightbecalledlaziness,butDr.Kl