设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。 int i=1： while(i＜=n) i=i*2：

admin2019-12-10 41

问题设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。
int i=1：
while(i＜=n)
i=i*2：

选项 A、O(log₂n)
B、O(n)
C、O(nlog₂n)
D、O(n²)

答案A

解析这是一个比较有趣的问题。如果不仔细分析的话，可能会得到O(n)的结果。关键在于分析出while语句执行的次数。由于循环体中，i=i*2，所以循环执行的次数是log₂n，由此可见，算法的时间复杂度不是由问题规模n直接决定，而是log₂n。

转载请注明原文地址:https://kaotiyun.com/show/ys3i777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

真值0在原码、反码和补码机器数形式下()。
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后，得到IP地址都不一样，可能吗?为什么?
某计算机采用微程序控制方式，微指令字长32位，采用字段直接编码的控制方式，共有55个微命令，可分为6个互斥组，分别包含1、3、7、8、12、24个微命令。另外，该机共有5个可判定的外部条件，采用断定方式形成后续微指令地址。(1)设计该机微指令的格式，
某机字长32位，它的存储容量为256MB，按字节编址，则它的寻址范围大小为()。
就绪队列中有n个进程等待使用一个CPU，那么，如果采用不同的调用算法，就有()种调度顺序。
假定在一个处理机上执行的操作如下：作业估计服务时间片优先数A103B11C23D14E52这些
某中央处理器的数据通路如图所示。MDR为内存数据寄存器，PC为程序计数器，IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释：为什么要设置T暂存器?(3)假定指
设某计算机有四个中断源，优先顺序按1→2→3→4降序排列，若1、2、3、4中断源的服务程序中对应的屏蔽字分别为1110、0100、0110、1111，试写出这四个中断源的中断处理次序(按降序排列)。若四个中断源同时有中断请求，画出CPU执行程序的轨迹。
某计算机的主存地址空间大小为256MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下：假定int类型数据用32位补码表示，程序
假设某系统总线在一个总线周期中并行传输4B信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz，则总线带宽是____。

随机试题

下列不是邮寄访问法的优点的是()
A．Austin-Flint杂音B．Graham-Steell杂音C．胸骨左缘第2肋间连续性杂音D．突然出现的胸骨左缘第4肋间的舒张期杂音重度二尖瓣狭窄
把符合t检验条件的资料做秩和检验，则
取断根时易引起上颌窦穿孔的牙是采用翻瓣术取牙根时易损伤颏神经的牙是
A．内泻热结B．活血祛瘀C．和解清热D．泻火除湿E．缓急止痛大柴胡汤中配伍芍药的主要意义是()
A、驱风健胃B、清暑利湿C、解表化湿，理气和中D、祛风，行气，降逆，消炎，镇痛E、清热解暑，去湿生津砂仁驱风油的功效是
下列住宅设计应计算的技术经济指标中，何者是正确的?
蚂蚁在从蚁穴回到食物源的途中，会留下一种成为信息素的化学物质。蚂蚁根据信息素的气味，来回于蚁穴和食物源之间，把食物运回蚁穴。当气温达到摄氏45度以上，这种信息素几乎都会不留痕迹地蒸发。撒哈拉沙漠下午的气温都在摄氏45度以上。如果上述断定为真，最能支持以下哪
8086当前指令的地址存放在(　　　)中。
数据库管理系统是()。

最新回复(0)

设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。 int i=1： while(i＜=n) i=i*2：

计算机408

学硕统考专业

真值0在原码、反码和补码机器数形式下()。

什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后，得到IP地址都不一样，可能吗?为什么?

某机字长32位，它的存储容量为256MB，按字节编址，则它的寻址范围大小为()。

就绪队列中有n个进程等待使用一个CPU，那么，如果采用不同的调用算法，就有()种调度顺序。

假定在一个处理机上执行的操作如下：作业估计服务时间片优先数A103B11C23D14E52这些

某中央处理器的数据通路如图所示。MDR为内存数据寄存器，PC为程序计数器，IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释：为什么要设置T暂存器?(3)假定指

假设某系统总线在一个总线周期中并行传输4B信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz，则总线带宽是____。

下列不是邮寄访问法的优点的是()

A．Austin-Flint杂音B．Graham-Steell杂音C．胸骨左缘第2肋间连续性杂音D．突然出现的胸骨左缘第4肋间的舒张期杂音重度二尖瓣狭窄

把符合t检验条件的资料做秩和检验，则

取断根时易引起上颌窦穿孔的牙是采用翻瓣术取牙根时易损伤颏神经的牙是

A．内泻热结B．活血祛瘀C．和解清热D．泻火除湿E．缓急止痛大柴胡汤中配伍芍药的主要意义是()

A、驱风健胃B、清暑利湿C、解表化湿，理气和中D、祛风，行气，降逆，消炎，镇痛E、清热解暑，去湿生津砂仁驱风油的功效是

下列住宅设计应计算的技术经济指标中，何者是正确的?

8086当前指令的地址存放在( )中。

数据库管理系统是()。

8086当前指令的地址存放在(　　　)中。