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

admin2019-12-10 62

问题设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://www.kaotiyun.com/show/V93i777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

下列选择中，()不是操作系统关心的主要问题。

设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。

在集中式总线仲裁中，()方式响应时间最快。

一个UDP用户的数据报的数据部分长为8192字节。那么通过以太网来传播该UDP数据报时，最后一个IP分片的数据长度是()。

在机器数中，正数的符号位用“1”表示的是()。

设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][O]的存储地址为860，则a[3][5]的存储地址为()。

主机A向主机B连续发送了两个TCP报文段，其序号分别为70和100。试问：(1)第一个报文段携带了多少个字节的数据?(2)主机B收到第一个报文段后发回的确认中的确认号应当是多少?(3)如果主机B收到第二个报文段后发回的确认中的

某二叉树的先序和后序序列正好相反，则该二叉树一定是()。

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

二氧化碳灭火剂的主要优点是()。

结合桑螵蛸药性，试用中医药理论阐述桑螵蛸的功效与主治病证。

培养哪种微生物的分离培养基中需要加入青霉素

血清蛋白电泳时通常用pH8．6缓冲液，此时各种蛋白质带有的电荷为

当桥梁基桩桩孔较深且倾斜度较大时，可用于检测钻孔倾斜度的设备有()。

专项规划是指导该领域的发展以及审批核准该领域重大项目和安排重大投资的()。

根据《证券法》的规定，某上市公司的下列人员中，不得将其持有的该公司的股票在买入后6个月内卖出，或者在卖出后6个月内又买人的有()。

心理健康教育属于我国学校德育范畴。()

耦合和内聚是评价模块独立性的两个主要标准，其中【】反映了模块内各成分之间的联系。