首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设n是描述问题规模的正整数,下面程序片段的时间复杂度是( )。 i=2j; while(i<n/3) i=i*3;
设n是描述问题规模的正整数,下面程序片段的时间复杂度是( )。 i=2j; while(i<n/3) i=i*3;
admin
2019-12-10
57
问题
设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结点的祖先。
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址?(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所分配的地址对TC
一个字节多路通道连接D1、D2、D3、D4、D5共5台设备,这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求,请回答下列问题:(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字
若浮点运算结果尾数不是规格化数,将进行结果规格化。结果规格化有左规和右规之分,下列操作中,属于结果规格化的操作是()。I.尾数左移1位,阶码加1Ⅱ.尾数左移1位,阶码减1Ⅲ.尾数右移1位,阶码加1Ⅳ.尾数右移1位,阶码减1
四位运算器框图如下图所示,ALU为算术:逻辑单元,A和B为三选一多路开关,预先已通过多路开关A的sw门向寄存器R1,R2送入数据如下:R1=0101,R2=1010。寄存器BR输出端接四个发光二极管进行显示。其运算过程依次如下:(1)R1(A)
某计算机系统的内存储器由(2ache和主存构成,Cache的存取周期为45纳秒,主存的存取周期为200纳秒。已知在一段给定的时间内,CPU共访问内存4500次,其中340次访问主存。问:如果Cache为8行,主存16块,分别采用三种方式映射主存的第9块
下面()协议中,客户端和服务器之间采用面向无连接的协议进行通信。
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(e1,e2,…,en);i=1:while(所剩边数>=顶点数){从图中删去ei;若图不再连通,则恢复ei;i=
以下关于查找方法的说法正确的是()。 Ⅰ顺序查找法只能在顺序存储结构上进行 Ⅱ折半查找法可以在有序的双向链表上进行 Ⅲ分块查找的效率与线性表被分为多少块有关
下列说法正确的是()。Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
随机试题
《民政部关于进一步加快推进民办社会工作服务机构发展的意见》提出要进一步增强民办社会工作服务机构内部治理能力,督促民办社会工作服务机构建立健全以章程为核心的各项规章制度,健全理事会、监事会制度,完善法人治理结构,恪守三个原则,这三原则分别是民间性、公益性和(
__________theopportunity,everyoneofuswillbeasuccess.
2006年5月17日,马来西亚人陈某驾驶货轮在我国领海运输我国限制进口货物,被我国某海关查获。某海关经查认定,陈某运输的以上货物无合法证明,其以运往马来西亚海防为名,实际准备运往我国内地。某海关认定陈某的行为已构成走私,决定没收其所有物品。香港某有限公司不
下列不属于项目经理责任制内涵的是()。
在WindowsXP中文件有四种属性:存档、只读、隐藏、系统。()
本票自出票日起,付款期限最长不得超过2个月。()
里姆斯基一科萨科夫的管弦乐作品《野蜂飞舞》适合下面的哪种指挥图示?()
试析美国次贷危机对我国经济的影响及对策。
微型计算机系统中,PROM是
WhataccountsforthegreatoutburstofmajorinventionsinearlyAmerica—breakthroughsuchasthetelegraph,thesteamboatand
最新回复
(
0
)