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

admin2019-12-10 52

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

学硕统考专业

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

以下叙述不正确的是()。

序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。

下列的网络协议中，()的运输层协议是使用TCP的。

系统总线中地址线的功能是用于选择()。

一个磁盘有N个磁道，寻道时每移过一个磁道耗时T秒，文件相邻的数据块在磁盘上存放的位置平均相隔13个磁道，磁盘旋转延时平均R秒，每个存储块的传输时间为P秒，在这种情况下，传输100个数据块需要的时间是()。

为了防止各种意外可能破坏文件，文件系统保护文件的方法可以是()。

设有一个二维数组A[m][n]在存储中按行优先存放(数组的每一个元素占一个窄间)，假设A[0][0]存放位置在780(10)，A[4][6]存放位置在1146(10)，则A[6][20]存放在()位置(其中(10)、表明用十进制数表示)。

EmilyDickinsonwassometimescuriousaboutthefeelingofspeechofdeathandinoneofherpoemsshewroteaboutthe______ofd

唯一能够通过胎盘的免疫球蛋白是

低钾血症心电图的改变有

胆道手术回病房后“T”形管要

水泥稳定土、石灰土、工业废渣稳定土基层施工技术中具有相同要求的有()。

当事人对付款时间没有约定或者约定不明的，利息应付时间是()。

根据《会计法》的规定，公司企业在确认、计量和记录资产、负债、所有者权益、收入、费用、成本和利润时所遵循的依据是(　　)。

有以下程序#includemain(){charc;do{c=getchar();putchar(c);}while(c!=’#’);printf("\n");}执行时如输入：abcdefg##,则输出结果是（）。

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

计算机408

学硕统考专业

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

以下叙述不正确的是()。

序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。

下列的网络协议中，()的运输层协议是使用TCP的。

系统总线中地址线的功能是用于选择()。

一个磁盘有N个磁道，寻道时每移过一个磁道耗时T秒，文件相邻的数据块在磁盘上存放的位置平均相隔13个磁道，磁盘旋转延时平均R秒，每个存储块的传输时间为P秒，在这种情况下，传输100个数据块需要的时间是()。

为了防止各种意外可能破坏文件，文件系统保护文件的方法可以是()。

设有一个二维数组A[m][n]在存储中按行优先存放(数组的每一个元素占一个窄间)，假设A[0][0]存放位置在780(10)，A[4][6]存放位置在1146(10)，则A[6][20]存放在()位置(其中(10)、表明用十进制数表示)。

EmilyDickinsonwassometimescuriousaboutthefeelingofspeechofdeathandinoneofherpoemsshewroteaboutthe______ofd

唯一能够通过胎盘的免疫球蛋白是

低钾血症心电图的改变有

胆道手术回病房后“T”形管要

水泥稳定土、石灰土、工业废渣稳定土基层施工技术中具有相同要求的有()。

当事人对付款时间没有约定或者约定不明的，利息应付时间是()。

根据《会计法》的规定，公司企业在确认、计量和记录资产、负债、所有者权益、收入、费用、成本和利润时所遵循的依据是( )。

有以下程序#includemain(){charc;do{c=getchar();putchar(c);}while(c!=’#’);printf("\n");}执行时如输入：abcdefg##,则输出结果是（）。

根据《会计法》的规定，公司企业在确认、计量和记录资产、负债、所有者权益、收入、费用、成本和利润时所遵循的依据是(　　)。