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

admin2019-07-12 30

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

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

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

软考中级

相关试题推荐

WindowsServer2008R2默认状态下没有安装IIS服务，必须手动安装。配置下列()服务前需先安装IIS服务。
防火墙的工作层次是决定防火墙效率及安全的主要因素，下面的叙述中正确的是(44)。
网络配置如下图所示，为路由器Routerl配置访问网络1和网络2的命令是(1)。路由配置完成后，在Routerl的(2)可以查看路由，查看路由采用的命令是(3)。(3)
OSPF协议使用(39)分组来保持与其邻居的连接。
某公司有2000台主机，则必须给它分配(1)个C类网络。为了使该公司的网络地址在路由表中只占一行，给它指定的子网掩码必须是(2)。(1)
网络系统设计过程中，物理网络设计阶段的任务是____________。
ATM网络采用了许多通信量管理技术以避免拥塞的出现，其中(34)是防止网络过载的第一道防线。
两个主机通过电缆直接相连，主机A的IP地址为220．17．33．24／28，而主机B的IP地址为220．17．33．100／28，两个主机互相ping不通，这时应该____________。
阅读以下说明和VisualBasic代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】某绘图系统定义了一个抽象类IShape，现有三个类CPoint、CLine和CCircle，它们都具有IShape界面。相应的类图关系如图7-1所示。
阅读以下说明和C语言函数，应填入(n)处。【说明】在一个分布网络中，资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中，资源会有损耗。例如，天然气的气压会减少，电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗

随机试题

下列哪项不是瓜蒌的功效()(2001年第32题)
英国某法院曾审理一件颇为棘手的刑事案。一名叫乔治的年轻人设法进入某皇家空军机场，坐在机场跑道上观看天上的飞机。其被警察带走，并于几天后被送上法庭。乔治的辩护律师为其辩道，《官方机密条例》规定：“不得在禁区附近妨碍皇家军队成员的行动。”虽然军用机场是个“禁区
设f"(x)连续，求证∫abxf"(x)dx=[bf’(b)-f(b)]-[af’(a)-f(a)]．
男性，65岁。既往有高血压病史。因反复心前区闷痛1周入院，并出现夜间阵发性呼吸困难，端坐呼吸。查体：血压110／60mmHg，心率106次／分，心尖部可闻及3／6级收缩期杂音，两下肺可闻及稍许细小湿性啰音。双下肢无水肿。此时应采用的药物是
1分子乙酰CoA经过三羧酸循环氧化能生成
按照我国目前的规定，在工程量清单计价过程中，分部分项工程单价不包括()。
原始凭证是登记明细分类账的依据，记账凭证是登记总分类账的依据。()
Mysisterdoesn’tlikeskating,______.
田先生认为，绝大部分笔记本电脑运行速度慢的原因不是CPU性能太差，也不是内存容量太小，而是硬盘速度太慢，给老旧的笔记本电脑换装固态硬盘可以大幅提升使用者的游戏体验。以下哪项如果为真，最能质疑田先生的观点?
Whenyouopenyourelectronicmail,youmayfindinformationabouthowtobuymedicine,cheapairlinetickets,books,computerp

最新回复(0)

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

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

软考中级

WindowsServer2008R2默认状态下没有安装IIS服务，必须手动安装。配置下列()服务前需先安装IIS服务。

防火墙的工作层次是决定防火墙效率及安全的主要因素，下面的叙述中正确的是(44)。

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

OSPF协议使用(39)分组来保持与其邻居的连接。

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

网络系统设计过程中，物理网络设计阶段的任务是____________。

ATM网络采用了许多通信量管理技术以避免拥塞的出现，其中(34)是防止网络过载的第一道防线。

两个主机通过电缆直接相连，主机A的IP地址为220．17．33．24／28，而主机B的IP地址为220．17．33．100／28，两个主机互相ping不通，这时应该____________。

阅读以下说明和VisualBasic代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】某绘图系统定义了一个抽象类IShape，现有三个类CPoint、CLine和CCircle，它们都具有IShape界面。相应的类图关系如图7-1所示。

下列哪项不是瓜蒌的功效()(2001年第32题)

设f"(x)连续，求证∫abxf"(x)dx=[bf’(b)-f(b)]-[af’(a)-f(a)]．

1分子乙酰CoA经过三羧酸循环氧化能生成

按照我国目前的规定，在工程量清单计价过程中，分部分项工程单价不包括()。

原始凭证是登记明细分类账的依据，记账凭证是登记总分类账的依据。()

Mysisterdoesn’tlikeskating,______.

田先生认为，绝大部分笔记本电脑运行速度慢的原因不是CPU性能太差，也不是内存容量太小，而是硬盘速度太慢，给老旧的笔记本电脑换装固态硬盘可以大幅提升使用者的游戏体验。以下哪项如果为真，最能质疑田先生的观点?

Whenyouopenyourelectronicmail,youmayfindinformationabouthowtobuymedicine,cheapairlinetickets,books,computerp

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