某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为_，若问题的规模增加了16倍，则运行时间增加 _倍。 (63)

admin2019-07-12 20

问题某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为_______，若问题的规模增加了16倍，则运行时间增加 _______倍。
(63)

选项 A、16
B、64
C、256
D、1024

答案C

解析对于递归式，假设T(1)=1，则：
T(n)=T(n一1)+n
=T(n一2)+n一1+n
=T(n一3)+n一2+n一1+n
=…
=1+2+…+n一1+n
=n(n+1)／2
可见，时间复杂度为O(n²)。若问题的规模增加了16倍，则运行时间增加了16²=256倍。

转载请注明原文地址:https://kaotiyun.com/show/G9CZ777K

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

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

软考中级

相关试题推荐

~SSL协议使用的默认端El是()。
在进行DNS查询时，首先向()进行域名查询，以获取对应的IP地址。
路由器命令“Router(config-subif)#encapsulationdotlq1”的作用是______。
IPv6地址以16进制数表示，每4个16进制数为一组，组之间用冒号分隔，下面的　IPv6地址ADBF：0000：FEEA：0000：0000：00EA：00AC：DEED的简化写法是(20)。
计算机指令一股包括操作码和地址码两部分，为分析执行一条指令，其______。
工作站A的IP地址是202，117．17．24/28，而工作站B的IP地址是202．117．17．100/28，当两个工作站直接相连时不能通信，怎样修改地址才能使得这两个工作站可以互相通信？(56)。
李某在《电脑与编程》杂志上看到张某发表的一组程序，颇为欣赏，就复印了100份作为程序设计辅导教材发给学生。李某又将这组程序逐段加以评析，写成评论文章后投到《电脑编程技巧》杂志上发表。李某的行为__________。(2008年下半年试题)
以下关于Cache的叙述中，正确的是()。
阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】在并发系统设计中，通过对信号量S的P、V操作实现进程的同步与互斥控制。P(S):S:=S-1，若S≥0，则执行P操作的进程继续执行：若S＜0，则置该进程为阻塞状态，
在关系代数运算中，关系S、SP和R如下表所示。若先(33)，则可以从S和SP获得R。其对应的关系表达式为(34)。如下的SQL语句可以查询销售总量大于1000的部门名。Select部门名FromSWhere部门号in(Selec

随机试题

应急照明包括哪些照明?[2010年第110题]
患者男性，20岁。于4天前突然寒战发热，2天后，体温高峰达39℃，查体可见颜面潮红，结膜充血，腹股沟可见焦痂形成，腹股沟淋巴结肿大，变形杆菌OXk凝集的反应1:320。对该患者最有效的药物是A．环丙沙星B．氯霉素C．复方新诺明D．庆大霉素E
高眼压症在测量眼压时充分注意测量误差，眼压测量时的主要误差因素（）
关于生殖道病毒感染，下列哪项是错误的
中国大型机械制造公司出口数台大型挖掘机至法国某建筑设备租赁公司，约定主要交易条件为FOB汕头，此批挖掘机根据双方约定货装甲板，装船过程中因遭遇恶劣天气，导致两台已经装到甲板上的挖掘机脱离绳索跌落大海，经采取紧急措施，最终其余挖掘机被顺利装船并运至目的地交给
如果一个广告看过0次的是3人，看过1次的是3人，看过2次的是5人，看过3次的是2人，看过4次的是2人。那么实例中的毛评点是()次。
某大学新生军训长途行军时，脚磨起泡，泡里的淡黄色液体是()。
为调动农民生产积极性，从2004年起，我国全面放开粮食收购市场，为保护粮食生产能力，同年，我国还配套出台的“三农”政策是()。
有人说，“志不强者，智不达”。对此，请你谈谈信念和信仰的重要性。
Malnutritionduringweaningage—whenbreastmilkisbeingreplacedbysemi-solidfoods—ishighlyprevalentinchildrenofpoorh

最新回复(0)

某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为_______，若问题的规模增加了16倍，则运行时间增加 _______倍。 (63)

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

软考中级

~SSL协议使用的默认端El是()。

在进行DNS查询时，首先向()进行域名查询，以获取对应的IP地址。

路由器命令“Router(config-subif)#encapsulationdotlq1”的作用是______。

IPv6地址以16进制数表示，每4个16进制数为一组，组之间用冒号分隔，下面的 IPv6地址ADBF：0000：FEEA：0000：0000：00EA：00AC：DEED的简化写法是(20)。

计算机指令一股包括操作码和地址码两部分，为分析执行一条指令，其______。

工作站A的IP地址是202，117．17．24/28，而工作站B的IP地址是202．117．17．100/28，当两个工作站直接相连时不能通信，怎样修改地址才能使得这两个工作站可以互相通信？(56)。

以下关于Cache的叙述中，正确的是()。

在关系代数运算中，关系S、SP和R如下表所示。若先(33)，则可以从S和SP获得R。其对应的关系表达式为(34)。如下的SQL语句可以查询销售总量大于1000的部门名。Select部门名FromSWhere部门号in(Selec

应急照明包括哪些照明?[2010年第110题]

高眼压症在测量眼压时充分注意测量误差，眼压测量时的主要误差因素（）

关于生殖道病毒感染，下列哪项是错误的

如果一个广告看过0次的是3人，看过1次的是3人，看过2次的是5人，看过3次的是2人，看过4次的是2人。那么实例中的毛评点是()次。

某大学新生军训长途行军时，脚磨起泡，泡里的淡黄色液体是()。

为调动农民生产积极性，从2004年起，我国全面放开粮食收购市场，为保护粮食生产能力，同年，我国还配套出台的“三农”政策是()。

有人说，“志不强者，智不达”。对此，请你谈谈信念和信仰的重要性。

Malnutritionduringweaningage—whenbreastmilkisbeingreplacedbysemi-solidfoods—ishighlyprevalentinchildrenofpoorh

某个算法的时间复杂度递归式T(n)=T(n-1)+n，其中n为问题的规模，则该算法的渐进时间复杂度为_，若问题的规模增加了16倍，则运行时间增加 _倍。 (63)

IPv6地址以16进制数表示，每4个16进制数为一组，组之间用冒号分隔，下面的　IPv6地址ADBF：0000：FEEA：0000：0000：00EA：00AC：DEED的简化写法是(20)。