首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设n是描述问题规模的正整数,下面程序片段的时间复杂度是( )。 i=2j; while(i<n/3) i=i*3;
设n是描述问题规模的正整数,下面程序片段的时间复杂度是( )。 i=2j; while(i<n/3) i=i*3;
admin
2019-12-10
52
问题
设n是描述问题规模的正整数,下面程序片段的时间复杂度是( )。
i=2j;
while(i<n/3)
i=i*3;
选项
A、0(log
2
n)
B、0(n)
C、0(
)
D、0(n
3
)
答案
A
解析
考查时间复杂度。在程序中,执行频率最高的语句为“i=i*3”。设该基本语句一共执行了k次,根据循环结束条件,有n>2*3
k
≥n/3,由此可得算法的时间复杂度为O(log
3
n)=O(lgn)=O(log
2
n)。
注:题中k=log
3
n,又因log
3
n=lgn/lg3,即k的数量级为lgn,由此可知,在时间复杂度为对数级别的时候,底数数字的改变对于整个时间复杂度没有影响,也可一律忽略底数写为O(log
1
n)。
转载请注明原文地址:https://kaotiyun.com/show/V93i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
以下叙述不正确的是()。
序列的“中值记录”指的是:如果将此序列排序后,它是第n/2个记录。试写出一个求中值记录的算法。
下列的网络协议中,()的运输层协议是使用TCP的。
系统总线中地址线的功能是用于选择()。
一个磁盘有N个磁道,寻道时每移过一个磁道耗时T秒,文件相邻的数据块在磁盘上存放的位置平均相隔13个磁道,磁盘旋转延时平均R秒,每个存储块的传输时间为P秒,在这种情况下,传输100个数据块需要的时间是()。
为了防止各种意外可能破坏文件,文件系统保护文件的方法可以是()。
一个TCP连接总是以1KB的最大段长发送TCP段,发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是_
设有一个二维数组A[m][n]在存储中按行优先存放(数组的每一个元素占一个窄间),假设A[0][0]存放位置在780(10),A[4][6]存放位置在1146(10),则A[6][20]存放在()位置(其中(10)、表明用十进制数表示)。
随机试题
EmilyDickinsonwassometimescuriousaboutthefeelingofspeechofdeathandinoneofherpoemsshewroteaboutthe______ofd
唯一能够通过胎盘的免疫球蛋白是
低钾血症心电图的改变有
胆道手术回病房后“T”形管要
水泥稳定土、石灰土、工业废渣稳定土基层施工技术中具有相同要求的有()。
当事人对付款时间没有约定或者约定不明的,利息应付时间是()。
根据《会计法》的规定,公司企业在确认、计量和记录资产、负债、所有者权益、收入、费用、成本和利润时所遵循的依据是( )。
被评估成套设备购建于2006年12月,账面价值100万元,2011年对设备进行技术改造,追加投资20万元,2016年12月对该设备进行评估。经评估人员调查分析得到如下数据:(1)从2006年到2011年,每年该类设备价格上升率为10%,而从2011年至
读书时,即使书中的字都认得了,话全懂了,也未必就知道作书人的意思。意思是离不开语言的,但有些是语言文字所不能完全表达出来的。如果仅局限于语言文字,死抓住语言文字不放,那就成为死读书了。语言文字是帮助了解书的意思的拐棍。这就是古人所说的“得意忘言”,在读书中
有以下程序#includemain(){charc;do{c=getchar();putchar(c);}while(c!=’#’);printf("\n");}执行时如输入:abcdefg##,则输出结果是()。
最新回复
(
0
)