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

admin2019-07-12 18

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

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

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

软考中级

相关试题推荐

下面的地址中，可以分配给某台主机接口的地址是_____________。
若路由器的路由信息如下，则最后一行路由信息是__________得到的。(2011年上半年试题)R3#showiprouteGateway0f1astresortisnotset192．168．0．0／24iSsubnetted
在生成树协议(STP)中，根交换机是根据什么来选择的?(60).
网络系统设计过程中，物理网络设计阶段的任务是____________。
工作站A的IP地址是202，117．17．24/28，而工作站B的IP地址是202．117．17．100/28，当两个工作站直接相连时不能通信，怎样修改地址才能使得这两个工作站可以互相通信？(56)。
计算机在进行浮点数的相加(减)运算之前先进行对阶操作，若x的阶码大于y的阶码，则应将__________。
在某并发系统中，有一个发送进程A、一个接收进程B、一个环形缓冲区BUFFER、信号量S1和S2。发送进程不断地产生消息并写入缓冲区BUFFER，接收进程不断地从缓冲区BUFFER取消息。假设发送进程和接收进程可以并发地执行，那么，当缓冲区的容量为N时，如何
阅读下列说明和数据流图，回答问题1至问题3。说明某图书管理系统的主要功能是图书管理和信息查询。对于初次借书的读者，系统自动生成读者号，并与读者基本信息(姓名、单位、地址等)一起写入读者文件。系统的图书管理功能分为四个方面：购入新书、读者借
阅读以下说明和VisualBasic代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】某绘图系统定义了一个抽象类IShape，现有三个类CPoint、CLine和CCircle，它们都具有IShape界面。相应的类图关系如图7-1所示。
当图像分辨率为800×600，屏幕分辨率为640×480时，(13)。

随机试题

浮球式液位计根据浮球与容器的相对位置，可分为()。
犬上唇唇沟上、中1／3交界处的穴位是
广东某地厕所多建在鱼塘上，用人畜粪给鱼塘施肥，并且当地居民喜生食冰虾与醉虾，这就造成了一些人畜共患寄生虫病的发生。生吃冰虾与醉虾后，一些居民出现消瘦、倦怠乏力、食欲减退、腹泻、腹痛、腹部饱胀等症状；部分居民出现浮肿、腹水、脾肿大、贫血等类似肝硬化的症状。
QRS综合波代表
A、缺铁性贫血B、慢性失血性贫血C、巨幼细胞贫血D、再生障碍性贫血E、急性失血性贫血叶酸缺乏可导致
位于水库下游()km范围内的管道穿(跨)越工程防洪安全要求，应根据地形条件、水库容量等进行防洪设计。
下列关于固定利率和浮动利率的说法，正确的有()。
美国国家专利局授予发明者专利的数量，1971年为56000项，1978年降低到45000项，而用于科研与开发的国家投入，1964年达到国民生产总值的3%，1978年只有2.2%，而在此期间，在美国对科研与开发的投入不断减少的同时，联邦德国与日本在这方面的投
(1)在考生文件夹中有一个工程文件sjt3．vbp，窗体上有2个命令按钮、1个水平滚动条和1个计时器，其名称分别为Command1、Commanct2、HScroll1和Timer1，如图3—8(a)所示。程序运行后，按钮Command1、Command2
Whoarethespeakers?

最新回复(0)

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

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

软考中级

下面的地址中，可以分配给某台主机接口的地址是_____________。

若路由器的路由信息如下，则最后一行路由信息是__________得到的。(2011年上半年试题)R3#showiprouteGateway0f1astresortisnotset192．168．0．0／24iSsubnetted

在生成树协议(STP)中，根交换机是根据什么来选择的?(60).

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

工作站A的IP地址是202，117．17．24/28，而工作站B的IP地址是202．117．17．100/28，当两个工作站直接相连时不能通信，怎样修改地址才能使得这两个工作站可以互相通信？(56)。

计算机在进行浮点数的相加(减)运算之前先进行对阶操作，若x的阶码大于y的阶码，则应将__________。

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

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

浮球式液位计根据浮球与容器的相对位置，可分为()。

犬上唇唇沟上、中1／3交界处的穴位是

QRS综合波代表

A、缺铁性贫血B、慢性失血性贫血C、巨幼细胞贫血D、再生障碍性贫血E、急性失血性贫血叶酸缺乏可导致

位于水库下游()km范围内的管道穿(跨)越工程防洪安全要求，应根据地形条件、水库容量等进行防洪设计。

下列关于固定利率和浮动利率的说法，正确的有()。

(1)在考生文件夹中有一个工程文件sjt3．vbp，窗体上有2个命令按钮、1个水平滚动条和1个计时器，其名称分别为Command1、Commanct2、HScroll1和Timer1，如图3—8(a)所示。程序运行后，按钮Command1、Command2

Whoarethespeakers?

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