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

admin2019-07-12 19

问题某个算法的时间复杂度递归式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

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

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

软考中级

相关试题推荐

子网掩码的作用是__________。
在进行DNS查询时，首先向()进行域名查询，以获取对应的IP地址。
假设某分时系统采用简单时间片轮转发，当系统中的用户数为n，时间片为q时，系统对每个用户的响应时间T为____________。
下图是一个软件项目的活动图，其中顶点表示项目里程碑，联结顶点的边表示包含的活动，则里程碑(1)在关键路径上，活动FG的松弛时间为(2)。(2)
IEEE802．11标准定义的PeertoPeer网络是__________。(20lO年上半年试题)
李某在《电脑与编程》杂志上看到张某发表的一组程序，颇为欣赏，就复印了100份作为程序设计辅导教材发给学生。李某又将这组程序逐段加以评析，写成评论文章后投到《电脑编程技巧》杂志上发表。李某的行为__________。(2008年下半年试题)
网络拓扑设计对网络的影响主要表现在__________。(2013年上半年试题)①网络性能②系统可靠性③出口带宽④网络协议
阅读下列说明和算法，回答问题1和问题2，将解答填入答题纸的对应栏内。[说明]算法2-1是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号，则给出相应的提示信息，如下所示：文件提示信息(
阅读下列函数说明和c代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】函数intToplogical(LindedWDipaphG)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE-网
阅读下列说明和E-R图，回答问题1至问题3，将解答填入答题纸的对应栏内。说明某网上订书系统的E-R图(已消除了不必要的冗余)如图2-1所示(图中没有标出主码)。图中实体的说明如表2-1所示，相关属性说明如表2-2所示。一个顾客可以在同一天填写

随机试题

腹痛较剧，痛如针刺，痛处固定，舌质紫暗，脉细涩者，治疗主方为
离合器从动盘因磨损变薄，会造成离合器踏板自由行程()。
A．粉碎性骨折B．病理性骨折C．疲劳性骨折D．压缩性骨折E．撕脱性骨折肌肉拉力可引起
A、联合卡环B、对半卡环C、圈形卡环D、回力卡环E、三臂卡环用于最后孤立磨牙、且向近中舌侧或近中颊侧倾斜牙上的卡环是
检验检疫的旧机电产品包括国家机电办管理的机电产品；不包括其他不属于机电办管理的机电产品。
按照土地增值税法的规定，纳税人提供的扣除项目金融不实的，在计算土地增值税时，应当按照()扣除。
国民生产总值和国内生产总值的关系是()。
截至2019年12月31日，中国共产党党员总数为9191.6万名，同比增长1.46%。在党员的性别、民族和学历上，女党员2559.9万名，少数民族党员680.3万名，大专及以上学历党员4661.5万名。在党员的入党时间上，新中国成立前入党的17.4万名，新
一份报告显示，截至3月份的一年内，中国内地买家成为购买美国房产的第二大外国买家群体，交易额达90亿美元，仅次于加拿大。这比上一年73亿美元的交易额高出23％，比前年48亿美元的交易额高出88％。有人据此认为，中国有越来越多的富人正在把财产转移到境外。以下哪
公钥加密体制中，没有公开的是

最新回复(0)

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

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

软考中级

子网掩码的作用是__________。

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

假设某分时系统采用简单时间片轮转发，当系统中的用户数为n，时间片为q时，系统对每个用户的响应时间T为____________。

下图是一个软件项目的活动图，其中顶点表示项目里程碑，联结顶点的边表示包含的活动，则里程碑(1)在关键路径上，活动FG的松弛时间为(2)。(2)

IEEE802．11标准定义的PeertoPeer网络是__________。(20lO年上半年试题)

网络拓扑设计对网络的影响主要表现在__________。(2013年上半年试题)①网络性能②系统可靠性③出口带宽④网络协议

阅读下列函数说明和c代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】函数intToplogical(LindedWDipaphG)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE-网

腹痛较剧，痛如针刺，痛处固定，舌质紫暗，脉细涩者，治疗主方为

离合器从动盘因磨损变薄，会造成离合器踏板自由行程()。

A．粉碎性骨折B．病理性骨折C．疲劳性骨折D．压缩性骨折E．撕脱性骨折肌肉拉力可引起

A、联合卡环B、对半卡环C、圈形卡环D、回力卡环E、三臂卡环用于最后孤立磨牙、且向近中舌侧或近中颊侧倾斜牙上的卡环是

检验检疫的旧机电产品包括国家机电办管理的机电产品；不包括其他不属于机电办管理的机电产品。

按照土地增值税法的规定，纳税人提供的扣除项目金融不实的，在计算土地增值税时，应当按照()扣除。

国民生产总值和国内生产总值的关系是()。

公钥加密体制中，没有公开的是

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