首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设n是描述问题规模的正整数，下面程序片段的时间复杂度是( )。 i=2j； while(i＜n／3) i=i*3；
设n是描述问题规模的正整数，下面程序片段的时间复杂度是( )。 i=2j； while(i＜n／3) i=i*3；
admin
2019-12-10
75
问题
设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://www.kaotiyun.com/show/V93i777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
若有4个进程共享同一程序段，每次允许3个进程进入该程序段，用P、V操作作为同步机制，则信号量S的取值范围是()。
下图所示为双总线结构机器的数据通路，IR为指令寄存器，PC为程序计数器(具有自增功能)，M为主存(受R／W信号控制)，AR为地址寄存器，DR为数据缓冲寄存器，ALU由加、减控制信号决定完成何种操作，控制信号G控制的是一个门电路。另外，线上标注有小圈表示有控
在AOE网络中关键路径叙述正确的是()。
设有两个子网202．118．133．0／24和202．118．130．0／24，如果进行路由汇聚，得到的网络地址是()。
在操作系统的以下功能中，不需要硬件支持的是()。
某二叉树的先序和后序序列正好相反，则该二叉树一定是()。
请求分页管理系统中，假设某进程的页表内容见表A一2。页面大小为4KB，一次内存的访问时间为100ns，一次快表(TLB)的访问时间为10ns，处理一次缺页的平均时间为10Sns(已含更新TLB和页表的时间)，进程的驻留集大小固定为2，采用最近最少使用置
假定某计算机字长16位，没有Cache，运算器一次定点加法时间等于100ns，配置的磁盘旋转速度为每分钟3000转，每个磁道上记录两个数据块，每一块有8000B，两个数据块之间间隙的越过时间为2ms，主存周期为500ns，存储器总线宽度为16位，总线带宽为
按照IEEE754标准规定的32位浮点数(41A4C000)16对应的十进制数是()。
单级中断系统中，中断服务程序内的执行顺序是_______。Ⅰ．保护现场Ⅱ．开中断Ⅲ．关中断Ⅳ．保存断点Ⅴ．中断事件处理Ⅵ．恢复现场Ⅶ．中断返回
随机试题
患者，女，52岁。缺失，行固定义齿修复，46为基牙。1年后基牙有跳痛，其主要原因为()
运动员参赛时可以服用的药品是()。
在纽约外汇市场上，美元对瑞士法郎的即期汇率USD1=CHF1.0149～1.0169，美元对瑞士法郎3个月远期汇率的点数是20～30，则美元对瑞士法郎的远期汇率是( )。
下列关于工业企业销售商品收入确认的表述中，不正确的是()。
下面哪一特征属于性格的意志特征?()
新课程重视不同课程领域(特别是综合实践活动、体育、艺术等)对学生发展的独特价值，淡化学科界限，强调学科间的_________与_________。
所谓职业道德，就是同人们的执业活动紧密联系的符合职业特点所要求的()的总和。
1．8，3．6，7．2，14．4，()，57．6
文革之前的十年中，我国所取得的经济建设成就中不包括()
下列程序的输出结果是()。#include＜stdio.h＞main(){inta=3,b=2,c=1；if(a＜b)if(b＜O)c=0；elsec++
最新回复
(
0
)
