首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某算法的时间代价递推关系为T(n)=2T(n/2)+n,T(1)=1,则该算法的时间复杂度为______。
某算法的时间代价递推关系为T(n)=2T(n/2)+n,T(1)=1,则该算法的时间复杂度为______。
admin
2010-12-17
34
问题
某算法的时间代价递推关系为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
软件设计师上午基础知识考试
软考中级
相关试题推荐
安全的威胁可分为两大类,即主动攻击和被动攻击。通过截取以前的合法记录稍后重新加入一个连接,叫做重放攻击。为防止这种情况,可以采用的办法是(50)。一个计算机系统被认为是可信任的,主要从其受保护的程度而言的,WindowsNT4.0以上版本目前具有的安全等级
Networkscanbeinterconnectedbydifferentdevices.Inthephysicallayer,networkscanbeconnectedby(66)orHubs,whichjustmo
指令的执行过程包括(3)、分析指令、执行指令。
DES加密算法采用的密码技术是(61),它采用(62)bit密钥对传输的数据进行加密,著名的网络安全系统Kerberos采用的是(63)加密技术。公钥密码是(64),常用的公钥加密算法有(65),它可以实现加密和数字签名。
基于Web的客户/服务器应用模式飞速发展的原因是(57)。
CSMA/CD在CSMA的基础上增加了冲突检测功能。网络中的某个发送站点一旦检测到冲突,它就立即停止发送,并发送一个冲突码,其他站点都会(39)。如果站点发送时间为1,任意两个站之间的传播延迟为t,若能正常检测到冲突,对于基带总线网络,t的值应为(40);
在IEEE802.11标准中使用了扩频通信技术,下面选项中有关扩频通信技术说法正确的是()。
在图8-7所示的网络拓扑结构的分支机构路由器上,正确的拨号映射配置语句是(53)。
FrameRelayissimplifiedformof(71),similarinprincipleto(72),inwhichsynchronous,framesofdataareroutedtodifferent
MIB对象标识符分级树根未命名,但是有3个直接后裔,分别由ISO、(1)及(2)进行管理。分级树中关于MIB-Ⅱ节点下包括10个功能组,共171个对象。在这些功能组中是一个联系各种接口的特殊节点,与接口组相配合,提供与子网类型有关的专用信息的功能组是(3)
随机试题
A.脐部圆形包块,加腹压后包块突出,平卧时包块消失B.卵黄管的脐端未闭,遗留较短的盲管C.脐带周围发生缺损,腹腔内脏脱出体外D.出生后见胃肠突出于腹壁外,脐和脐带正常,腹壁裂孔在脐的右侧并为纵向E.卵黄管的脐端有残留的黏膜形成息肉样红色突起,少量液
A、祛暑利湿,补气生津B、祛暑除湿,和胃消食C、祛暑解表,清热生津D、解表化湿,理气和中E、清热解毒,利湿化浊六合定中丸的功效()。
第二类精神药品处方印刷用纸为
抢救青霉素过敏性休克的首选药物是
EVA、PE类聚合物改性沥青混合料的废弃温度为()。
某公司为获得一项工程合同,拟向工程发包方的有关人员支付好处费8万元,公司市场部持公司的批示到财务部领取该笔款项。财务部经理谢某认为该项支出不符合有关规定,但考虑到公司主要领导已作了批示,遂同意拨付了款项。对谢某做法的下列认定中正确的是()。
我国对资本主义工商业进行社会主义改造的政策是和平赎买。()
小刚在一次演讲比赛中有五名裁判给他打分,除去最低分外,他的平均成绩是96分;加上最低分,它的平均成绩下降了3分。问其中打的最低分是多少?()
设f(x)连续,其中V={(x,y,z)|x2+y2≤t2,0≤z≤h}(t>0),求其中,[x]表示不超过x的最大整数.
WhatcanbecitedtoshowMr.Eliasson’sunderstandingoftotal-immersionart?
最新回复
(
0
)