首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某算法的时间代价递推关系为T(n)=2T(n/2)+n,T(1)=1,则该算法的时间复杂度为______。
某算法的时间代价递推关系为T(n)=2T(n/2)+n,T(1)=1,则该算法的时间复杂度为______。
admin
2010-12-17
30
问题
某算法的时间代价递推关系为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
软件设计师上午基础知识考试
软考中级
相关试题推荐
下面给出了一些软件编码的原则,其中错误的是(9)。
原型化(Prototyping)方法是一类动态定义需求的方法,(7)不是原型化方法所具有的特征。与结构化方法相比,原型化方法更需要(8)。衡量原型开发人员能力的重要标准是(9)。
网络配置如下图所示:其中某设备路由表信息如下:C192.168.1.0/24isdirectlyconnected,FastEthemet0/0R192.168.3.0/24[120/1]via192.168.65.2,00:00:
网络配置如下图所示:其中某设备路由表信息如下:C192.168.1.0/24isdirectlyconnected,FastEthemet0/0R192.168.3.0/24[120/1]via192.168.65.2,00:00:
~IPv6协议数据单元由一个固定头部和若干个扩展头部以及上层协议提供的负载组成,其中用于表示松散源路由功能的扩展头是()。如果有多个扩展头部,第一个扩展头部为()。
RlPv2对RIPvl协议有三方面的改进。下面的选项中,RIPv2的特点不包括()。在RIPv2中,可以采用水平分割法来消除路由循环,这种方法是指()。
题1:引入多道程序设计技术的目的是(53)。题2:某节点。(路由器)存放的路由信息见表1。表1路由信息则该网络使用的路由算法最可能是(54)。节点A根据当前的路由信息计算出的到节点D的路由可能为(55)。将路由信息发送到其他节点所采用的
Fast(66)isalsoreferredtoas100BASE-Tor802.3uandisacommunications(67)thatenablescomputersonalocal-areanetworkto
计算机在进行浮点数的相加(减)运算之前先进行对阶操作,若x的阶码大于y的阶码,则应将(2)。
FrameRelayissimplifiedformof(71),similarinprincipleto(72),inwhichsynchronous,framesofdataareroutedtodifferent
随机试题
心的正常自动节律性兴奋的起搏点是()。
下列关于药物主治病证的叙述,错误的是
患者,男,58岁,进行性贫血、消瘦、乏力半年,有时右腹有隐痛,无腹泻。查体:贫血貌,右中腹可触及肿块,肠鸣音活跃。该患者术前准备中最重要的护理措施是
根据《审计法》,下列说法正确的是:()
目标动态控制过程中,( )组成一个连续不断的“循环链”。
铁路土建工程施工质量控制主要包括()四个方面的施工质量控制。
下列叙述中正确的是()。
Theworldisinaself-destructionmode,BythisstatementImeanthatthepeopleoftheworldarebentonmakingthisplanetin
TheInternetmirrorssociety,reflectingourstrengthsandweaknesses.AhealthysocietyandahealthyInternetsharethesamev
A、Familieswithcars.B、Americans’heavydependenceoncars.C、Roadsandhighways.D、TrafficproblemsinAmerica.B理解归纳题。女士认为美国人
最新回复
(
0
)