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

admin2019-12-10 29

问题设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

学硕统考专业

相关试题推荐

在一个长度为n(n>1)的带头结点的单链表h上，设有尾指针r(指向尾结点)，则执行()操作与链表的长度有关。
在集中式总线仲裁中，()方式响应时间最快。
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程A先得到CPU运行，进程B后运行。进程A的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms，结束。进程B的运行轨迹为：计算50
某计算机的CPU主频为500MHz，CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0．5MB／s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间
在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是()。
在CRC码中，接收端检查出某一位数据出错后，一般采用的纠正方法是()。
假设计算机系统采用CSCAN(循环扫描)磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空闲状态。如果将磁盘替换为随机访问的Flash半导体存储器(如u盘、SSD等)，是否有比CSCAN更高效的磁盘调度策略?若有，给出磁盘调度策略的名称并说明
以下关于查找方法的说法正确的是()。I顺序查找法只能在顺序存储结构上进行Ⅱ折半查找法可以在有序的双向链表上进行Ⅲ分块查找的效率与线性表被分为多少块有关
动态ROM的刷新以()为单位。
使用海明码来检出并纠正一位错，当有效代码长度为8位时，至少需要()位校验位。

随机试题

背景某市政务服务中心办公大楼工程，地下为3层连体车库，地上24层，其中：裙房6层，檐高27m，报告厅混凝土结构局部层高8m，演艺厅钢结构层高8m。框架—剪力墙结构，基础埋深12m。地下水位在底板以上2m。由于现场场地开阔，故地质勘察报告和设计文件推荐基坑
正常卵黄囊的超声测量值是
以下关于咽旁间隙描述，错误的是
女，46岁。突发上腹痛14小时，频繁呕吐胃内容物，疼痛阵发性加剧，向右肩放射2小时后发热伴腹胀，无寒战、腹泻。既往有上腹饱胀5年，按“胃痛”治疗后，偶有好转。查体：T：38．5℃，P：101次／分，BP：95／40mmHg，P：23次／分。心肺无异常，腹胀
质量控制的目的是()。
调压站是城市燃气管网系统中用来调节和稳定管网压力的设施，通常是由调压器，阀门，（），安全装置，旁通管及测量仪表等组成。
社会保险的特点主要包括()。
人工智能有近期、远期和终极三重威胁，我们在发展人工智能时必须慎重，不应盲目。在人工智能发展上首先要做好风险管控，这样才能为人类造福。这体现的哲学观点是：
假设用12个二进制位表示数据。它能表示的最大无符号整数为(1)；若采用原码，它能表示的最小负整数为(2)。
【B1】【B4】

最新回复(0)

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

计算机408

学硕统考专业

在一个长度为n(n>1)的带头结点的单链表h上，设有尾指针r(指向尾结点)，则执行()操作与链表的长度有关。

在集中式总线仲裁中，()方式响应时间最快。

在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是()。

在CRC码中，接收端检查出某一位数据出错后，一般采用的纠正方法是()。

以下关于查找方法的说法正确的是()。I顺序查找法只能在顺序存储结构上进行Ⅱ折半查找法可以在有序的双向链表上进行Ⅲ分块查找的效率与线性表被分为多少块有关

动态ROM的刷新以()为单位。

使用海明码来检出并纠正一位错，当有效代码长度为8位时，至少需要()位校验位。

正常卵黄囊的超声测量值是

以下关于咽旁间隙描述，错误的是

质量控制的目的是()。

调压站是城市燃气管网系统中用来调节和稳定管网压力的设施，通常是由调压器，阀门，（），安全装置，旁通管及测量仪表等组成。

社会保险的特点主要包括()。

人工智能有近期、远期和终极三重威胁，我们在发展人工智能时必须慎重，不应盲目。在人工智能发展上首先要做好风险管控，这样才能为人类造福。这体现的哲学观点是：

假设用12个二进制位表示数据。它能表示的最大无符号整数为(1)；若采用原码，它能表示的最小负整数为(2)。

【B1】【B4】