首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设n是描述问题规模的正整数，下面程序片段的时间复杂度是( )。 i=2j； while(i＜n／3) i=i*3；
设n是描述问题规模的正整数，下面程序片段的时间复杂度是( )。 i=2j； while(i＜n／3) i=i*3；
admin
2019-12-10
31
问题
设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://jikaoti.com/ti/LHDjFFFM
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
某计算机的Cache共有16块，采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。
拿内存加上外存容量之和与虚拟存储空间相比，其大小关系是()。
在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是()。
给定页面请求序列RS=cadbebabcd，页框为4，起始为空，写出LRU页面置换过程。
若一个栈的输入序列为1，2，3…n，输出序列的第一个元素是i，则第j个输出元素是()。
已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成?请简述原因。
在一个按字节编址的计算机中，若数据在存储器中以小端方案存放。假定int型变量i的地址为08000000H，i的机器数为01234567H，地址：08000000H单元的内容是()。
某主机的IP地址为l80．80．77．55，子网掩码为255．255．252．0。若该主机向其所在子网发送广播分组，则目的地址可以是
假设Internel的两个自治系统构成的网络如题47图所示，自治系统AS1由路由器R1连接两个子网构成；自治系统As2由路由器R2、R3互联并连接3个子网构成。各子网地址、R2的接口名、Rl与R3的部分接口IP地址如题47图所示。请回答下列问题。若
假定某计算机字长16位，没有Cache，运算器一次定点加法时间等于100ns，配置的磁盘旋转速度为每分钟3000转，每个磁道上记录两个数据块，每一块有8000B，两个数据块之间间隙的越过时间为2ms，主存周期为500ns，存储器总线宽度为16位，总线带宽为
随机试题
切除肾上腺引起动物死亡的原因，主要是由于缺乏()
A．消瘦，乏力，腹胀B．贫血，出血倾向C．腹泻，蜘蛛痣D．腹水伴脾大E．肝脏进行性肿大，可伴红细胞增多症肝硬化最常见的临床表现
腹痛剧烈的急性胰腺炎病人宜
催化剂可加快反应速率的原因，下列叙述正确的是()。[2013年真题]
一般来讲，运用小组工作方法，可以产生以下几个方面成效：()。
教育技术是教育过程中所用到的各种物化手段。()
《唐律.名例律》规定：“其本应重而犯时不知者，依凡论；本应轻者，听从本。”《疏议》规定：“假有叔侄别处生长，素不相识，侄打伤叔，官司推问始知，听依凡人斗法。”以上规定意在区分()
Eachofushasapicture,howevervague,ofwhatwewouldliketoaccomplishbeforewedie.Howclosewegettoattainingthisg
请将以上[C++代码1]与[C++代码2]程序段中的(1)～(7)空缺处的语句填写完整。请用150字以内的文字简要说明[C++代码1]、[C++代码2]这两种对传输门进行状态模拟的设计思路的区别之处。
A、Expanditsbusinessbeyondgroceries.B、Fire25,000ofitscurrentemployees.C、CutitsDVDpublishingbusiness.D、Sellthebu
最新回复
(
0
)
