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

admin2019-07-12 55

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

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

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

软考中级

相关试题推荐

使用白盒测试方法时，确定测试用例应根据__________和指定的覆盖标准。(2010年上半年试题)
网络配置如下图所示，为路由器Routerl配置访问网络1和网络2的命令是(1)。路由配置完成后，在Routerl的(2)可以查看路由，查看路由采用的命令是(3)。(3)
以下给出的地址中，不属于网络222.15.64.0/20的主机地址是(56)。
路由器命令“Router(config-subif)#encapsulationdotlq1”的作用是______。
图1-1是一个软件项目的活动图，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的值表示完成活动所需要的时间，则关键路径长度为______。
根据上述说明，请给出(1)“职员”关系模式的主键和外键。(2)“部门”关系模式的主键和外键。对于表2-1、表2-2所示的“职员”和“部门”关系，请指出下列各行是否可以插入“职员”关系，为什么?
请采用说明中的词汇，给出数据确认处理所需的数据流在第1层图中的全部可选起点(第0层图和第1层图中均未给出)。打印分户账清单时，必须以下列哪一组数据作为关键字进行排序，才能满足需求?请从下面选项中选择。①储蓄所②账号⑧开户日
阅读以下说明和C代码，将应填入(n)处的字句写在的对应栏内。【说明】在一个简化的绘图程序中，支持的图形种类有点(point)和圆(circle)，在设计过程中采用面向对象思想，认为所有的点和圆都是一种图形(shape)，并定义了类型shape
多媒体技术的关键在于解决动态图像和声音的存储与传输问题。若不经压缩，以　VGA640×480点阵存储一幅256色的彩色图像大约需(56)MB存储空间，以9600bit/s的速度传输这幅图像大约需(57)秒，按我国电视PAL标准每秒25幅，一张650MB的光
设表达式E=a*(b-c)/(d+e)+f*(g+h)，则E的逆波兰表达式为(40)，E的波兰表达式为(41)。

随机试题

软化切制后暴晒会使鞣质氧化聚合而泛红的药材是
转移定价过程中，当跨国公司要把产品销往高关税国家的分公司时，应该()
对资本主义私有制的改造，马克思和恩格斯曾经设想过暴力没收、和平赎买两种形式，而和平赎买的必要性在于()
不属于臂丛的神经为
患者久病，畏寒喜暖，形寒肢冷，面色咣白，蜷卧神疲，小便清长，下利清谷，偶见小腿浮肿，按之凹陷如泥，舌淡脉迟。其病机是()
下列词语中没有错别字的一组是()。
项目法人一般不得直接指定分包人，项目法人可直接指定分包人的情况有()。
某建设工程合同约定，“工程通过竣工验收后2个月内，结清全部工程款”。2005年10月1日工程通过竣工验收，10月10日承包人提交竣工结算文件，10月20日承包几将工程移交发包人，但发包人一直未付工程余款。2006年5月1日，承包人将发包人起诉至人民法院，要
数据库系统是实现有组织地、动态地存储大量___________数据，支持多用户访问的计算机软件、________和数据资源组成的系统。
学校德育的基本方法就是榜样教育法。()

最新回复(0)

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

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

软考中级

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

网络配置如下图所示，为路由器Routerl配置访问网络1和网络2的命令是(1)。路由配置完成后，在Routerl的(2)可以查看路由，查看路由采用的命令是(3)。(3)

以下给出的地址中，不属于网络222.15.64.0/20的主机地址是(56)。

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

图1-1是一个软件项目的活动图，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的值表示完成活动所需要的时间，则关键路径长度为______。

根据上述说明，请给出(1)“职员”关系模式的主键和外键。(2)“部门”关系模式的主键和外键。对于表2-1、表2-2所示的“职员”和“部门”关系，请指出下列各行是否可以插入“职员”关系，为什么?

设表达式E=a(b-c)/(d+e)+f(g+h)，则E的逆波兰表达式为(40)，E的波兰表达式为(41)。

软化切制后暴晒会使鞣质氧化聚合而泛红的药材是

转移定价过程中，当跨国公司要把产品销往高关税国家的分公司时，应该()

对资本主义私有制的改造，马克思和恩格斯曾经设想过暴力没收、和平赎买两种形式，而和平赎买的必要性在于()

不属于臂丛的神经为

患者久病，畏寒喜暖，形寒肢冷，面色咣白，蜷卧神疲，小便清长，下利清谷，偶见小腿浮肿，按之凹陷如泥，舌淡脉迟。其病机是()

下列词语中没有错别字的一组是()。

项目法人一般不得直接指定分包人，项目法人可直接指定分包人的情况有()。

数据库系统是实现有组织地、动态地存储大量___数据，支持多用户访问的计算机软件、和数据资源组成的系统。

学校德育的基本方法就是榜样教育法。()

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

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

软考中级

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

网络配置如下图所示，为路由器Routerl配置访问网络1和网络2的命令是(1)。路由配置完成后，在Routerl的(2)可以查看路由，查看路由采用的命令是(3)。(3)

以下给出的地址中，不属于网络222.15.64.0/20的主机地址是(56)。

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

图1-1是一个软件项目的活动图，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的值表示完成活动所需要的时间，则关键路径长度为______。

根据上述说明，请给出(1)“职员”关系模式的主键和外键。(2)“部门”关系模式的主键和外键。对于表2-1、表2-2所示的“职员”和“部门”关系，请指出下列各行是否可以插入“职员”关系，为什么?

多媒体技术的关键在于解决动态图像和声音的存储与传输问题。若不经压缩，以 VGA640×480点阵存储一幅256色的彩色图像大约需(56)MB存储空间，以9600bit/s的速度传输这幅图像大约需(57)秒，按我国电视PAL标准每秒25幅，一张650MB的光

设表达式E=a*(b-c)/(d+e)+f*(g+h)，则E的逆波兰表达式为(40)，E的波兰表达式为(41)。

软化切制后暴晒会使鞣质氧化聚合而泛红的药材是

转移定价过程中，当跨国公司要把产品销往高关税国家的分公司时，应该()

对资本主义私有制的改造，马克思和恩格斯曾经设想过暴力没收、和平赎买两种形式，而和平赎买的必要性在于()

不属于臂丛的神经为

患者久病，畏寒喜暖，形寒肢冷，面色咣白，蜷卧神疲，小便清长，下利清谷，偶见小腿浮肿，按之凹陷如泥，舌淡脉迟。其病机是()

下列词语中没有错别字的一组是()。

项目法人一般不得直接指定分包人，项目法人可直接指定分包人的情况有()。

数据库系统是实现有组织地、动态地存储大量___________数据，支持多用户访问的计算机软件、________和数据资源组成的系统。

学校德育的基本方法就是榜样教育法。()

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

设表达式E=a(b-c)/(d+e)+f(g+h)，则E的逆波兰表达式为(40)，E的波兰表达式为(41)。

数据库系统是实现有组织地、动态地存储大量___数据，支持多用户访问的计算机软件、和数据资源组成的系统。