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

admin2010-12-17 16

问题某算法的时间代价递推关系为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

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

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

软考中级

相关试题推荐

网络协议是计算机网络和分布系统中进行互相通信的(18)间交换信息时必须遵守的规则的集合。协议的关键成分中(19)是数据和控制信息的结构或格式；(20)是用于协调和进行差错处理的控制信息；定时是对事件实现顺序的详细说明，而网络体系结构则是(21)。
图1是曼彻斯特编码，它表示的数据可能为(26)，这种编码适用的网络是(27)。为了在广域网上高速传输数字信号，一般编码方法是(28)，其编码效率为(29)。设某编码体制的编码方法为：输入数据am(m＝1,2,…)，发送时，首先计算bm＝(am+bm-1)M
两个人利用Netphone通话时，对语言格式的解释是由(19)完成的。
配置WWW服务器是UNIX操作系统平台的重要工作之一，而Apache是目前应用最为广泛的Web服务器产品之一，(59)是Apache的主要配置文件。URL根目录与服务器本地目录之间的映射关系是通过指令(60)设定；指令ServerAdmin的作用
TheBorderGatewayProtocol(BGP)isaninterautonomoussystem【S1】protoco1．TheprimaryfunctionofaBGPspeakingsystemistoexc
在进行消息认证时，经常利用安全单向散列函数产生消息摘要。安全单向散列函数不需要具有(57)特性。
在计算机系统中采用总线结构，便于实现系统的积木化构造，同时可以__________。(2011年上半年试题)
Kerberos要求用户使用(1)作为自己的标识，而客户端与KDC服务器之间的交互则使用(2)。当用户需要和其他用户通信时，需要从服务器端获得(3)，然后再用其向KDC服务器申请与需要通信的一方交互的会话密钥。接收到这个密钥后，就可以建立与对方用户
在OSI参考模型中，实现端到端的应答、分组排序和流量控制功能的协议层是(22)。
下一代IP协议IPv6的基本报头包含(203)个字节，并包含多个可扩展报头。基本报头中的(204)字段指明了一个特定的源站向一个特定目标站发送的分组序列。一个数据流由(205)命名。在IPv6中，地址被扩充为128位。按照IPv6的地址表示方法，以下地址中

随机试题

女性，42岁。颈前结块肿大，弥漫对称，不疼痛。胸闷、咳嗽，吞咽困难，苔薄腻，脉弦。中医治疗可选用
A．头晕目眩，面白无华，爪甲不荣，视物模糊B．头晕眼花，两目干涩，面部烘热或颧红C．头晕胀痛，痛势若劈，面红目赤，急躁易怒D．眩晕耳鸣，头目胀痛，面红目赤，腰膝酸软E．胁肋灼热胀痛，厌食腹胀，口苦，身目发黄
(2010年)图5-41所示悬臂梁自由端承受集中力偶Me，若梁的长度减少一半，梁的最大挠度是原来的()。
某从事会计教学的王老师在2006年度月工资为1660元，同年7月份校外讲课取得报酬3000元，在教学之外，王老师还在一家公司兼职担任会计工作，月工资1000元。根据以上资料回答下列问题：
下列处分不属于银行内部纪律处分的是()。
甲公司是非居民企业，在中国境内未设立机构、场所。2020年初为境内居民企业提供商标使用权，合同约定期限3年，根据合同境内企业每年需在3月1日前支付商标使用费400万元。甲公司2020年度在中国境内应缴纳企业所得税税额为()万元。
真理体现了主观与客观，认识与实践的统一。()
传统的心理物理法有哪些?简述这些方法并对它们进行比较。
下列关于综合布线部件的描述中，正确的是
Whatdoestheword"ruled"inparagraphonemean?Ifthesuspectistoopoortopayalawyer,______.

最新回复(0)

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

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

软考中级

两个人利用Netphone通话时，对语言格式的解释是由(19)完成的。

配置WWW服务器是UNIX操作系统平台的重要工作之一，而Apache是目前应用最为广泛的Web服务器产品之一，(59)是Apache的主要配置文件。URL根目录与服务器本地目录之间的映射关系是通过指令(60)设定；指令ServerAdmin的作用

TheBorderGatewayProtocol(BGP)isaninterautonomoussystem【S1】protoco1．TheprimaryfunctionofaBGPspeakingsystemistoexc

在进行消息认证时，经常利用安全单向散列函数产生消息摘要。安全单向散列函数不需要具有(57)特性。

在计算机系统中采用总线结构，便于实现系统的积木化构造，同时可以__________。(2011年上半年试题)

在OSI参考模型中，实现端到端的应答、分组排序和流量控制功能的协议层是(22)。

女性，42岁。颈前结块肿大，弥漫对称，不疼痛。胸闷、咳嗽，吞咽困难，苔薄腻，脉弦。中医治疗可选用

A．头晕目眩，面白无华，爪甲不荣，视物模糊B．头晕眼花，两目干涩，面部烘热或颧红C．头晕胀痛，痛势若劈，面红目赤，急躁易怒D．眩晕耳鸣，头目胀痛，面红目赤，腰膝酸软E．胁肋灼热胀痛，厌食腹胀，口苦，身目发黄

(2010年)图5-41所示悬臂梁自由端承受集中力偶Me，若梁的长度减少一半，梁的最大挠度是原来的()。

某从事会计教学的王老师在2006年度月工资为1660元，同年7月份校外讲课取得报酬3000元，在教学之外，王老师还在一家公司兼职担任会计工作，月工资1000元。根据以上资料回答下列问题：

下列处分不属于银行内部纪律处分的是()。

真理体现了主观与客观，认识与实践的统一。()

传统的心理物理法有哪些?简述这些方法并对它们进行比较。

下列关于综合布线部件的描述中，正确的是

Whatdoestheword"ruled"inparagraphonemean?Ifthesuspectistoopoortopayalawyer,______.