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

admin2019-07-12 41

问题某个算法的时间复杂度递归式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://www.kaotiyun.com/show/G9CZ777K

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

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

软考中级

相关试题推荐

在Internet上有许多协议，下面的选项中能正确表示协议层次关系的是(23)。
使用白盒测试方法时，确定测试用例应根据__________和指定的覆盖标准。(2010年上半年试题)
李某在《电脑与编程》杂志上看到张某发表的一组程序，颇为欣赏，就复印了一百份作为程序设计辅导材料发给了学生。李某又将这组程序逐段加以评析，写成评论文章后投到《电脑编程技巧》杂志上发表。李某的行为(10)。
下图是一个软件项目的活动图，其中顶点表示项目里程碑，联结顶点的边表示包含的活动，则里程碑(1)在关键路径上，活动FG的松弛时间为(2)。(1)
根据E-R图中给出的词汇，按照“关系模式名(属性，属性，…)”的格式，将此E-R图转换为4个关系模式，并指出每个关系模式中的主码和外码，其中模式名根据需要取实体名或联系名。创建Customers表时，cid使用INTEGER数据类型，cnarne使用
阅读下列说明和数据流图，回答问题1至问题3。说明某图书管理系统的主要功能是图书管理和信息查询。对于初次借书的读者，系统自动生成读者号，并与读者基本信息(姓名、单位、地址等)一起写入读者文件。系统的图书管理功能分为四个方面：购入新书、读者借
根据以上说明设计的实体联系图如下图所示，请指出读者与图书、书目与读者、书目与图书之间的联系类型。请指出问题2中给出的读者、书目关系模式的主键，以及图书、借还记录和预约登记关系模式的主键和外键。
阅读以下说明和C语言函数，应填入(n)处。【说明】在一个分布网络中，资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中，资源会有损耗。例如，天然气的气压会减少，电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗

随机试题

A．K+B．Na+C．Ca2+D．Cl-与神经纤维动作电位复极相有关的离子主要是
某承包人一直拖欠材料商的货款，材料商多次索要未果，便将此债权转让给了该工程的建设单位。工程结算时，建设单位提出要将此债权与需要支付的部分工程款抵消，施工单位以自己不知道此事为由不同意。针对本案下列表述中正确的是()。
证券的代销、包销期限最长不得超过()
民间非营利组织净资产按照是否受到限制，分为()。
安排每周锻炼计划时，运动负荷应大中小结合，大运动负荷每周()次为宜。
Peoplewithhearingimpairmentsdon’twanttobetreatedasthoughtheyaresomehowlessvaluableinthecommunity.Isitnormal
下列关于函数的描述中，错误的是()。
下列诸因素中，对计算机的正常工作影响最小的是
Whenwewantto【C1】______otherpeoplewhatwethink,wecandoitnotonlywiththehelpofwords,butalsoinmany【C2】______way
Researchersfoundfamilyinfluenceddelinquency.Attachmentandinvolvementwereboth【S1】______relatedtodelinquency.Children

最新回复(0)

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

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

软考中级

在Internet上有许多协议，下面的选项中能正确表示协议层次关系的是(23)。

使用白盒测试方法时，确定测试用例应根据__________和指定的覆盖标准。(2010年上半年试题)

李某在《电脑与编程》杂志上看到张某发表的一组程序，颇为欣赏，就复印了一百份作为程序设计辅导材料发给了学生。李某又将这组程序逐段加以评析，写成评论文章后投到《电脑编程技巧》杂志上发表。李某的行为(10)。

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

根据以上说明设计的实体联系图如下图所示，请指出读者与图书、书目与读者、书目与图书之间的联系类型。请指出问题2中给出的读者、书目关系模式的主键，以及图书、借还记录和预约登记关系模式的主键和外键。

A．K+B．Na+C．Ca2+D．Cl-与神经纤维动作电位复极相有关的离子主要是

证券的代销、包销期限最长不得超过()

民间非营利组织净资产按照是否受到限制，分为()。

安排每周锻炼计划时，运动负荷应大中小结合，大运动负荷每周()次为宜。

Peoplewithhearingimpairmentsdon’twanttobetreatedasthoughtheyaresomehowlessvaluableinthecommunity.Isitnormal

下列关于函数的描述中，错误的是()。

下列诸因素中，对计算机的正常工作影响最小的是

Whenwewantto【C1】______otherpeoplewhatwethink,wecandoitnotonlywiththehelpofwords,butalsoinmany【C2】______way

Researchersfoundfamilyinfluenceddelinquency.Attachmentandinvolvementwereboth【S1】______relatedtodelinquency.Children

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

Whenwewantto【C1】otherpeoplewhatwethink,wecandoitnotonlywiththehelpofwords,butalsoinmany【C2】way