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

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

admin2019-12-10  55
问题 设n是描述问题规模的正整数，下面程序片段的时间复杂度是(    )。
i=2j；
while(i＜n／3)
    i=i*3；
选项 A、0(log2n)
B、0(n)
C、0()
D、0(n3)
答案A
解析 考查时间复杂度。在程序中，执行频率最高的语句为“i=i*3”。设该基本语句一共执行了k次，根据循环结束条件，有n＞2*3k≥n／3，由此可得算法的时间复杂度为O(log3n)=O(lgn)=O(log2n)。
    注：题中k=log3n，又因log3n=lgn／lg3，即k的数量级为lgn，由此可知，在时间复杂度为对数级别的时候，底数数字的改变对于整个时间复杂度没有影响，也可一律忽略底数写为O(log1n)。
转载请注明原文地址:https://kaotiyun.com/show/V93i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)