设n是描述问题规模的正整数，下面程序片段的时间复杂度是( )。 i=2j； while(i＜n／3) i=i*3；

admin2019-12-10 34

问题设n是描述问题规模的正整数，下面程序片段的时间复杂度是( )。
i=2j；
while(i＜n／3)
i=i*3；

选项 A、0(log₂n)
B、0(n)
C、0(

)
D、0(n³)

答案A

解析考查时间复杂度。在程序中，执行频率最高的语句为“i=i*3”。设该基本语句一共执行了k次，根据循环结束条件，有n＞2*3^k≥n／3，由此可得算法的时间复杂度为O(log₃n)=O(lgn)=O(log₂n)。
注：题中k=log₃n，又因log₃n=lgn／lg3，即k的数量级为lgn，由此可知，在时间复杂度为对数级别的时候，底数数字的改变对于整个时间复杂度没有影响，也可一律忽略底数写为O(log₁n)。

转载请注明原文地址:https://kaotiyun.com/show/V93i777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

设n是描述问题规模的正整数，下面程序片段的时间复杂度是( )。 i=2j； while(i＜n／3) i=i*3；

计算机408

学硕统考专业

指令字长为12位，每个地址码为3位，采用扩展操作码的方式，设计4条三地址指令、16条二地址指令、64条一地址指令和16条零地址指令。(1)给出一种操作码的扩展方案。(2)计算该方案操作码的平均长度。

在AOE网络中关键路径叙述正确的是()。

如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题：(1)该TCP／IP网络使用的是哪一类IP地址。(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构

进程从运行状态转换为就绪状态的可能原因是()。

给定二叉树结点的结构定义typedefstructnode*link：structnode{intitem，linkl，r；}；给定数组inta[L．r]，编写递归程序，由数组a[]建立锦标树。如给定数组a[0．4]={‘A’，‘M’，‘P’，‘L’，‘E

某机采用计数器定时查询方式来进行总线判优控制，共有4个主设备竞争总线使用权，当汁数器初值恒为102时，4个主设备的优先级顺序为()。

简述国际服务目标市场国选择的影响因素。

在Word2010编辑状态下，绘制一个图形，首先应该选择【】

You’dbetterletmeknowassoonasthereisa(n)_________positioninthebranchoffice.

炙甘草汤证的脉症见

直肠肛管疾病最常见的并发症是()

下列哪些物品可按展览品申报进境：关于展览品和展览用品的进境许可证件管理，下列表述正确的是：

一天你在街上看到一位衣衫整洁的老人显得很慌张．并且精神有些恍惚，你上前询问，却发现他不记得任何亲人的联系方式。作为一名公安干警．你会怎么做?

A.takingmedicinesB.coldvirusesC.theheatofyourbodyD.varioussymptomsA.takemedicinestorelieve【T13】________ofcol

在32位编译器上，设有定义char*str1="Hello",str2[]="Hello";，则以下语句printf("%d%d",sizeof(str1),sizeof(str2));的输出结果是（）。

A、Congratulations!B、Itisadeal.C、Ihopeso.D、Idon’thaveajob.A本题考查对别人表示祝贺的表达。当别人说了一个好消息时，自己应该表示祝贺。A)“祝贺你”，是恰当的回答。