首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设n是描述问题规模的正整数,下面程序片段的时间复杂度是( )。 i=2j; while(i<n/3) i=i*3;
设n是描述问题规模的正整数,下面程序片段的时间复杂度是( )。 i=2j; while(i<n/3) i=i*3;
admin
2019-12-10
45
问题
设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
学硕统考专业
相关试题推荐
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
既考虑作业等待时间又考虑作业执行时间的调度算法是()。
就绪队列中有n个进程等待使用一个CPU,那么,如果采用不同的调用算法,就有()种调度顺序。
某计算机的Cache共有16块,采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节,按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
拿内存加上外存容量之和与虚拟存储空间相比,其大小关系是()。
请利用队列的基本操作写出判定一棵二叉树是否为完全二叉树的算法。要求以二叉链表作为二叉树的存储结构。函数原型为:intIsFull_Bitree(BitreeT)。
描述滑动窗口机制及其作用。比较停止一等待协议,多帧滑动窗口和后退N帧协议,多帧滑动窗口与选择重传协议的区别。
若浮点运算结果尾数不是规格化数,将进行结果规格化。结果规格化有左规和右规之分,下列操作中,属于结果规格化的操作是()。I.尾数左移1位,阶码加1Ⅱ.尾数左移1位,阶码减1Ⅲ.尾数右移1位,阶码加1Ⅳ.尾数右移1位,阶码减1
下面()协议中,客户端和服务器之间采用面向无连接的协议进行通信。
随机试题
相对不适合行全髋关节置换术的是:
患者女性,44岁,近2个月劳累后感到乏力、胸闷、下肢水肿,血压95/60mmHg,叩诊心界左大,心尖部可闻及1/6~2/6级收缩期杂音。心电图显示左室高电压,完全左束支阻滞。最可能的诊断’患者女性,40岁,间断胸闷、乏力10余年,超声心动图显示二尖瓣狭
患者,女,45岁。半月来常于夜间睡眠时憋醒,伴咳嗽、咳粘液痰,气喘,两肺底闻及湿哕音。该表现属于
患者,男,32岁,在屋内使用火盆烤火时昏迷在屋内,被家人发现后送至医院,查血液碳氧血红蛋白实验呈阳性,诊断为一氧化碳中毒。下列一氧化碳中毒急救措施哪项是错误的
货币形态的演进经历了四个主要的阶段:实物货币、表征货币、()和电子货币。
背景资料:某广场地下车库工程,建设面积18000m2。建设单位和某施工单位根据《建设工程施工合同(示范文本)》(GF一2013—0201)签订了施工承包合同,合同工期140天。工程实施过程中发生了下列事件:事件一:施工单位将施
消防性能化设计以消防安全工程学为基础,采用的防火设计方法区别与传统的按照建筑规范标准进行设计,但其防火设计目标具有一致性。因此,必须确保采用消防性能化设计的建筑的消防安全水平不能()按照现行国家标准规范进行防火设计的消防水平。
约束理论(TOC)的实质是什么?用它来系统地回答任何企业改进过程中哪三个问题?
1938年,毛泽东在()会议上作的题为《论新阶段》的政治报告中最先提出了“马克思主义中国化”这个科学命题。
形式逻辑思维的发展主要表现为()。
最新回复
(
0
)