首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设n是描述问题规模的正整数，下面程序片段的时间复杂度是( )。 i=2j； while(i＜n／3) i=i*3；
设n是描述问题规模的正整数，下面程序片段的时间复杂度是( )。 i=2j； while(i＜n／3) i=i*3；
admin
2019-12-10
61
问题
设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
学硕统考专业
相关试题推荐
下列各种情况中，应采用异步通信方式的是()。
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项，首先访问结点3，与3邻接的结点4、2都未曾访问过，故3后面因该为2、4(或4、2)，故D错。
在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n个结点，采用三叉链表存储时，每个结点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，最后一个结点下标为k(起
下列的网络协议中，()的运输层协议是使用TCP的。
将要相互通信双方怎样进行建立TCP连接?在TCP报文段的首部中只有端口号而没有IP地址，当TCP将其报文段交给IP层时，IP协议怎样知道目的IP地址呢?为什么把IP地址又称为“虚拟地址”，把TCP连接说成是“虚连接”?假设在建立连接时使用2次握手而非3次握
指令系统中设置多种不同的寻址方式，可以()。
传输层用于标识不同的应用的是()。
某图形显示器的分辨率为640×480，刷新频率为50Hz，且假定水平回扫期和垂直回扫期各占水平扫描周期和垂直扫描周期的20％，试计算图形显示器的行频、水平扫描周期、每个像素的读出时间和视频带宽。若分辨率提高到1024×768，刷新频率提高到60Hz，再次计
已知L为没有头结点的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符或数字字符或其它字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符。(要求用最少的时间和最少的空间)。
假设Internel的两个自治系统构成的网络如题47图所示，自治系统AS1由路由器R1连接两个子网构成；自治系统As2由路由器R2、R3互联并连接3个子网构成。各子网地址、R2的接口名、Rl与R3的部分接口IP地址如题47图所示。请回答下列问题。R
随机试题
关于右心室，描述错误的是
在潜在任职人员的能力和条件中，智力素质不包括()。
现金及银行存款日记账按规定应采用订本式账簿，总分类账和明细分类账既可以用订本账，也可以用活页账。()
在下列()中,技术分析将无效。
个体工商户与企业联营而分得的利润,按()征收个人所得税。
每条长200米的三个圆形跑道相交于A点，张三、李四、王五三个队员从三个跑道的交点A处同时出发，各取一条跑道练习长跑。张三每小时跑5公里，李四每小时跑7公里，王五每小时跑9公里。问三人第四次在A处相遇时，他们跑了多长时间?()
以下各项中，不属于绩效考评类型的是()。
购买力平价的理论基础是()。
信息要满足一定的质量属性，其中信息()指信息的来源、采集方法、传输过程是可以信任的，符合预期。
Muchmeaningcanbe【C1】______,clearly,withoureyes,soitisoftensaidthateyescanspeak.Doyouhavesuchkindofexperie
最新回复
(
0
)
