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

admin2019-12-10 69

问题设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://www.kaotiyun.com/show/ys3i777K

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

计算机408

学硕统考专业

相关试题推荐

在一个长度为n(n>1)的带头结点的单链表h上，设有尾指针r(指向尾结点)，则执行()操作与链表的长度有关。
某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程A先得到CPU运行，进程B后运行。进程A的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms，结束。进程B的运行轨迹为：计算50
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连，只要互相间接通过道路即可)，并要求增设的道路条数为最少，要解决这个问题，问：(1)
某32位计算机系统采用段页式虚拟存储管理，现有一个进程被分成5段，其段号和段长见下表，段内分页，页表见下，存放在内存中，每页的长度为4096B。进程运行到某一个指令，其地址为(2，3，010)，当前CPU的寄存器和地址加法器的状态如图所示，当上述指令执行时
快速排序算法中，如何选取一个界值(又称为轴元素)，影响着快速排序的效率，而且界值也并不一定是被排序序列中的一个元素。例如，我们可以用被排序序列中所有元素的平均值作为界值。编写算法实现以平均值为界值的快速排序方法。
已知一组关键字为(26，36，41，38，44，15，68，12，6，51，25)，用链地址法解决冲突。假设装填因子a＝0．75，散列函数的形式为H(K)＝KMODP，回答下列问题：(1)构造散列函数；(2)画出散列表；(
某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：设该Cache的命中率为98％，如果Cache的速度是主存的5倍，则该机采用Cache时存储系统的速度是不采用
下面说法错误的是()。(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度0(2n)的算法(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界(4)同一个算法，实现

随机试题

X线特性：________、________、________、________。
北宋初期，宰相制度的建立原则始终是()
药品安全法律责任是指由于违反药品法律法规所应承担的法律后果，包括以下哪种构成要件
防潮层采用聚氯乙烯卷材施工时，粘贴的方法除螺旋形缠绕法外，还有()。
下列不属于盈利能力指标的是()。
想法和感觉是不同的,虽然他们常常相伴而行,但是想法是由感觉或情绪而产生的,感觉则进一步演化为情绪。()
【中国民权保障同盟】vip2014年中国近代史真题
简述公司外部融资与销售增长的关系。
贝克曼工程正在考虑进行资本结构的调整。公司目前负债规模2000万元，负债利率8％，当前发行在外的股份为200万股，每股价格为40元。该公司是一家零增长的公司，将利润全部作为红利分配。公司的EBIT、为1493．3万元，税率为40％。无风险利率为6％，市场风
TheScienceofAnthropologyAThroughvariousmethodsofresearch,anthropologiststrytofittogetherthepiecesofthehum

最新回复(0)

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

计算机408

学硕统考专业

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

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

已知一组关键字为(26，36，41，38，44，15，68，12，6，51，25)，用链地址法解决冲突。假设装填因子a＝0．75，散列函数的形式为H(K)＝KMODP，回答下列问题：(1)构造散列函数；(2)画出散列表；(

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：设该Cache的命中率为98％，如果Cache的速度是主存的5倍，则该机采用Cache时存储系统的速度是不采用

X线特性：________、________、________、________。

北宋初期，宰相制度的建立原则始终是()

药品安全法律责任是指由于违反药品法律法规所应承担的法律后果，包括以下哪种构成要件

防潮层采用聚氯乙烯卷材施工时，粘贴的方法除螺旋形缠绕法外，还有()。

下列不属于盈利能力指标的是()。

想法和感觉是不同的,虽然他们常常相伴而行,但是想法是由感觉或情绪而产生的,感觉则进一步演化为情绪。()

【中国民权保障同盟】vip2014年中国近代史真题

简述公司外部融资与销售增长的关系。

TheScienceofAnthropologyAThroughvariousmethodsofresearch,anthropologiststrytofittogetherthepiecesofthehum

X线特性：、、、。