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

admin2019-07-12 28

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

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

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

软考中级

相关试题推荐

路由器Console端口默认的数据速率为(58)。
在进行DNS查询时，首先向()进行域名查询，以获取对应的IP地址。
在Linux系统中，命令__________用于管理各项软件包。(2011年上半年试题)
阅读下列说明和数据流图，回答问题1至问题3。说明某图书管理系统的主要功能是图书管理和信息查询。对于初次借书的读者，系统自动生成读者号，并与读者基本信息(姓名、单位、地址等)一起写入读者文件。系统的图书管理功能分为四个方面：购入新书、读者借
请用120字以内文字，从业务的继承性、升级成本(时间、工作量)和扩展性三个方面简要说明开发人员所提方案的优点。服务注册中心、服务提供者和服务请求者之间的交互和操作构成了WebService的体系结构，如下图所示。请用180字以内文字，说明这三者的主要
根据以上说明设计的实体联系图如下图所示，请指出读者与图书、书目与读者、书目与图书之间的联系类型。请指出问题2中给出的读者、书目关系模式的主键，以及图书、借还记录和预约登记关系模式的主键和外键。
阅读以下说明和C语言函数，应填入(n)处。【说明】在一个分布网络中，资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中，资源会有损耗。例如，天然气的气压会减少，电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗
阅读以下说明和图，填补流程图中的空缺。【说明】在一条农村公路的一边稀疏地分布着房子，其分布如图10-5所示。某电信公司需要在某些位置放置蜂窝电话基站，由于基站的覆盖范围是6公里，因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化
在关系代数运算中，关系S、SP和R如下表所示。若先(33)，则可以从S和SP获得R。其对应的关系表达式为(34)。如下的SQL语句可以查询销售总量大于1000的部门名。Select部门名FromSWhere部门号in(Selec

随机试题

下列关于通气／血流比值的描述，哪一项是错误的()
城市房屋拆迁当事人对拆迁估价报告有异议的可以()。[2008年考题]
[2011年，第60题]已知铆钉的许可切应力为[τ]，许可挤压应力为[σbs]，钢板的厚度为δ，则图5．3-8示铆钉直径d与钢板厚度δ的关系是()。
下列各项中，构成企业所有者权益总额的有()。
下列关于行业风险分析框架中成本结构的说法，正确的是()。
作为中间交易的交易业务，是指银行为满足客户保值或自身Jx【险管理等方面的需求，利用各种金融工具进行的资金交易活动，主要包括外汇交易业务和金融衍生品交易业务。()
只有企业在职工劳动合同到期之前解除与职工的劳动关系的情况下，职工才可以享受辞退福利。()
下面是某求助者的EPQ和SAS测验结果：SAS总粗分：65下列关于SAS说法错误的有()。
【《德里协定》】
A、Thenumberofgraduatesisincreasingeachyear.B、Technologyandworkplacearechangingfaster.C、Therearemorevacantjobs

最新回复(0)

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

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

软考中级

路由器Console端口默认的数据速率为(58)。

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

在Linux系统中，命令__________用于管理各项软件包。(2011年上半年试题)

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

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

下列关于通气／血流比值的描述，哪一项是错误的()

城市房屋拆迁当事人对拆迁估价报告有异议的可以()。[2008年考题]

[2011年，第60题]已知铆钉的许可切应力为[τ]，许可挤压应力为[σbs]，钢板的厚度为δ，则图5．3-8示铆钉直径d与钢板厚度δ的关系是()。

下列各项中，构成企业所有者权益总额的有()。

下列关于行业风险分析框架中成本结构的说法，正确的是()。

作为中间交易的交易业务，是指银行为满足客户保值或自身Jx【险管理等方面的需求，利用各种金融工具进行的资金交易活动，主要包括外汇交易业务和金融衍生品交易业务。()

只有企业在职工劳动合同到期之前解除与职工的劳动关系的情况下，职工才可以享受辞退福利。()

下面是某求助者的EPQ和SAS测验结果：SAS总粗分：65下列关于SAS说法错误的有()。

【《德里协定》】

A、Thenumberofgraduatesisincreasingeachyear.B、Technologyandworkplacearechangingfaster.C、Therearemorevacantjobs

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