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

admin2019-07-12 61

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

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

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

软考中级

相关试题推荐

在Linux中，_________命令可将文件以修改时间顺序显示。
某公司有2000台主机，则必须给它分配(1)个C类网络。为了使该公司的网络地址在路由表中只占一行，给它指定的子网掩码必须是(2)。(2)
路由表如下图所示，如果一个分组的目标地址是220．117．5．65,则会被发送给__________端口。(2013年上半年试题)NetworkInterfacenext—hop220．117．I．0／24e0directlyconnecte
VLAN之间的通信通过(18)________________实现。
下图是一个软件项目的活动图，其中顶点表示项目里程碑，联结顶点的边表示包含的活动，则里程碑(1)在关键路径上，活动FG的松弛时间为(2)。(1)
在下图的SNMP配置中，能够响应Manager2的getRequest请求的是()。
[程序]#include＜ioStream.h＞template＜classT＞classArray；template＜classT＞classArrayBody{friend
阅读以下说明和表，回答问题1～问题4。【说明】某公司信息管理系统的需求分析和部分关系模式设计的结果描述如下。1．公司有多个部门，每个部门有一名负责人、一间办公室、一部电话、多名职员，每个职员最多属于一个部门，负责人也是一名公司职员。
识别关联的多重度是面向对象建模过程中的一个重要步骤。根据说明中给出的描述，完成图10-4中的(1)～(6)。请从表10-2中选择方法，完成图10-5中的(7)～(10)。
当图像分辨率为800×600，屏幕分辨率为640×480时，(13)。

随机试题

被视为“近代中国开眼看世界之第一人”是（　　　）
A．3′→5′B．5→3′C．N端→C端D．C端→N端DNA的合成方向是
与糖尿病相关的遗传性综合征包括
男性，患慢性粒细胞白血病3年，经干扰素+羟基脲治疗后脾脏缩小，外周血象正常，但近来不明原因发热，脾再次肿大，血象：Hb80g/L，血小板90×109/L，WBC20×109/L，骨髓中原始粒细胞38%，继续上述治疗无效。下列哪种情况最为可能
生产经营单位应当向从业人员如实告知作业场所和工作岗位存在的（），防范措施以及事故应急措施。
某平面任意力系向O点简化后，得到如图4-13所示的一个主矢F’B和一个主矩Mo，则该力系的最后简化结果为()。
下列主管税务机关对欠税的纳税人做出的行为中，符合《税收征收管理法》及有关政策规定的有()。
“音乐舞蹈起源于性的冲动，起源于恋爱”是()的说法。
已知x=zey+z确定函数z=z(x，y)，则dz|(e，0)=________．
PresidentProsperAvrilhasbeenarrestedonchargeof______.

最新回复(0)

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

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

软考中级

在Linux中，_________命令可将文件以修改时间顺序显示。

某公司有2000台主机，则必须给它分配(1)个C类网络。为了使该公司的网络地址在路由表中只占一行，给它指定的子网掩码必须是(2)。(2)

路由表如下图所示，如果一个分组的目标地址是220．117．5．65,则会被发送给__________端口。(2013年上半年试题)NetworkInterfacenext—hop220．117．I．0／24e0directlyconnecte

VLAN之间的通信通过(18)________________实现。

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

在下图的SNMP配置中，能够响应Manager2的getRequest请求的是()。

[程序]#include＜ioStream.h＞template＜classT＞classArray；template＜classT＞classArrayBody{friend

识别关联的多重度是面向对象建模过程中的一个重要步骤。根据说明中给出的描述，完成图10-4中的(1)～(6)。请从表10-2中选择方法，完成图10-5中的(7)～(10)。

当图像分辨率为800×600，屏幕分辨率为640×480时，(13)。

被视为“近代中国开眼看世界之第一人”是（ ）

A．3′→5′B．5→3′C．N端→C端D．C端→N端DNA的合成方向是

与糖尿病相关的遗传性综合征包括

生产经营单位应当向从业人员如实告知作业场所和工作岗位存在的（），防范措施以及事故应急措施。

某平面任意力系向O点简化后，得到如图4-13所示的一个主矢F’B和一个主矩Mo，则该力系的最后简化结果为()。

下列主管税务机关对欠税的纳税人做出的行为中，符合《税收征收管理法》及有关政策规定的有()。

“音乐舞蹈起源于性的冲动，起源于恋爱”是()的说法。

已知x=zey+z确定函数z=z(x，y)，则dz|(e，0)=________．

PresidentProsperAvrilhasbeenarrestedonchargeof______.

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

被视为“近代中国开眼看世界之第一人”是（　　　）