首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某算法的时间代价递推关系为T(n)=2T(n/2)+n,T(1)=1,则该算法的时间复杂度为______。
某算法的时间代价递推关系为T(n)=2T(n/2)+n,T(1)=1,则该算法的时间复杂度为______。
admin
2010-12-17
31
问题
某算法的时间代价递推关系为T(n)=2T(n/2)+n,T(1)=1,则该算法的时间复杂度为______。
选项
A、O(n)
B、
C、O(n
2
)
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
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
ODQDB同时支持(33)两种服务。DQDB子网的双总线结构由(34)总线以及接在这两条总线上的大量的节点组成。DQDB网络为双总线提供了(35)访问控制方式,其中能够提供非等时服务是(36),它用于(37)业务。
在OSI参考模型中,物理层的功能是(25)等。实体在一次交互作用中传送的信息单位称为(26),它包括(27)两部分。上下邻层实体之间的接口称为服务访问点(SAP),网络层的服务访问点也称为(28),通常分为(29)两部分。
网络管理系统的实现方式有(10)。
HFC应用(35)传输技术,综合接入多种业务。HFC的用户端,从PC机接收的以太帧被封装在时隙中,经过(36)调制后,通过HFC网络的上行数据通路传送给CMTS。
设计算机系统由CPU、存储器、I/O3部分组成,其可靠性分别为0.95、0.91和0.98,则计算机系统的可靠性为(12)。
自动专用IP地址(AutomaticPrivateIPAddress,APIPA)是IANA(InternetAssignedNumbersAuthority)保留的一个地址块,它的地址范围是()。当()时,使用APIPA。
关于自治系统(Autonomous System,AS),以下说法错误的是(26)。
计算机在进行浮点数的相加(减)运算之前先进行对阶操作,若x的阶码大于y的阶码,则应将(2)。
Kerberos要求用户使用(1)作为自己的标识,而客户端与KDC服务器之间的交互则使用(2)。当用户需要和其他用户通信时,需要从服务器端获得(3),然后再用其向KDC服务器申请与需要通信的一方交互的会话密钥。接收到这个密钥后,就可以建立与对方用户
在OSI参考模型中,实现端到端的应答、分组排序和流量控制功能的协议层是(22)。
随机试题
投资组合管理的目的为()。Ⅰ.分散风险Ⅱ.提高效率Ⅲ.投资回报率实现最大化Ⅳ.汇聚资产
仅由树木构成的防护林带,风可以从林冠的上方和下方通过,这种林带的结构是()
张某与甲公司签订商品房买卖合同,根据合同约定,张某支付30%的购房款,剩余部分通过银行按揭贷款方式支付,收房日期为8月8日。合同签订后,张某支付了房款,办理了贷款。及至收房日期,由于对房屋质量、面积、费用等问题发生争执,张某拒绝收房。8月10日,甲公司催告
停车45辆的地上汽车库建筑,木材可用下列哪个部位?[2007年第057题]
消防装备中的()是消防员灭火救援的根本。
王某于2002年3月,购买一辆捷达牌轿车,支付全部价款合计为10.2万元,另支付代收临时牌照费200元,购买工具件及零配件共计3100元,其应纳车辆购置税为( )元。
教师要做好学生的心理辅导工作,应该()。
下面二叉树中序遍历结果是()。
Attheapartment,wefoundanunshaven,grey-hairedmansittinginashabbyrecliner.Hehadan【B1】______grinonhisface.His
A、Anannualcyclingevent.B、MajorCanadianbicycleraces.C、Thecontributionofcyclingtohealth.D、Howtoincreaseone’sspee
最新回复
(
0
)