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

admin2010-12-17 28

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

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

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

软考中级

相关试题推荐

从介质访问控制方法的角度来对局域网进行分类，它们有(31)。
图1是曼彻斯特编码，它表示的数据可能为(26)，这种编码适用的网络是(27)。为了在广域网上高速传输数字信号，一般编码方法是(28)，其编码效率为(29)。设某编码体制的编码方法为：输入数据am(m＝1,2,…)，发送时，首先计算bm＝(am+bm-1)M
指令的执行过程包括(3)、分析指令、执行指令。
FDDI的基本编码方法是(30)，在此基础上采用(31)编码以获得足够多的同步信息，这样使编码效率提高到(32)。为了消除环网中的时钟偏移，FDDI使用了(33)方案，并规定进入站点缓冲器的数据时钟由输入信号的时钟确定，缓冲器的输出时钟信号由(34)确定。
配置WWW服务器是UNIX操作系统平台的重要工作之一，而Apache是目前应用最为广泛的Web服务器产品之一，(59)是Apache的主要配置文件。URL根目录与服务器本地目录之间的映射关系是通过指令(60)设定；指令ServerAdmin的作用
设系统中有R类资源m个，现有n个进程互斥使用。若每个进程对R资源的最大需求为w，那么当m、n、w取下表的值时，对于下表中的a～e五种情况，()两种情况可能会发生死锁。对于这两种情况，若将()，则不会发生死锁。
某项目主要由A～I任务构成，其计划图(如下图所示)展示了各任务之间的前后关系以及每个任务的工期(单位：天)，该项目的关键路径是()。在不延误项目总工期的情况下，任务A最多可以推迟开始的时间是()天。
题1：引入多道程序设计技术的目的是(53)。题2：某节点。(路由器)存放的路由信息见表1。表1路由信息则该网络使用的路由算法最可能是(54)。节点A根据当前的路由信息计算出的到节点D的路由可能为(55)。将路由信息发送到其他节点所采用的
假设如图1-5所示的网络拓扑结构中，路由器A至路由器F都运行链路状态路由算法。网络运行300秒后A到目的地C的最小路径成本是(33)。
在一个带宽为3KHz、没有噪声的信道，传输二进制信号能够达到的极限数据数率为(14)。一个带宽为3KHz、信噪比为30dB的信道，能够达到的极限数据传输率为(15)。上述结果表明，(16)。根据奈奎斯特第十定理，为了保证传输质量，达到3Kb/s的数

随机试题

A．突触前膜B．突触后膜C．突触前成分的胞质D．突触后成分的胞质神经递质受体所在部位()
男，50岁，肝炎病史20年，肝区持续性疼痛3个月，伴乏力，消瘦、食欲减退，恶心，低热，黄疸。查体：肋下腋前线可触及肿大之肝脏，质硬。对诊断有确诊意义的是
骨髓检查中，通常用油镜来观察的是
此时对母儿的影响错误的是妊娠期的处理不正确的是
A．诱导B细胞活化，但无需Th细胞辅助B．产生协同刺激信号，使B细胞活化C．为B细胞活化的初级信号传导分子D．产生增强的免疫应答，分泌高亲和力抗体E．产生活化第一信号，需Th细胞辅助，诱导B细胞活化
男，37岁，右小腿被汽车压伤3天就诊。查体：右小腿严重肿胀畸形，足趾苍白、发凉，足背动脉搏动消失，被动活动足趾剧痛。X线片示右胫腓骨严重粉碎性骨折。产生上述并发症的原因是()
下列关于计算机的叙述中，不正确的是（）。
主张“教育即生活”，强调教法与教材的统一，注重“从做中学”的教育家是()
HowlongdoestheChristmasholidaylast?Wecanknowfromthdpassagethat______likeChristmasbest.
WillAIRobotsTurnHumansintoPets?A)InaroomattheUnitedNationsoverlookingNewYork’sEastRiver,atatablea

最新回复(0)

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

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

软考中级

从介质访问控制方法的角度来对局域网进行分类，它们有(31)。

指令的执行过程包括(3)、分析指令、执行指令。

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

设系统中有R类资源m个，现有n个进程互斥使用。若每个进程对R资源的最大需求为w，那么当m、n、w取下表的值时，对于下表中的a～e五种情况，()两种情况可能会发生死锁。对于这两种情况，若将()，则不会发生死锁。

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

假设如图1-5所示的网络拓扑结构中，路由器A至路由器F都运行链路状态路由算法。网络运行300秒后A到目的地C的最小路径成本是(33)。

A．突触前膜B．突触后膜C．突触前成分的胞质D．突触后成分的胞质神经递质受体所在部位()

男，50岁，肝炎病史20年，肝区持续性疼痛3个月，伴乏力，消瘦、食欲减退，恶心，低热，黄疸。查体：肋下腋前线可触及肿大之肝脏，质硬。对诊断有确诊意义的是

骨髓检查中，通常用油镜来观察的是

此时对母儿的影响错误的是妊娠期的处理不正确的是

A．诱导B细胞活化，但无需Th细胞辅助B．产生协同刺激信号，使B细胞活化C．为B细胞活化的初级信号传导分子D．产生增强的免疫应答，分泌高亲和力抗体E．产生活化第一信号，需Th细胞辅助，诱导B细胞活化

男，37岁，右小腿被汽车压伤3天就诊。查体：右小腿严重肿胀畸形，足趾苍白、发凉，足背动脉搏动消失，被动活动足趾剧痛。X线片示右胫腓骨严重粉碎性骨折。产生上述并发症的原因是()

下列关于计算机的叙述中，不正确的是（）。

主张“教育即生活”，强调教法与教材的统一，注重“从做中学”的教育家是()

HowlongdoestheChristmasholidaylast?Wecanknowfromthdpassagethat______likeChristmasbest.

WillAIRobotsTurnHumansintoPets?A)InaroomattheUnitedNationsoverlookingNewYork’sEastRiver,atatablea