设n是描述问题规模的正整数，下面程序片段的时间复杂度是( )。 i=2j； while(i＜n／3) i=i*3；

admin2019-12-10 70

问题设n是描述问题规模的正整数，下面程序片段的时间复杂度是( )。
i=2j；
while(i＜n／3)
i=i*3；

选项 A、0(log₂n)
B、0(n)
C、0(

)
D、0(n³)

答案A

解析考查时间复杂度。在程序中，执行频率最高的语句为“i=i*3”。设该基本语句一共执行了k次，根据循环结束条件，有n＞2*3^k≥n／3，由此可得算法的时间复杂度为O(log₃n)=O(lgn)=O(log₂n)。
注：题中k=log₃n，又因log₃n=lgn／lg3，即k的数量级为lgn，由此可知，在时间复杂度为对数级别的时候，底数数字的改变对于整个时间复杂度没有影响，也可一律忽略底数写为O(log₁n)。

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

设n是描述问题规模的正整数，下面程序片段的时间复杂度是( )。 i=2j； while(i＜n／3) i=i*3；

计算机408

学硕统考专业

对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是()。

计算机系统采用补码运算是为了()。

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题：(1)该TCP／IP网络使用的是哪一类1P地址。(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所

一个FTP的用户，发送了LIST命令来获取服务器的文件列表，这时候服务器应该通过()端口来传输该列表。

在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?

页式存储系统的逻辑地址是由页号和页内地址两部分组成，地址变换过程如下图4-1所示。假定页面的大小为8K，图中所示的十进制逻辑地址9612经过地址变换后，形成的物理地址a(十进制)是()。

CPU在响应中断的过程中，保护现场的工作由()完成。

中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是_______。

神经细胞动作电位去极相的产生是由于()

低钾性碱中毒常出现于

关于如何根据社会主义法治理念完善我国宪法的权力制约原则，下列哪些选项是正确的？(2012—卷一—59，多)

环境影响报告表的主要内容不包括()。

急滩按成因可分为()。

采购商与供应商之间的竞争关系是()的竞争。

资产的未来现金流量为外币的，应当以资产产生的未来现金流量的结算货币为基础预计其未来现金流量，然后按照计算现金流当日的即期汇率折算为记账本位币，最后根据记账本位币适用的折现率计算未来现金流量的现值。()

我国农村工作的中心是坚持()。

背叛国家罪的主体是特殊主体。(　　)

有以下程序：#includevoidfun(char**p){++P；printf("％s＼n"，p)；}main(){chara[]={"Morning

设n是描述问题规模的正整数，下面程序片段的时间复杂度是( )。 i=2j； while(i＜n／3) i=i*3；

计算机408

学硕统考专业

对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是()。

计算机系统采用补码运算是为了()。

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题：(1)该TCP／IP网络使用的是哪一类1P地址。(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所

一个FTP的用户，发送了LIST命令来获取服务器的文件列表，这时候服务器应该通过()端口来传输该列表。

在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?

页式存储系统的逻辑地址是由页号和页内地址两部分组成，地址变换过程如下图4-1所示。假定页面的大小为8K，图中所示的十进制逻辑地址9612经过地址变换后，形成的物理地址a(十进制)是()。

CPU在响应中断的过程中，保护现场的工作由()完成。

中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是_______。

神经细胞动作电位去极相的产生是由于()

低钾性碱中毒常出现于

关于如何根据社会主义法治理念完善我国宪法的权力制约原则，下列哪些选项是正确的？(2012—卷一—59，多)

环境影响报告表的主要内容不包括()。

急滩按成因可分为()。

采购商与供应商之间的竞争关系是()的竞争。

资产的未来现金流量为外币的，应当以资产产生的未来现金流量的结算货币为基础预计其未来现金流量，然后按照计算现金流当日的即期汇率折算为记账本位币，最后根据记账本位币适用的折现率计算未来现金流量的现值。()

我国农村工作的中心是坚持()。

背叛国家罪的主体是特殊主体。( )

有以下程序：#includevoidfun(char**p){++P；printf("％s＼n"，*p)；}main(){char*a[]={"Morning

背叛国家罪的主体是特殊主体。(　　)

有以下程序：#includevoidfun(char**p){++P；printf("％s＼n"，p)；}main(){chara[]={"Morning